Здравейте колеги,
Домашното от втората тема за алгоритми върху графи е качено.
Извинявам се за забавянето, срещнах сериозни затруднения да разпиша примери за задачи, които не съм решавал. За някои от задачите все още не сме добавили примерен вход и изход, ще се постараем близките 1-2 дни да ги допълним, за да може да тествате решенията си.
Срокът за предаване и оценяване в системата е удължен.
Това домашно ми повдига много въпроси и на мене. Схванах че първа задача иска Прим, но както каза колегата Прим просто не дава оптимални резултати в някой ситуации, тогава излиза добрия въпрос DP ли да ползвам и да пиша коментари вътре че излизат различни резултати, защото DP вади по оптимални решения или да си оставя Прим алгоритъма. Или по добре поставен въпроса идеята на задачата да упражним Прим ли е или да я решим оптимално?
На 3та задача или по точно за Dijkstra алгоритъма ми излиза следния въпрос, понеже много се блъсках да опитам да го направя оптимално, ако използвам BinaryHeap за приоритетна опашка при намирането на по добър път към node, се иска да се преподреди опашката (предполагам с идеята че новия път може да го постави на по предна позиция за обхождане), но при положение че всички node-ове трябва да бъдат обходени така или иначе, няма ли този процес само да ни забави. При голяма опашка едно преподреждане изглежда като много по скъпа операция от операцията за презаписване на разстоянието. Сега като обмислям нещата може би самият въпрос е какво печелим от използването на приоритетна опашка за Dijkstra.
И аз си задавам същият въпрос :)
По-бързо е с BinaryHeap, защото операцията за намиране на най-малък елемент е константа, а DecreaseKey е със сложност log(V) . Така нареченото "преподреждане" всъщност е доста бърза операция, която е с порядъци по-добра от линейното търсене - особено при по-голям брой възли.
Edit: Пфф 2 дена по късно успях да вдяна защо приоритетната опашка е по бърза. Някой друг ако се чуди, има смисъл да е приоритетна опашка, защото винаги избирайки най-късото разстояние от началото, гарантира че когато стъпим на връх няма по-кратък път до него от старта и в продължение на това, няма смисъл да се проверява разстоянието от такъв връх до други вече обходени върхове (нещо, което трябва да правим при произволно обхождане), общо взето е това, печелим от спестяване на проверки.