Софтуерно Инженерство
Loading...
+ Нов въпрос
Filkolev avatar Filkolev 4501 Точки

[Homework] Advanced Graph Algorithms

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

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

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

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

Тагове:
nakov avatar nakov SoftUni Team Trainer 5296 Точки

Вече има примерен вход и примерен изход на всички задачи от темата "Advanced Graph Algorithms", както и картинки, за по-лесна ориентация + насоки за решение (hints).

Имайте предвид, че това е една от най-важните и най-трудните теми в курса и поне една от задачите на изпита ще са върху материала от тази тема.

Наков

2
malkstor avatar malkstor 348 Точки

Здравейте :)

Темата наистина е тегавичка, поне за сравнително начинаещ като мен. От лекциите почти всичко ми е ясно, но като седна да пиша става весело и още се опитвам да отлепя от първата задача на лаб-а.

Алгоритъма на Крускал по заданието изглежда горе-долу така, с TODO-тата както ги разбрах аз:

var spanningTree = new List<Edge>();
edges.Sort();
foreach (Edge edge in edges)
{
    int rootStartNode = FindRoot(edge.StartNode, parent);
    int rootEndNode = FindRoot(edge.EndNode, parent);
    if (rootStartNode != rootEndNode)
    {
        spanningTree.Add(edge);
        parent[edge.EndNode] = edge.StartNode;
    }
}

с допълнение сортирането на входните ребра на графа на ред 2. Без него получавам:

Minimum spanning forest weight: 53
(0 3) -> 9
(0 5) -> 4
(0 8) -> 5
(1 4) -> 8
(1 7) -> 7
(2 6) -> 12
(3 6) -> 8

а с него:

Minimum spanning forest weight: 82
(3 5) -> 2
(0 5) -> 4
(0 8) -> 5
(1 7) -> 7
(6 8) -> 7
(1 4) -> 8
(3 6) -> 8
(0 3) -> 9
(2 6) -> 12
(3 8) -> 20

в първия случай ребрата са правилния брой, но не са правилните, а във втория - разстоянията са ок, но има излишни ребра, и не мога да разбера къде е заровено кучето, дето се вика :D

Тук е целия клас.

1
27/10/2015 22:25:39
Filkolev avatar Filkolev 4501 Точки

Трябва да кажеш, че rootStartNode е родител на rootEndNode (или обратното).

Обяснението е направено с пример с три ребра, което е малко, за да се покаже логиката на смяна на родителя. Двата върха имат различни корени, това, което трябва да се направи, е единият корен да стане дете на другия, за да се съединят дърветата. Ако кажеш, че единият нод е дете на другия, реално прекъсваш връзката с предишния му родител и от там се получават грешките. Ще помисля дали няма по-добър начин да се опише, за да е по-ясно.

2
malkstor avatar malkstor 348 Точки

Благодаря ти Фил, проработи :)

parent[rootEndNode] = rootStartNode;

1
Filkolev avatar Filkolev 4501 Точки

Проблемът е в обяснението, ще трябва да го коригирам, защото е подвеждащо в този си вид.

2
dim4o avatar dim4o 289 Точки

Здравейте,

Имам неясноти по разбирането на условоието на първа задача от домашното. Най-вече ме обърка този Hint накрая. Според мен ако се действа по тази схема изобщо няма да има гаранция дали ще се изпълни условието да се свържат колкото се може повече клиенти. Пример:

Ако на диаграмата от първия пример за възел 2 е закачен възел А и реброто 2-А има тежест 8 например и предположим, че за А има навързани верижно още 100 ребра - А-B-C-D.... с тежест 1. Ако пуснем Прим, той ще предпочете най малкото ребро, което свързва свързаните до момента клиенти с нов клиен и ще спре преди да надхвърли лимита, т.е ще имаме същия изход като на примерната диграма и ще имаме присъединени 3 нови клиента. Ако тръгнем пък от 2-A-B-C ще можем да присъединим 13 нови клиента за цена 20. Подобна е ситуацията ако първоначално нямаме никакви връзки. Трябва да започнем или от случайно място, което ще доведе потенциално до грешен резултат или от възел който е край на най-малкото ребро, което пак може да е грешно (заради контрапример подобен на горния). Не съм убеден , че точно в този конкрете случай  "лакомия" подход ще работи.

Друго решение е да пуснем Prim от всеки свободен възел и да спираме когато се свържем към съществуващата мрежа(ако има такава). Но това съществено се различава като подход от упътването и не мисля, че такава е била идеята.

Освен това на последния пример изхода също не го разбирам много, защото мрежата е разцепена. Реално мрежата не трябва ли по дефиниция да е силно свързана част в графа. Няма логика според мен 5-6 да са отделени от останалата част.То ако ще е така по-добре с модификация на Kruskal и на всяка стъпка да се взима най-малкото ребро и единствено гледаме да не свързваме ребра с общ root.

Вие как приемате това условие?

3
29/10/2015 00:35:50
mihayloff14 avatar mihayloff14 825 Точки

Много добър point. Наистина, в такъв случай алгоритъма който е описан няма да сработи.

Тогава задачата става малко по-сложна - ще се наложи да се използва динамично оптимиране. Например, при всеки нод, да се опитваме да намерим най-оптималния MST за всеки от наследниците му при даден бюджет като критерия за най-оптимален ще бъде броя на свързаните node-ове поради условието на задачата.

1
dim4o avatar dim4o 289 Точки

@mihayloff14

Да, става доста по-различна и по-интересна задача, но най-вероятно не е била такава идеята. Въпреки това предложението ти за използване на DP е много добро и заслужава да се пробва. Но ако е валидна "разцепената" мрежа от последния пример това също ще промени нещата.

@moholovka 

Сетих се за подобно решение и че наистина ще задоволи условието. Ако мрежата реално не е мрежа и има разцепвания именно това ще е най-доброто. Просто взимаш на всяка стъпка най-малкото ребро и го включваш ако един от краищата му не е избиран досега. Мисля, че и ти правиш нещо подобно. Но това не е изобщо MST и не отговаря и на разбиранията ми за network. Може и да става въпрос в задачата за някакви локални мрежички, но определено това трябва да се поясни. А относно хинта - според мен не само на последния пример няма да работи, а няма да работи изобщо.

1
29/10/2015 10:50:21
Hristo_Penchev avatar Hristo_Penchev 388 Точки

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

0
Filkolev avatar Filkolev 4501 Точки

Мърджването е процедура при изграждането на самото дърво (MST). В различни етапи от алгоритъма ще се получат няколко дървета, които в даден момент ще се съединят - когато се добави ребро, чиито върхове принадлеждат на различни дървета. Накрая ще се получи само едно дърво.

0
Hristo_Penchev avatar Hristo_Penchev 388 Точки

Съжалявам, но отново нищо не разбрах. Може ли малко по-просто? Какво все пак се иска от нас?

0
byclops avatar byclops 126 Точки

До колкото го разбирам, във втора задача трябва да направим MST, като използваме Kruskal с Disjoint Sets Optimization, от слайд 22 в презентацията.

 

0
Innos avatar Innos SoftUni Team 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 SoftUni Team 419 Точки

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

0
03/11/2015 19:29:13
andrey.blagoev avatar andrey.blagoev 62 Точки

На задача 5 Shortest Paths with Negative Edges, най-късата дистанция не е ли [4 -> 9]: -58? Защото пътя от 4 до 3 е -5, което е по-малко от пътя от 0 до 3: -4.

0
01/11/2015 21:27:56
Filkolev avatar Filkolev 4501 Точки

Търси се най-малкото разстояние между 0 и 9, търсеният път се подава на входа.

0
andrey.blagoev avatar andrey.blagoev 62 Точки

ОК, благодаря! Сега видях, че не съм свалил последната версия на домашното.

0