|
Titlul: arbori Steiner Scris de: Neagu Gabriel din Februarie 25, 2012, 17:13:39 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 :D Titlul: Răspuns: arbori Steiner Scris de: Cosmin Negruseri din Februarie 26, 2012, 09:18:40 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. Titlul: Răspuns: arbori Steiner Scris de: FMI Ciprian Olariu din Februarie 26, 2012, 21:10:29 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 (http://infoarena.ro/algoritmiada-2012/runda-2/solutii) mai detaliat decat s-a zis pe forum? :) Titlul: Răspuns: arbori Steiner Scris de: Cosmin Negruseri din Februarie 27, 2012, 01:59:22 de ce nu completezi tu :).
Titlul: Răspuns: arbori Steiner Scris de: FMI Ciprian Olariu din Februarie 27, 2012, 10:21:32 de ce nu completezi tu :). Fiindca eu am scos pe arhiva maxim 35 puncte (neconsiderand gruparea testelor am 60) :-' Titlul: Răspuns: arbori Steiner Scris de: Cosmin Negruseri din Februarie 28, 2012, 03:45:12 daca ai inteles ideea poti sa o scrii linistit, nu trebuie sa iei maxim in concurs pt asta.
Titlul: Răspuns: arbori Steiner Scris de: Petru Trimbitas din Martie 19, 2012, 14:26:49 Am incercat sa completez eu aici solutia: http://infoarena.ro/algoritmiada-2012/runda-2/solutii/subarbore
Sper sa se inteleaga :) |