Jenereta ya Maze ya Algorithm ya Kruskal

Algorithm ya Kruskal ni algorithm ya chini ya mti ambayo inaweza kubadilishwa kwa kizazi cha maze. Ni muhimu hasa kwa ajili ya kujenga mazes kamili. Njia mbadala ya algorithm ya Kruskal ni algorithm ya Prim, ambayo pia ni algorithm ya chini ya miti, lakini kwa kuwa hutoa mazes sawa na Kruskal anaendesha haraka, sijasumbua kutekeleza Prim's.

Maze kamili ni maze ambayo kuna njia moja kutoka kwa hatua yoyote kwenye maze hadi hatua nyingine yoyote. Hiyo ina maana kwamba huwezi kuishia kuzunguka kwenye miduara, lakini mara nyingi utakutana na ncha zisizokufa, na kukulazimisha kugeuka na kurudi nyuma.

Ramani za mlolongo zinazozalishwa hapa ni pamoja na toleo chaguo-msingi bila nafasi zozote za kuanza na kumaliza, kwa hivyo unaweza kujiamulia hizo: kutakuwa na suluhu kutoka sehemu yoyote kwenye msururu hadi sehemu nyingine yoyote. Ikiwa unataka msukumo, unaweza kuwezesha nafasi iliyopendekezwa ya kuanza na kumaliza - na hata kuona suluhisho kati ya hizo mbili.

Kuhusu algorithm ya Kruskal

Algorithm ya Kruskal iliundwa na Joseph Bernard Kruskal, Jr., mtaalamu wa hisabati wa Marekani, statistician, na mwanasayansi wa kompyuta. Alielezea kwa mara ya kwanza algorithm katika 1956 katika karatasi yake "Kwenye Subtree ya Spanning ya Graph na Tatizo la Mauzo ya Kusafiri."

Algorithm imeundwa kupata mti wa chini wa urefu (MST) wa grafu, kuhakikisha kuwa vertices zote zimeunganishwa na uzito mdogo wa jumla wakati wa kuepuka mizunguko.

Jinsi algorithm ya Kruskal inavyofanya kazi kwa kizazi cha Maze

Hatua ya 1: Kuanzisha

• Kutibu kila seli katika maze kama seti tofauti (sehemu ya kipekee).
• Orodhesha kuta zote kati ya seli zilizo karibu kama kingo zinazowezekana.

Hatua ya 2: Panga Ukuta

• Shuffle au nasibu kuagiza kuta. Ikiwa kutekeleza kama algorithm ya kweli ya Kruskal, panga kuta kwa mpangilio wa nasibu (kwa kuwa kizazi cha maze hakihitaji uzito).

Hatua ya 3: Mchakato wa Ukuta

• Iterate kupitia kuta zilizokatwa.
• Ikiwa seli mbili zilizogawanywa na ukuta ni za seti tofauti (yaani, bado hazijaunganishwa kwenye maze), ondoa ukuta na kuunganisha seti.
• Ikiwa tayari wako katika seti sawa, ruka ukuta (ili kuepuka mizunguko).

Hatua ya 4: Endelea hadi kukamilika

• Rudia mchakato huu mpaka seli zote ziunganishwe, na kutengeneza mti mmoja wa kurefusha.
• Mwishoni, kila seli imeunganishwa na wengine bila vitanzi au sehemu zilizotengwa.

Kwa kuwa algorithm ya Kruskal inategemea seti za kuunganisha, inaweza kuboreshwa kwa kutumia algorithm ya Umoja-Find, ambayo hutoa njia bora ya kufuatilia seli zilizounganishwa wakati wa kizazi cha maze. Unaweza kuona utekelezaji wangu wa PHP wa algorithm ya Umoja-Find hapa: Seti ya Kuunganishwa (Union-Find Algorithm) katika PHP