Kruskal na Algorithm Maze Generator

Tsarin aikin Kruskal shine mafi ƙarancin tsarin aikin bishiyoyi wanda za'a iya daidaita shi don samar da tsarin aikin maze. Yana da tasiri musamman wajen ƙirƙirar tsarin aikin maze cikakke. Madadin tsarin aikin Kruskal shine tsarin aikin Prim, wanda kuma shine mafi ƙarancin tsarin aikin bishiyoyi, amma tunda suna samar da tsarin aikin maze iri ɗaya kuma tsarin aikin Kruskal yana gudu da sauri, ban damu da aiwatar da tsarin aikin Prim ba.

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 Tsarin Aikin Kruskal

Joseph Bernard Kruskal, Jr., wani masanin lissafi, masanin kididdiga, kuma masanin kimiyyar kwamfuta ɗan Amurka ne ya ƙirƙiro tsarin Kruskal. Ya fara bayyana tsarin a shekarar 1956 a cikin takardarsa mai suna "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.

An tsara wannan tsari ne don nemo mafi ƙarancin bishiyar da ke yawo (MST) na jadawali, yana tabbatar da cewa dukkan layukan suna da alaƙa da mafi ƙarancin jimlar nauyin gefen yayin da ake guje wa zagayowar.

Yadda Tsarin Aiki na Kruskal ke Aiki ga Tsarin Maze

Mataki na 1: Fara

• Yi wa kowace tantanin halitta da ke cikin maze ɗin a matsayin wani tsari daban (wani abu na musamman).
• Jera dukkan bangon da ke tsakanin ƙwayoyin da ke kusa a matsayin gefuna masu yuwuwa.

Mataki na 2: Tsara Bango

• A canza ko a yi odar ganuwar ba tare da tsari ba. Idan ana aiwatar da shi a matsayin ainihin tsarin Kruskal, a tsara ganuwar a cikin tsari ba tare da tsari ba (tunda samar da maze ba ya buƙatar nauyi).

Mataki na 3: Tsarin Ganuwar

• Yi maimaitawa ta cikin bangon da aka haɗa.
• Idan ƙwayoyin halitta guda biyu da bangon ya raba suna cikin sassa daban-daban (watau, ba a haɗa su a cikin maze ba tukuna), cire bangon kuma haɗa sassan.
• Idan sun riga sun kasance a cikin saitin ɗaya, tsallake bango (don guje wa zagayowar).

Mataki na 4: Ci gaba Har Sai An Kammala

• Maimaita wannan tsari har sai dukkan ƙwayoyin halitta sun haɗu, suna samar da itace ɗaya mai faɗi.
• Ƙarshe, kowace tantanin halitta tana da alaƙa da sauran ba tare da madaukai ko sassan da aka keɓe ba.

Tunda tsarin Kruskal ya dogara ne akan haɗa saitin, ana iya inganta shi ta amfani da tsarin Union-Find, wanda ke ba da hanya mai inganci don bin diddigin ƙwayoyin da aka haɗa yayin samar da maze. Kuna iya ganin aiwatar da PHP na na tsarin Union-Find anan: Link

Karin Karatu

Idan kuna jin daɗin wannan sakon, kuna iya kuma son waɗannan shawarwari:

• Mai Ƙirƙirar Labirint na Algoritmin Eller
• Wilson's Algorithm Maze Generator
• Mai Ƙirƙirar Labirint na Farauta da Kisa