Крускалийн алгоритм төөрдөг байшин үүсгэгч
Нийтэлсэн: 2025 оны гуравдугаар сарын 19 20:33:05 (UTC)
Төгс төөрдөг байшин үүсгэхийн тулд Kruskal-ийн алгоритмыг ашиглан төөрдөг байшин үүсгэгч. Энэ алгоритм нь дунд зэргийн урт коридор, олон гарцгүй төгсгөлтэй төөрдөг байшинг бий болгох хандлагатай бөгөөд нэлээд шулуун шийдэлтэй байдаг.Kruskal's Algorithm Maze Generator
Kruskal-ийн алгоритм нь төөрдөг байшин үүсгэхэд тохируулж болох хамгийн бага хүрээтэй модны алгоритм юм. Энэ нь төгс төөрдөг байшинг бүтээхэд онцгой үр дүнтэй байдаг. Крускал алгоритмын өөр нэг хувилбар бол Примийн алгоритм бөгөөд энэ нь мөн хамгийн бага хүрээг хамарсан модны алгоритм боловч тэдгээр нь ижил төөрдөг байшин, Крускалын гүйлтийг илүү хурдан үүсгэдэг тул Примийн алгоритмыг хэрэгжүүлэхээс санаа зовсонгүй.
Төгс төөрдөг байшин гэдэг нь төөрдөг шорооны аль ч цэгээс өөр цэг хүртэл яг нэг зам байдаг төөрдөг байшин юм. Энэ нь та эргэн тойронд эргэлдэж чадахгүй гэсэн үг, гэхдээ та ихэнхдээ гарцгүй гарцтай тулгарах бөгөөд таныг эргэж, буцаж явахад хүргэдэг.
Энд үүсгэсэн төөрдөг шорооны газрын зураг нь ямар ч эхлэл, төгсгөлийн байрлалгүй анхдагч хувилбарыг агуулдаг тул та эдгээрийг өөрөө шийдэх боломжтой: төөрдөг газрын аль ч цэгээс өөр цэг хүртэл шийдэл байх болно. Хэрэв та урам зориг авахыг хүсч байвал санал болгож буй эхлэх, дуусгах байрлалыг идэвхжүүлж, тэр ч байтугай хоёрын хоорондох шийдлийг харж болно.
Крускалын алгоритмын тухай
Крускалын алгоритмыг Америкийн математикич, статистикч, компьютерийн шинжлэх ухааны мэргэжилтэн Жозеф Бернард Крускал, Жр. зохиосон. Тэрээр энэ алгоритмыг 1956 онд "Графын хамгийн богино холбогдсон мод ба Худалдагчийн аяллын асуудал" нэртэй өгүүлэлдээ анх тайлбарласан.
Алгоритм нь графын хамгийн бага жигд холболтын модыг (MST) олоход зориулагдсан бөгөөд бүх оргилуудыг хамгийн бага боломжит нийт хязгаарын жинтэй холбож, мөчлөгүүдээс зайлсхийхийг баталгаажуулдаг.
Крускалын алгоритм хэрхэн лабиринт үүсгэхэд ажилладаг вэ
Алхам 1: Эхлүүлэх
- Лабиринтын бүх клеткийг тус бүртээ өөрийн гэсэн багц (тусдаа бүрэлдэхүүн хэсэг) гэж үзнэ.
- Хөрш клеткүүдийн хоорондох бүх ханаыг боломжит хязгаарууд гэж жагсаана.
Алхам 2: Ханануудыг эрэмбэлэх
- Ханануудыг ээрэх эсвэл санамсаргүйгээр эрэмбэлнэ. Хэрэв энэ нь Крускалын алгоритм байвал, ханааг санамсаргүй эрэмбэлнэ (учир нь лабиринт үүсгэхэд жин шаардагдахгүй).
Алхам 3: Ханануудыг боловсруулах
- Ээрсэн ханануудыг дамжуулна.
- Хэрэв ханаар хуваагдсан хоёр клетк нь өөр өөр багцад багтсан бол (өөрөөр хэлбэл, тэд лабиринтэд одоогоор холбогдоогүй байгаа бол), ханааг устгаж, багцуудыг нэгтгэнэ.
- Хэрэв тэд аль хэдийн нэг багцад багтсан бол, ханааг орхиод (мөчлөгөөс зайлсхийх үүднээс).
Алхам 4: Гүйцэтгэлээ хүртэл үргэлжлүүлэх
- Энэ процессыг бүх клеткүүд холбогдсон, нэг холбогдсон мод үүссэн хүртэл давтана.
- Эцэст нь, бүх клеткүүд бусадтай ямар ч мөчлөггүй, тусгаарлагдсан хэсэггүй холбогдсон байна.
Крускалын алгоритм нь багцуудыг нэгтгэхэд суурилдаг тул, энэ нь Labyrinth үүсгэх явцад холбогдсон клеткүүдийг хянах үр ашигтай арга замыг олгодог Union-Find алгоритмыг ашиглан сайжруулж болно. Миний PHP хэрэгжилтийг эндээс харж болно: PHP хэл дээрх Disjoint Set (Union-Find Algorithm).