|
Titlul: 1231 Subarbore Scris de: Andrei Grigorean din Ianuarie 22, 2012, 14:26:42 Aici puteți discuta despre problema Subarbore (http://infoarena.ro/problema/subarbore).
Titlul: Răspuns: 1231 Subarbore Scris de: Horia Cretescu din Ianuarie 24, 2012, 21:15:03 Salut, eu am facut problema de 35 de puncte cu 8 incorect , am facut roy_floyd si dupa am generat permutarile cu cele T noduri am determinat drumurile avand grija sa nu adun o muchie de 2 ori. Sunt curios cum se face de 100 de puncte daca ma poate ajuta cineva cu o idee.
Titlul: Răspuns: 1231 Subarbore Scris de: Carabet Cosmin Andrei din Ianuarie 24, 2012, 22:42:33 Salut. Cred ca ar trebui sa schimbati niste teste pentru a delimita solutia corecta de alte solutii mai putin bune :). Eu spre ex am reusit sa obtin 100 puncte cu o sol incompleta: http://infoarena.ro/job_detail/667842 .
Sunt foarte curios care-i solutia optima. Titlul: Răspuns: 1231 Subarbore Scris de: Cosmin Negruseri din Ianuarie 24, 2012, 22:51:55 Problema e una clasica si se numeste Steiner Tree Problem.
un arbore cu T frunze poate avea maxim T - 1 noduri interne. Astfel putem fixa oricare 6 noduri din graf ca noduri interne si pt cele 7 alese + cele 6 interne sa rulam un algoritm de arbore partial de cost minim. Solutia asta va fi O(n^(T - 1) * T^2). Exista si solutii mai bune, una de care stiu e O(n3^T). Titlul: Răspuns: 1231 Subarbore Scris de: Adrian Budau din Ianuarie 25, 2012, 04:56:10 Defapt poate avea maxim T - 2 noduri interne(daca prin nod intern se intelege nod cu grad mai mare ca 2).
Demonstratia e intuitiva: Arborele are x frunze, y noduri de grad 2 si z noduri interne . Suma gradelor este 2 *(x + y + z) - 2 intr-un arbore cu x + y + z noduri x + 2 * y + z * k = 2 * x + 2 * y + 2 * z - 2 unde k e media gradelor nodurilor interne(k >= 3) (k - 2) * z = x - 2 z = (x - 2) / (k - 2) <= (x - 2) / (3 - 1) = x - 2. => La noi in problema fixam doar 5 noduri nu 6 :-) Titlul: Răspuns: 1231 Subarbore Scris de: Paul Herman din Ianuarie 25, 2012, 14:54:57 Ati putea sa-mi spuneti de ce abordarea urmatoare e gresita: calculez distantele intre toate nodurile speciale, memorand drumurile intre oricare doua si apoi fac APM pe aceste drumuri, iar la sfarsit insumez costurile muchiilor din care sunt compuse drumurile avand grija sa nu le adun de mai multe ori?
Merci! Titlul: Răspuns: 1231 Subarbore Scris de: Mihai Calancea din Ianuarie 25, 2012, 20:40:28 Uite exemplul asta:
4 noduri, 4 muchii: 1 2 cu cost 3 2 3 cu cost 3 1 4 cu cost 4 4 3 cu cost 5 nodurile speciale sunt 1 , 4 , 3 Drumul minim intre 1 si 3 e 1 -> 2- > 3. Drumul minim intre 4 si 3 e 4 -> 3. Graful asociat drumurilor minime e identic cu cel initial. Daca faci APM pe el o sa-ti lege de arbore si nodul 2, care nu te intereseaza. Ideea e ca nu ai nevoie de toate nodurile din graful drumurilor minime in arbore, si nu poti face un APM selectiv in timp polinomial, fiindca daca ai fi putut, ai fi facut-o de la inceput. |