1231 Subarbore

[•wefgef]

Aici puteți discuta despre problema Subarbore.

[•ELHoria]

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.

[•cosmin79]

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.

[•Cosmin]

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).

[•freak93]

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

[•blustudio]

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!

[•klamathix]

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.