Kruskal urang Algoritma Maze generator

Algoritma Kruskal mangrupikeun algoritma tangkal manjang minimum anu tiasa diadaptasi pikeun ngahasilkeun maze. Ieu hususna éféktif pikeun nyieun mazes sampurna. Alternatif pikeun algoritma Kruskal nyaéta algoritma Prim, nu ogé mangrupa algoritma tangkal Manjang minimum, Tapi saprak maranéhna ngahasilkeun mazes idéntik jeung Kruskal ngajalankeun gancang, Kuring geus teu ganggu palaksanaan Prim urang.

Maze sampurna nyaéta Maze dimana aya persis hiji jalur ti titik mana waé dina Maze ka titik séjén. Éta hartina anjeun moal bisa mungkas nepi ka sabudeureun dina bunderan, tapi anjeun bakal mindeng sapatemon dead ends, forcing anjeun ngahurungkeun sabudeureun tur balik.

Peta Maze anu dihasilkeun di dieu kalebet versi standar tanpa posisi awal sareng akhir, ku kituna anjeun tiasa mutuskeun pikeun diri anjeun: bakal aya solusi ti mana waé dina maze ka titik anu sanés. Upami anjeun hoyong inspirasi, anjeun tiasa ngaktipkeun posisi mimiti sareng bérés anu disarankeun - komo ningali solusi antara dua.

Ngeunaan Algoritma Kruskal urang

Algoritma Kruskal diciptakeun ku Joseph Bernard Kruskal, Jr., saurang matematikawan Amérika, ahli statistik, sareng élmuwan komputer. Anjeunna mimiti ngajelaskeun algoritma dina 1956 dina makalahna "On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem."

Algoritma dirancang pikeun manggihan tangkal bentang minimum (MST) tina grafik, mastikeun yén sakabéh vertice disambungkeun jeung total beurat ujung minimal mungkin bari Ngahindarkeun siklus.

Kumaha Algoritma Kruskal Gawéna pikeun Generasi Maze

Lengkah 1: Initialize

• Ngubaran unggal sél dina Maze salaku set misah (komponén unik).
• Daptar sadaya tembok antara sél padeukeut salaku poténsi edges.

Lengkah 2: Urut Tembok

• Ngacak atawa acak mesen tembok. Lamun nerapkeun eta salaku algoritma Kruskal leres, tembok diurutkeun dina urutan acak (saprak generasi Maze teu merlukeun beurat).

Lengkah 3: Témbok prosés

• Iterate ngaliwatan tembok shuffled.
• Upami dua sél dibagi ku témbok milik sét anu béda (nyaéta, aranjeunna henteu acan nyambung dina Maze), cabut témbok sareng gabungkeun set éta.
• Mun aranjeunna geus di set sarua, skip témbok (pikeun nyingkahan siklus).

Lengkah 4: Teraskeun dugi ka réngsé

• Malikan deui prosés ieu dugi ka sadaya sél disambungkeun, ngabentuk tangkal bentang tunggal.
• Dina tungtungna, unggal sél disambungkeun ka batur tanpa loop atanapi bagian terasing.

Kusabab algoritma Kruskal ngandelkeun ngahijikeun set, éta tiasa dioptimalkeun ku ngagunakeun algoritma Union-Find, anu nyayogikeun cara anu épisién pikeun ngalacak sél anu nyambung salami generasi maze. Anjeun tiasa ningali palaksanaan PHP kuring tina algoritma Union-Find di dieu: Disjoint Set (Union-Find Algorithm) dina PHP