arbori Steiner

[•wizekid]

salutare
fiind dat un graf ponderat neorientat cu n noduri si m muchii , sa se afle un arbore de cost minim care sa includa t noduri specificate ( nodurile t sunt incluse in nodurile n) .. in realizarea arborelui pot fi folosite si alte noduri din cele date atata timp cat costul este minim , iar toate cele t noduri sunt incluse in el ...
dupa cate am inteles este un capitol numit arbori Steiner care rezolva probleme in genul asta , problema e ca am gasit documentatii sarace in informatii si nu ma ajuta sa inteleg mare lucru .. daca ar putea cine sa-mi explice sau sa-mi ofere link cu documentatie+model de implementare

[•Cosmin]

http://infoarena.ro/problema/subarbore

Problema asta e exact steiner tree.

Eu am fixat 5 noduri intermediare si am facut brute force pentru cele noduri fixate si cele 6 posibile intermediare.

Exista o solutie mai desteapta in 3^n * n pe care a facut-o Patcas in concurs, abordarea in n3^n e luata din un paper de cercetare.

[•scipianus]

http://infoarena.ro/problema/subarbore

Problema asta e exact steiner tree.

Eu am fixat 6 noduri intermediare si am facut brute force pentru cele noduri fixate si cele 6 posibile intermediare.

Exista o solutie mai desteapta in 3^n * n pe care a facut-o Patcas in concurs, abordarea in n3^n e luata din un paper de cercetare.

Mai completeaza cineva va rog solutia la problema Subarbore aici http://infoarena.ro/algoritmiada-2012/runda-2/solutii mai detaliat decat s-a zis pe forum? 

[•Cosmin]

de ce nu completezi tu .

[•scipianus]

de ce nu completezi tu .

Fiindca eu am scos pe arhiva maxim 35 puncte (neconsiderand gruparea testelor am 60) 

[•Cosmin]

daca ai inteles ideea poti sa o scrii linistit, nu trebuie sa iei maxim in concurs pt asta.

[•S7012MY]

Am incercat sa completez eu aici solutia: http://infoarena.ro/algoritmiada-2012/runda-2/solutii/subarbore
Sper sa se inteleaga