Greedy algoritmi

Minimum spanning tree (MST) algoritmlarini boshlashdan avval biz ular uchun umumiy – Greedy algoritmi nazariyasini ko’rib chiqamiz.

Greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi.

Batafsil tushuntirishdan avval, biz ko’rib chiqadigan graph’ga doir ba’zi osonlashtiruvchi detallarni aniqlashtirib olamiz:

Edge weight’lari unikal.
Graph’da barcha vertex’lar bog’langan (connected).

Yuqoridagi shartlar graph’da MST mavjud va yagonaligini kafolatlaydi.

Vertex’lari bog’langan va edge weight’lari unikal bo’lgan graph

Shuningdek, bizga algoritm ishlashi jarayonida bajaradigan amallarni ham oldindan bilib olish zarar qilmaydi.

Cut (qirqish). Cut deganda graph’da vertex’larni ikki bo’sh bo’lmagan to’plamga ajratish tushuniladi. Cut bo’lishi uchun biz vertex’larning birinchi to’plamini kulrang, ikkinchi to’plamini oq rangga ajratamiz. Cut deb yana crossing edge’lar to’plamiga ham aytiladi.

Crossing edge. O’tish joyi hisoblanuvchi edge’lar ikki to’plamni bir biriga bog’laydi, aniqrog’i kulrang va oq rangli vertex’larni bir-biriga bog’lovchi edge’lar – crossing edge deyiladi.

Minimum spanning tree (MST) sharti esingizdami? MST bo’lishi uchun barcha vertex’larni bog’lovchi minimum weight’li tree’ga (path’ga) ega bo’lishimiz kerak edi. Ushbu qoidadan kelib chiqadigan bo’lsak, crossing edge’lar orasidagi minimum weight’li edge albatta MST ichida bo’ladi.

Greedy algoritmi ishlash tartibi

Ish boshlanishidan oldin, barcha edge’lar bir xil rangda (kulrang) bo’ladi.
Crossing edge’lar orasida qora edge bo’lmagan cut’ni topamiz. Ular orasidan minimum weight’dagi edge’ni qoraga bo’yaymiz.
2-qadamni V – 1 edge’lar qora bo’lmaguncha davom ettiramiz. Bu yerda V vertex’lar soni

Image credit: https://algs4.cs.princeton.edu/43mst/

V – 1 edge’lar qora bo’lganida biz MSTni topgan bo’lamiz.

Greedy algoritmi – umumiy algoritm. U asosida boshqa algoritmlar ishlab chiqilgan:

Algoritmlarning cut usulini qanday tanlashi bilan farqlanadi.

Mavzu boshida biz ikki osonlashtiruvchi detal kiritgandik – unikal edge weight va bog’langan vertex’lar. Agar ularni olib tashlasak greedy qanday ishlaydi?

Weight’lar unikal bo’lmagan holatda ham MST topiladi baribir, lekin fakt – graph’da ikki MST bor bo’lishi mumkin.

Agar graph’da barcha vertex’lar bog’lanmagan – bir necha komponentlar mavjud holatida MST har bir komponent uchun hisoblanadi.