Pagini recente » Diferente pentru runda/ccex-2013-clasa-a-10-a intre reviziile 2 si 1 | Diferente pentru algoritmiada-2012/runda-2/solutii/subarbore intre reviziile 6 si 5 | Monitorul de evaluare | Diferente pentru preoni-2005/runda-3/solutii intre reviziile 21 si 6 | Diferente pentru algoritmiada-2012/runda-2/solutii/subarbore intre reviziile 6 si 7
Nu exista diferente intre titluri.
Diferente intre continut:
h1(#subarbore). 'Subarbore':problema/subarbore
Trebuie sa selectam un arbore partial de cost minim care poate avea maxim T frunze. Acesta poate avea maxim T-2 noduri interne. Astfel noi alegem cele T noduri si pe langa ele mai luam inca T-2. Pentru toate aceste posibilitati facem arborele partial de cost minim si selectam minimul.
La inceput se ruleaza algoritmul roy floyd pentru a determina toate drumurile posibile de cost minim si formam din ele un graf complet.
Complexitate: Combinari(N,T-2)*T ^2^ *logT
Trebuie sa selectam un arbore partial de cost minim care poate avea maxim T frunze. Acesta poate avea maxim T-2 noduri interne. Astfel noi alegem cele T noduri si pe langa ele mai luam inca T-2. Pentru toate aceste posibilitati facem arborele partial de cost minim pe graful complet si selectam minimul.
Complexitate: N^3^+Combinari(N,T-2)*T^2^*logT
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
