Вилсоны алгоритм төөрдөг байшин үүсгэгч
Нийтэлсэн: 2025 оны гуравдугаар сарын 19 20:34:34 (UTC)
Төгс төөрдөг байшин үүсгэхийн тулд Wilson-ийн алгоритмыг ашиглан төөрдөг байшин үүсгэгч. Энэ алгоритм нь өгөгдсөн хэмжээтэй бүх боломжит төөрдөг байшинг ижил магадлалтайгаар үүсгэдэг тул онолын хувьд олон төрлийн холимог байрлалтай төөрдөг байшинг үүсгэж болох боловч урт коридороос илүү богино коридортой төөрдөг байшингууд олон байдаг тул та эдгээрийг илүү олон удаа харах болно.Wilson's Algorithm Maze Generator
Вилсоны алгоритм нь давталтаар арилгасан санамсаргүй алхалтын арга бөгөөд төөрдөг байшин үүсгэхэд зориулж жигд тархсан мод үүсгэдэг. Энэ нь өгөгдсөн хэмжээтэй бүх боломжит төөрдөг шороог үүсгэх магадлал ижил байна гэсэн үг бөгөөд энэ нь төөрдөг байшин үүсгэх арга техник юм. Вилсоны алгоритмыг Aldous-Broder алгоритмын сайжруулсан хувилбар гэж үзэж болно, учир нь энэ нь ижил шинж чанартай төөрдөг байшин үүсгэдэг, гэхдээ энэ нь илүү хурдан ажилладаг тул би энд Aldous-Broder алгоритмыг хэрэгжүүлэхэд санаа зовсонгүй.
Төгс төөрдөг байшин гэдэг нь төөрдөг шорооны аль ч цэгээс өөр цэг хүртэл яг нэг зам байдаг төөрдөг байшин юм. Энэ нь та эргэн тойронд эргэлдэж чадахгүй гэсэн үг, гэхдээ та ихэнхдээ гарцгүй гарцтай тулгарах бөгөөд таныг эргэж, буцаж явахад хүргэдэг.
Энд үүсгэсэн төөрдөг шорооны газрын зураг нь ямар ч эхлэл, төгсгөлийн байрлалгүй анхдагч хувилбарыг агуулдаг тул та эдгээрийг өөрөө шийдэх боломжтой: төөрдөг газрын аль ч цэгээс өөр цэг хүртэл шийдэл байх болно. Хэрэв та урам зориг авахыг хүсч байвал санал болгож буй эхлэх, дуусгах байрлалыг идэвхжүүлж, тэр ч байтугай хоёрын хоорондох шийдлийг харж болно.
Уилсоны алгоритмын тухай
Үйлсоны алгоритм нь давтагдсан санамсаргүй хана ашиглан нэгтгэсэн тархацтай мод үүсгэх аргыг Дэвид Брус Уилсон зохиосон.
Уилсон энэ алгоритмыг 1996 онд санамсаргүй тархацтай мод болон Марковын гинжин холбоог судалж байхдаа анх танилцуулсан. Түүний судалгаа нь голчлон математик болон статистик физикт байсан ч, энэ алгоритм нь төгс нэгтгэсэн лабиринт үүсгэх чадвараараа лабиринт үүсгэхэд өргөн хэрэглэгддэг болжээ.
Уилсоны алгоритм хэрхэн лабиринт үүсгэхэд ажилладаг вэ
Уилсоны алгоритм нь санамсаргүй алхмаар дамжин зочлогдоогүй эсүүдээс замуудыг тасралтгүй сийлж, эцсийн лабиринт нь ямар ч мөчлөггүй, бүрэн холбогдсон байхыг хангадаг.
Алхам 1: Эхлүүлэх
- Ханын бүрхүүлтэй тороос эхлэнэ.
- Бүх боломжит гарам эсүүдийн жагсаалтыг тодорхойлно.
Алхам 2: Санамсаргүй эхлэл эсийг сонгох
- Ямар ч санамсаргүй эсийг сонгож, үүнийг зочилсон гэж тэмдэглэнэ. Энэ нь лабиринт үүсгэх явцад эхлэх цэг болно.
Алхам 3: Санамсаргүй алхам хийх болон мөчлөг устгах
- Зочлогдоогүй эсийг сонгож, санамсаргүй алхам эхлүүлнэ (санамсаргүй чиглэлд хөдөлнө).
- Хэрэв алхам аль хэдийн зочилсон эсэд хүрвэл зам дахь мөчлөгийг устгана.
- Алхам зочлогдсон бүсэд холбогдсон үед, зам дээрх бүх эсүүдийг зочилсон гэж тэмдэглэнэ.
Алхам 4: Бүх эсүүд зочлогдсон болтол давтана:
- Зочлогдоогүй эсүүдийг үргэлжлүүлэн сонгож, санамсаргүй алхмуудыг хийсээр бүх эсүүд лабиринтын хэсэг болох хүртэл үргэлжлүүлнэ.