Kruskal na Algorithm Maze Generator

Algorithm na Kruskal ƙaramin aiki ne na algorithm na itace da za a iya daidaita don tsarar maze. Yana da amfani musamman wajen yin wuraren da suka fi kyau. Wani maƙasudi ga algorithm na Kruskal shi ne algorithm na Prim, wanda shi ma ƙaramin algorithm na itace ne, amma tun da yake suna ƙera irin waɗannan ƙananan

Cikakken maze shine maze wanda a cikinsa akwai ainihin hanya ɗaya daga kowane wuri a cikin maze zuwa kowane wuri. Wannan yana nufin ba za ku iya ƙarasa da zagayawa cikin da'ira ba, amma sau da yawa za ku gamu da matattu, wanda zai tilasta muku juyo da komawa.

Taswirorin maze da aka samar a nan sun haɗa da sigar tsoho ba tare da kowane matsayi na farawa da ƙare ba, don haka zaku iya yanke shawarar waɗancan da kanku: za a sami mafita daga kowane wuri a cikin maze zuwa kowane wuri. Idan kuna son ilhama, zaku iya kunna shawarar farawa da ƙarewa - har ma da ganin mafita tsakanin su biyun.

Game da Algorithm na Kruskal

Joseph Bernard Kruskal, Jr., wani masanin kimiyya, mai bincike, da kuma masanin kwamfuta a Amirka ne ya halicci wannan na'urar. Ya fara kwatanta wannan tsarin a shekara ta 1956 a cikin jaridarsa "On the Short Spanning Subtree of a Graph and the Traveling Seller Problem."

An shirya wannan tsarin don a gano ƙaramin itace (MST) na tsari, kuma hakan yana tabbatar da cewa dukan ƙananan

Yadda Algorithm na Kruskal Yake Aiki ga Tsarar Maze

Mataki na 1: Fara

• Ka bi da kowane ƙwaƙwalwa da ke cikin mafarkin a matsayin sashe na bambanta (abin da ya bambanta).
• Ka lissafa dukan ganuwa tsakanin ƙwayoyin da ke kusa da su a matsayin ƙafafun da za su iya zama.

Mataki na 2: Tsara Ganuwa

• Ka juya ko kuma ka zaɓi ganuwa a hanyar da ba ta dace ba. Idan yin amfani da shi a matsayin algorithm na Kruskal na gaske, ka tara ganuwa cikin tsari na ɓata lokaci (da yake tsarar maze ba ta bukatar nauyi).

Mataki 3: Process Walls

• Ka yi fushi a cikin ganuwa da aka juya.
• Idan ƙwayoyin biyu da bangon ya raba suna cikin kayan dabam dabam (ya ce, ba a haɗa su har yanzu a cikin mafarkin), ka cire bangon kuma ka haɗa kayan.
• Kuma idan sun kasance a cikin wani wuri, to, ku ƙẽtare ganuwa.

Mataki na 4: Ci gaba har sai an kammala

• Ka maimaita wannan aikin har sai dukan ƙwayoyin su haɗa kai, ka kafa itace guda.
• A ƙarshe, kowane ƙwaƙwalwa tana da haɗin kai da wasu ba tare da ƙara ko kuma wasu sashen da ba su da shi ba.

Tun da yake algorithm na Kruskal yana dogara ga haɗa shiryoyi, za a iya kyautata shi ta wajen yin amfani da algorithm na Union-Find, wanda ke ba da hanya mai kyau na bincika ƙwayoyin da aka haɗa a lokacin tsarar maze. Za ka iya ganin yadda aka yi amfani da tsarin algorithm na UNION-Find a nan: Disjoint Set (Union-Find Algorithm) a CIKINMÃNI