Jenereta ya Maze ya Algorithm ya Kruskal

Algorithm ya Kruskal ni algorithm ya mti yenye upana wa chini kabisa ambayo inaweza kubadilishwa kwa ajili ya uzalishaji wa maze. Inafaa sana kwa kuunda maze kamili. Njia mbadala ya algorithm ya Kruskal ni algorithm ya Prim, ambayo pia ni algorithm ya mti yenye upana wa chini kabisa, lakini kwa kuwa hutoa maze zinazofanana na Kruskal hufanya kazi haraka zaidi, sijajisumbua 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, takwimu, na mwanasayansi wa kompyuta kutoka Marekani. Alielezea algorithm hiyo kwa mara ya kwanza mwaka wa 1956 katika karatasi yake "Kwenye Mtindo Mfupi Zaidi wa Grafu na Tatizo la Muuzaji Anayesafiri.

Algorithm imeundwa ili kupata mti wa upana wa chini kabisa (MST) wa grafu, kuhakikisha kwamba vipeo vyote vimeunganishwa na uzito mdogo kabisa wa ukingo huku ikiepuka mizunguko.

Jinsi Algorithm ya Kruskal Inavyofanya Kazi kwa Kizazi cha Maze

Hatua ya 1: Anzisha

• Tumia kila seli kwenye maze kama seti tofauti (kipengele cha kipekee).
• Orodhesha kuta zote kati ya seli zilizo karibu kama kingo zinazowezekana.

Hatua ya 2: Panga Kuta

• Changanya au pangilia kuta bila mpangilio. Ukiitekeleza kama algoriti halisi ya Kruskal, panga kuta kwa mpangilio bila mpangilio (kwa kuwa utengenezaji wa maze hauhitaji uzani).

Hatua ya 3: Kuta za Mchakato

• Rudia kupitia kuta zilizochanganywa.
• Ikiwa seli mbili zilizogawanywa na ukuta ni za seti tofauti (yaani, bado hazijaunganishwa kwenye maze), ondoa ukuta na uunganishe seti hizo.
• Ikiwa tayari ziko katika seti moja, ruka ukuta (ili kuepuka mizunguko).

Hatua ya 4: Endelea Hadi Kukamilika

• Rudia mchakato huu hadi seli zote ziunganishwe, na kutengeneza mti mmoja unaozunguka.
• Mwishoni, kila seli imeunganishwa na zingine bila vitanzi au sehemu zilizotengwa.

Kwa kuwa algoriti ya Kruskal inategemea seti za kuunganisha, inaweza kuboreshwa kwa kutumia algoriti ya Union-Find, ambayo hutoa njia bora ya kufuatilia seli zilizounganishwa wakati wa uzalishaji wa maze. Unaweza kuona utekelezaji wangu wa PHP wa algoriti ya Union-Find hapa: Kiungo

Kusoma Zaidi

Ikiwa ulifurahia chapisho hili, unaweza pia kupenda mapendekezo haya:

• Kuongezeka kwa Jenereta ya Maze ya Algorithm ya Miti
• Jenereta ya Maze ya Algorithm ya Wilson
• Jenereta ya Maze ya Algorithm ya Eller