AlgorithmO #4 - Алгоритъм на Прим (минимално покриващо дърво на граф)

Днес ще ви покажа още един алгоритъм за намиране на МОД (минимално обхващащо дърво или минимално покриващо дърво). Трудно ми е да преценя дали го предпочитам пред алгоритъма на Крускал, но пък е хубаво човек да има повече от една опция.

Както и да е, този алгоритъм също не е особено труден за разбиране и само трябва да се приложи няколко пъти. Той влиза към т.нар. "greedy" (алчни) алгоритми, защото на всяка стъпка взема най-доброто възможно решение.

---

ОПИСАНИЕ:

Прим е предложил алгоритъм за намиране на минимално покриващо дърво чрез поредица от разширения на едно дърво. Началното дърво се състои от единствен произволен връх.

На всяка стъпка дървото се разширява по „алчен” начин – към него се добавя най-близкият връх, който не принадлежи на дървото, т.е., който е свързан с връх от дъвото чрез ребро с най-малко тегло.

Алгоритъмът приключва когато всички върхове се включат в дървото. Изпълняват се n-1 итерации ('n' е броят върхове/възли), тъй като на всяка се включва по едно ребро.

АЛГОРИТЪМ:

(взето от книгата на Преслав Наков, "Програмиране = ++Алгоритми")

1) Започваме строенето на МПД от произволен връх s: в началото дървото ще бъде T(H,D), H = {s}, D = Ø.
2) Повтаряме n–1 пъти:
2.1) Избираме реброто (i, j) ∈ Е, такова че:
- i ∈ H , j ∈ V \ H;
- f(i, j) е минимално.
2.2) Добавяме върха j към H и реброто (i, j) към D.

P.S: Ако горните знаци ви изглеждат плашещо, погледнете тук и тук за някои пояснения.

ПРИМЕР:

Нека използваме графа от примера за алгоритъма на Крускал: 

Първата стъпка е просто да си изберем начален връх.

Аз ще започна с 5, защото ми беше номера в класа едно време. 😀 Но може да е който и да е от другите.

Една кратка забележка - това не е "част от алгоритъма", но аз предпочитам да имам списъка от ребрата пред себе си, защото ако просто гледаш нарисувания граф или матрицата на съседство, има голям шанс да се объркаш и да изпуснеш някое от тях. 

И за да стана още по-досаден, предпочитам да имам списъка на ребрата в сортиран възходящ ред (пишейки това изречение осъзнавам, че май наистина алгоритъмът на Крускал ми харесва повече - no offense, Прим).

Ето я и таблицата, взета от предишния ми пост: 

Ребро	Тегло
5-8	1
1-2	1
6-9	1
7-6	1
1-4	2
2-3	3
3-6	3
4-3	4
6-5	12
5-9	13
2-5	13
4-7	14
4-6	16

Съветвам ви, ако имате таблицата със сортираните ребра пред себе си, да задрасквате тези, които вече са добавен към МОД (това не е необходимо, но ще улесни значително търсенето на следващото ребро).

За да сме по-практични ще превърнем таблицата в едно просто множество с всички ребра и теглата им:

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

След всяко добавяне на дадено ребро, то ще бъде оцветено в червено.

Забележете, че броят на върховете е 9, следователно ще имаме общо 8 итерации на алгоритъма.

Така, след като сме избрали 5, създаваме две множества, H и D. H ще съдържа върховете, които сме включили към МОД, а D ребрата, които сме използвали, за да постигнем това (т.е. ребрата на МОД). В началото H съдържа само избрания от нас връх (в случая 5), а D е празно множество ( Ø ).

H = { 5 }

D = Ø

Сега трябва да намерим ребро, в което участва 5, с минимално тегло. Лесно виждаме от таблицата, че това е реброто 5-8. Тъй като в реброто участва и 8, добавяме 8 към H, а 5-8 към D:

H = { 5, 8 }

D = { 5-8 }

(итерация 1)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Сега ни трябва ребро, в което участва някой от елементите на H и теглото му отново е минимално. Гледайки таблицата, най-добрият вариант е 6-5 (тъй като 5 е елемент на H). Добавяме 6 към H и 6-5 към D:

H = { 5, 8, 6 }

D = { 5-8, 6-5 }

(итерация 2)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Продължаваме смело напред. Следващото ребро, което отговаря на изискванията ни, е 6-9 (6 е част от H и теглото е минимално). Добавяме 9 към H, а 6-9 към D:

H = { 5, 8, 6, 9 }

D = { 5-8, 6-5, 6-9 }

(итерация 3)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

За жалост реброто 1-2 не съдържа върхове, които са в H, но пък 7-6 съдържа 6! Добавяме 7 към H и 7-6 към D:

H = { 5, 8, 6, 9, 7 }

D = { 5-8, 6-5, 6-9, 7-6 }

(итерация 4)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Сега сравнително лесно можем да видим, че следващото ребро ще е 3-6 (6 е част от H, теглото е минимално и преди него няма други ребра, които да използват връх от H). Добавяме 3 към H и 3-6 към D:

H = { 5, 8, 6, 9, 7, 3 }

D = { 5-8, 6-5, 6-9, 7-6, 3-6 }

(итерация 5)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Вече схванахте идеята, надявам се. Следващото ребро ще е 2-3. Добавяме 2 към H и 2-3 към D:

H = { 5, 8, 6, 9, 7, 3, 2 }

D = { 5-8, 6-5, 6-9, 7-6, 3-6, 2-3 }

(итерация 6)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Лесно забелязваме, че следващото ребро е 1-2, защото току що добавихме 2 към H и теглото е минимално. Добавяме 1 към H и 1-2 към D:

H = { 5, 8, 6, 9, 7, 3, 2, 1 }

D = { 5-8, 6-5, 6-9, 7-6, 3-6, 2-3, 1-2 }

(итерация 7)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Следващото и последно ребро (спомнете си, че алгоритъмът прави n-1 итерации) ще е 1-4. Добавяме 4 към H и 1-4 към D:

H = { 5, 8, 6, 9, 7, 3, 2, 1, 4 }

D = { 5-8, 6-5, 6-9, 7-6, 3-6, 2-3, 1-2, 1-4 }

(итерация 8)

R = { 5-8 (1), 1-2 (1), 6-9 (1), 7-6 (1), 1-4 (2),  2-3 (3), 3-6 (3), 4-3 (4), 6-5 (12), 5-9 (13), 2-5 (13), 4-7 (14), 4-6 (16) }

Това беше последната итерация.

Крайният резултат се съдържа в множеството D - това са ребрата на МОД. Теглата им са същите като тези в множеството R и горната таблица.

--- 

Това е за днес! Ако видите някоя неточност, моля кажете ми. 😉

AlgorithmO #3 - Алгоритъм на Крускал (минимално покриващо дърво на граф)

Тъй като имам предстоящ изпит именно върху алгоритмите, които представям... защо да не се възползвам от възможността да затвърдя знанията си, като ви споделя това, което научих? 😁

---

ОПИСАНИЕ:

Алгоритъмът на Крускал се използва за намиране на минимално покриващо дърво на граф (още наричано "минимално обхващащо дърво" или МОД). МОД представлява дърво, в което са включени всички върхове на графа и от всеки връх има ребро към друг, а теглото на ребрата, които ги свързват, е минимално.

АЛГОРИТЪМ:

Версия 1

1) Сортираме ребрата по реда на нарастване на теглата
2) Разглеждаме всеки връх като дърво от 1 възел
3) Преглеждаме ребрата по сортирания ред
- Ако поредното ребро съединява 2 отделни дървета, то включваме реброто в МОД и обединяваме 2-те дървета в едно.
4) Повтаряме стъпка 3 до получаването на единствено дърво.

Версия 2

(взето от книгата на Преслав Наков, "Програмиране = ++Алгоритми")

1) Създаваме n множества, като в i-тото множество поставяме i-тия връх от графа.
2) Сортираме ребрата на графа във възходящ ред (по теглата им).
3) Създаваме празно дърво T(V, Ø). След приключване на алгоритъма T ще бъде търсеното покриващо дърво.
4) Последователно (n–1 пъти) добавяме ребро (i,j) ∈ Е към T, така че да бъде изпълнено:
- теглото f(i, j) да бъде възможно най-малко (разполагаме със сортиран по теглата списък на ребрата от графа)
- върховете i и j да се намират в различни множества
След всяко добавено ребро (i,j) обединяваме множествата, в които се намират i и j.

ПРИМЕР:

Нека имаме следния граф:

Нека първо ви покажа как ща намерим МОД с първата версия на алгоритъма. 

Така, първото нещо, което трябва да направим, е да си направим списък с ребрата в графа и техните тегла. Нека използваме таблица, за да е по-прегледно:

Ребро	Тегло
1-2	1
1-4	2
4-7	14
4-6	16
7-6	1
4-3	4
2-3	3
2-5	13
3-6	3
6-5	12
6-9	1
5-9	13
5-8	1

Чудесно, сега нека ги сортираме във възходящ ред спрямо теглото (стъпка 1): 

Ребро	Тегло
5-8	1
1-2	1
6-9	1
7-6	1
1-4	2
2-3	3
3-6	3
4-3	4
6-5	12
5-9	13
2-5	13
4-7	14
4-6	16

Следващата стъпка е да създадем 9 отделни дървета от по 1 възел (за всеки възел от графа):

Сега следва забавната част! Разглеждаме всяко едно ребро по сортирания ред.

Първо 5-8. 5 и 8 са в отделни дървета, следователно това ребро ще бъде част от МОД!

5-8 ✅

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

1-2 ✅

6-9 ✅

7-6 ✅

1-4 ✅

2-3 ✅

3-6 ✅

4-3 ❌

Опа, 4-3 няма да е част от МОД. Защо? Нека да видим как изглежда МОД преди да стигнем до реброто 4-3:

4-3 няма да е част от МОД, тъй като не свързва 2 отделни дървета (както се вижда, 4 има връзка с 1, а пък 1 с 2 и накрая 2 с 3. Следователно 3 и 4 вече са в едно и също дърво.

Добре, нека да продължим напред!

6-5 дали става? Ами, 5 има връзка само с 8, следователно 6 се намира в друго дърво. Значи 6-5 е валидно ребро.

6-5 ✅

Следва 5-9. 5 има връзка с 6, а пък 6 с 9, така че двата възела са част от едно дърво и няма да добавяме реброто към МОД.

5-9 ❌

Аналогично за 2-5 (2 има връзка с 3, а 3 с 6 и 6 с 5... да, става малко объркващо, но двата възела са част от едно и също дърво).

2-5 ❌

Продължаваме с 4-7. Тук връзката е дълга и широка (4-1 => 1-2 => 2-3 => 3-6 => 6-7), но резултатът е пак същият. Това ребро отново няма да е част от МОД.

4-7 ❌

Остана и последното ребро, 4-6. Двата възела се намират в едно и също дърво (4-1 => 1-2 => 2-3 => 3-6). Не го добавяме към МОД.

И така, в крайна сметка, горното дърво се оказва МОД на графа:

Ребрата му са следните: (5-8), (1-2), (6-9), (7-6), (1-4), (2-3), (3-6), (6-5)

Теглата са същите като в таблицата горе.

---

Добре, нека решим същата задача по другия начин.

Алгоритъмът ни казва, че трябва да направим "n" множества, т.е колкото са възлите в графа. В случая са 9, затова правим 9 множества (с по 1 елемент - стойността във възела):

{ 1 }

{ 2 }

{ 3 }

{ 4 }

{ 5 }

{ 6 }

{ 7 }

{ 8 }

{ 9 }

Тъй като ще ни трябва, ето я таблицата със сортираните ребра... once again: 

Ребро	Тегло
5-8	1
1-2	1
6-9	1
7-6	1
1-4	2
2-3	3
3-6	3
4-3	4
6-5	12
5-9	13
2-5	13
4-7	14
4-6	16

Започваме с първото ребро, 5-8. Двата върха не са в едно множество, следователно това ребро ще е част от МОД (5-8 ✅). Съединяваме множествата { 5 } и { 8 }: 

{ 1 }

{ 2 }

{ 3 }

{ 4 }

{ 5, 8 }

{ 6 }

{ 7 }

{ 9 }

Продължаваме с 1-2. Абсолютно същото като предишния случай (1-2 ✅). Съединяваме множествата { 1 } и { 2 }:

{ 1, 2 }

{ 3 }

{ 4 }

{ 5, 8 }

{ 6 }

{ 7 }

{ 9 }

Схванахте идеята, но все пак... 6-9? Да, става (6-9 ✅): 

{ 1, 2 }

{ 3 }

{ 4 }

{ 5, 8 }

{ 6, 9 }

{ 7 }

Ами 7-6? Да, отново са в различни множества, така че добавяме това ребро към МОД (7-6 ✅):

{ 1, 2 }

{ 3 }

{ 4 }

{ 5, 8 }

{ 6, 9, 7 }

1-4? Валидно (1-4 ✅)! Добавяме към МОД:

{ 1, 2, 4 }

{ 3 }

{ 5, 8 }

{ 6, 9, 7 }

Аналогично за 2-3 (2-3 ✅):

{ 1, 2, 4, 3 }

{ 5, 8 }

{ 6, 9, 7 }

3-6? Отново към МОД (3-6 ✅). Спомнете си, че съединяваме множествата (а не просто добавяме единия елемент към множеството), така че сега ще имаме едно дълго множество: 

{ 1, 2, 4, 3, 6, 9, 7 }

{ 5, 8 }

И така, стигнахме до по-интересната част. 4-3 не става (4-3 ❌), защото 4 и 3 са в едно множество. Но това не важи за 6-5 (6-5 ✅), защото 6 и 5 са в различни множества. Съединяваме двете множества:

{ 1, 2, 4, 3, 6, 9, 7, 5, 8 }

Така, получихме едно дълго множество, което съдържа всички възли. Това означава, че сме приключили с намирането на ребрата, които ще са част от МОД. 5-9, 2-5, 4-7 и 4-6 няма да са част от него (5-9 ❌, 2-5 ❌, 4-7 ❌, 4-6 ❌).

В крайна сметка, МОД ще включва следните ребра:

(5-8), (1-2), (6-9), (7-6), (1-4), (2-3), (3-6), (6-5)

Резултатът е абсолютно същият. Въпрос на избор е коя "версия" на алгоритъма ще ползвате!

---

Това е за днес. Ако видите някоя неточност, моля кажете ми (аз също все още се уча)! Peeeeace.

AlgorithmO #2 - Код на Хъфман за компресиране на данни

Този алгоритъм ми харесва много, защото наистина виждам приложението му. Спомням си, че едно време се чудех как WinRAR магически смалява файлове (при това даже не нахалства и ти позволява да ползваш софтуера безкрайно, макар и да е изтекъл trial периодът 😅). Е, този алгоритъм е един от широко използваните при компресирането на данни.

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

---

ОПИСАНИЕ:

Алгоритъмът на Хъфман служи за компресиране на информация и е добър пример за алчен алгоритъм (тъй като винаги взема "най-доброто"). Идеята зад него е, че ако имаме някакво съобщение, можем да го преобразуваме в код от 0-ли и 1-ци.

За целта се използва т.нар. "дърво на Хъфман", от което се извежда и "код на Хъфман".

Ако се чудите "какво по дяволите е дърво" - ето тук има отлично обяснение на нещата, които ще трябва да знаете предварително. :)

АЛГОРИТЪМ:

1. Създават се дървета от по един възел, съответстващи на буквите от азбуката в съобщението.
2. Записват се честотите на срещане на всяка буква в корените на тези дървета
3. Избират се две дървета с минимално тегло и се обединяват в едно, като неговото тегло се получава от сумата на теглата на двете поддървета.
4. Горното действие се повтаря до получаване на единствено дърво.


ПРИМЕР: 

Съобщение: baabbcdddebbaccbdbda

Първото, което трябва да направим, е да видим кои са буквите, които участват в съобщението и колко пъти се среща всяка от тях. В случая имаме участието на само 5 букви - a, b, c, d, e.

Ето и колко пъти се среща всяка от тях:

а - 4 срещания
b - 7 срещания
c - 3 срещания
d - 5 срещания
e - 1 срещане

Следващата стъпка е да създадем 5 дървета с по 1 възел (или "връх"). Тъй като имаме само 1 възел, той представлява корен на съответното дърво.

Чудесно! Сега трябва да открием 2-те дървета с най-малко тегло (най-малка стойност) в корена. Лесно виждаме, че тези стойности са 3 и 1. Обединяваме ги в ново двоично подредено дърво. Това ново дърво ще има корен с тегло 4 (сумата от теглата на предишните 2 тегла), и наследници с тегла 3 и 1. 

Тъй като дървото е подредено, това означава че вляво добавяме по-малката стойност, а вдясно по-голямата (не правете същата грешка като мен - бях ги обърнал и резултатът не беше красив 👲).

След всичко това стигаме до следната ситуация:

Повтаряме същото! Този път най-малките стойности са 4 и 4 (не, няма значение, че стойностите са еднакви). Следваме същия принцип и получаваме следното:

Схванахте вече. Но нека отново ви кажа какво следва... 7 и 5! Ето и резултатът:

Хайде още 1 път... Разбира се, стойностите са 8 и 12, тъй като други няма. Резултатът:

Стигнахме до забавната част - вече имаме само 1 дърво. Сега следва да номерираме всяко ляво ребро с 0, и всяко дясно ребро с 1 (ребрата са стрелките), подобно на алгоритъма на Шенън-Фано.

Най-накрая получаваме дървото на Хъфман:

И сега... как да получим кода? Много просто - следваме пътя до всяка буква. Как да стигнем до буквата 'b' например? Започваме от корена 20 и преминаваме към 12 (реброто между двата възела е с тегло 1), от 12 отиваме към 7 (реброто между двата възела е с тегло 1).

В случая ни интересува последователността от теглата на ребрата до възела на дадената буква. Иначе казано, понеже първото ребро има тегло 1 и второто също има тегло 1, кодът на буквата 'b' е 11.

Аналогично намираме кода на всяка от останалите букви и получаваме следната таблица:

a	00
b	11
c	011
d	10
e	010

Така... какво беше съобщението? А, да:

baabbcdddebbaccbdbda

Сега просто заменяме всяка буква в съобщението с нейния код.

Получаваме кода на Хъфман:

11 | 00 | 00 | 11 | 11 | 011 | 10 | 10 | 10 | 010 | 11 | 11 | 00 | 011 | 011 | 11 | 10 | 11 | 10 | 00

 b     a     a     b     b     c      d     d     d     e      b     b     a      c      c      b     d     b     d    a

=> 11000011110111010100101111000110111110111000

Вече сте богове на компресирането. 😅

"Слушайте тялото си" - най-голямата пренебрегната ИСТИНА

Йо! Болен съм. При това за 3-ти път през последните 2 месеца.

Някои биха нарекли това лош късмет или биха обвинили лошото време или многото вируси, които се разпространяват от човек на човек.

Може и да греша, но аз по-скоро го наричам... глупост. Глупост от моя страна.

Това, в което се убеждавам все повече и повече, с всеки изминал ден, е, че тялото ни винаги ни дава някаква индикация, че "болестта наближава".

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

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

Липсва ни една важна част от пъзела.

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

Повечето хора се опитват да премахнат симптомите, а не това, което предизвиква болестта.

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

Сега стоя тук, отново болен, но някакси изплуват различни неприятни образи в главата ми. "Аа, пич, спомняш ли си, че вчера си махна шапката, защото ти се стори топло, ама всъщност не беше", "аа, пич, спомняш ли си, че онзи ден като тренира се беше изпотил много и беше студено, но ти игнорира този факт, защото искаше да направиш нов клип".

Не е приятно. Много по-лесно е да кажа "еми, такъв е сезонът, има много болни, вината не е моя". Но според мен далеч не е така.

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

Слушайте тялото си. Може да ви спести АДСКИ много главоболия.

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

Но за сметка на това - сега не се спирам. Опитвам се да запълня почти всяка една минута с нещо, което ме доближава до реализирането на целите ми. Гледам другите и си мисля "ха ха, виж го как бездейства, не като МЕН", но виждам само едната страна на монетата.

Макар да се гордея с това, че действам и подобрявам живота си, пак допускам една фатална грешка - пренебрегвам нуждата за почивка на тялото ми. И затова страдам.

Не правете тази грешка. Ключът е в баланса - действие + почивка. Това е просто естественият ред на нещата. Има слънчеви дни, но има и дъждовни дни. Здрави сме, но един ден се разболяваме. Раждаме се и умираме (да вкарам малко оптимизъм в цялата работа, а? :)).

А сега сериозно... нека повторя посланието.

Слушайте тялото си. Може да ви спести АДСКИ много главоболия.

Peace.