Софтуерно Инженерство
Loading...
Filkolev avatar Filkolev 4486 Точки

[Homework] Advanced Graph Algorithms

Здравейте колеги,

Домашното от втората тема за алгоритми върху графи е качено.

Извинявам се за забавянето, срещнах сериозни затруднения да разпиша примери за задачи, които не съм решавал. За някои от задачите все още не сме добавили примерен вход и изход, ще се постараем близките 1-2 дни да ги допълним, за да може да тествате решенията си.

Срокът за предаване и оценяване в системата е удължен.

Тагове:
Innos avatar Innos 419 Точки

Това домашно ми повдига много въпроси и на мене. Схванах че първа задача иска Прим, но както каза колегата Прим просто не дава оптимални резултати в някой ситуации, тогава излиза добрия въпрос DP ли да ползвам и да пиша коментари вътре че излизат различни резултати, защото DP вади по оптимални решения или да си оставя Прим алгоритъма. Или по добре поставен въпроса идеята на задачата да упражним Прим ли е или да я решим оптимално?
 

На 3та задача или по точно за Dijkstra алгоритъма ми излиза следния въпрос, понеже много се блъсках да опитам да го направя оптимално, ако използвам BinaryHeap за приоритетна опашка при намирането на по добър път към node, се иска да се преподреди опашката (предполагам с идеята че новия път може да го постави на по предна позиция за обхождане), но при положение че всички node-ове трябва да бъдат обходени така или иначе, няма ли този процес само да ни забави. При голяма опашка едно преподреждане изглежда като много по скъпа операция от операцията за презаписване на разстоянието. Сега като обмислям нещата може би самият въпрос е какво печелим от използването на приоритетна опашка за Dijkstra.

0
01/11/2015 18:47:28
moholovka avatar moholovka 169 Точки

Сега като обмислям нещата може би самият въпрос е какво печелим от използването на приоритетна опашка за Dijkstra.

И аз си задавам същият въпрос :)

 

0
dim4o avatar dim4o 289 Точки

По-бързо е с BinaryHeap, защото операцията за намиране на най-малък елемент е константа, а DecreaseKey е със сложност log(V) . Така нареченото "преподреждане" всъщност е доста бърза операция, която е с порядъци по-добра от линейното търсене - особено при по-голям брой възли. 

0
Innos avatar Innos 419 Точки

Edit: Пфф 2 дена по късно успях да вдяна защо приоритетната опашка е по бърза. Някой друг ако се чуди, има смисъл да е приоритетна опашка, защото винаги избирайки най-късото разстояние от началото, гарантира че когато стъпим на връх няма по-кратък път до него от старта и в продължение на това, няма смисъл да се проверява разстоянието от такъв връх до други вече обходени върхове (нещо, което трябва да правим при произволно обхождане), общо взето е това, печелим от спестяване на проверки.

0
03/11/2015 19:29:13