Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1231 Subarbore  (Citit de 1649 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« : Ianuarie 22, 2012, 14:26:42 »

Aici puteți discuta despre problema Subarbore.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
ELHoria
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #1 : 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.
Memorat
cosmin79
Strain
*

Karma: 36
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #2 : 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  Smile. 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.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #3 : 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).
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #4 : 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 Smile
Memorat
blustudio
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 9



Vezi Profilul
« Răspunde #5 : 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!
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #6 : 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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines