Алгоритм створення лабіринту: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 88:
=== Алгоритм Вільсона ===
Всі перераховані вище алгоритми мають різного роду зміщення: пошук у глибину зміщен у бік довгих коридорів, тоді як алгоритми Крускала/Прима зміщені до багатої кількості коротких тупиків. З іншого боку, алгоритм Вільсона<ref>{{cite
| url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.8598&rep=rep1&type=pdf
| format = PDF
| title = Generating random spanning trees more quickly than the cover time
| first = David Bruce
| last = Wilson
| date = May 22–24, 1996
| conference = Symposium on Theory of Computing
| book-title = Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing
| publisher = ACM
| location = Philadelphia
| pages = 296–303
| isbn = 0-89791-785-5
| doi = 10.1145/237814.237880
}}</ref> генерує '' незміщену'' вибірку з [[рівномірний розподіл|дискретним рівномірним розподілом]] над усіма лабіринтами, використовуючи [[випадковий пошук]] з виключенням циклічності.
Розпочнемо алгоритм, ініціалізуючи лабіринт однією довільно вибраною клітинкою. Потім ми починаємо з нової клітини, обраної довільно, і виконуємо випадковий пошук, поки не дістанемося до клітини, яка вже знаходиться в лабіринті - однак, якщо в будь-якій точці випадковий пошук досягне свого шляху, утворюючи петлю, ми виключаємо цикл з шляху перед тим, як продовжити. Коли шлях доходить до лабіринту, ми додаємо його до лабіринту. Потім ми виконуємо інший випадковий пошук з виключенням циклічності з іншої довільної початкової клітинки, повторюючи, поки всі клітини не будуть заповнені.
| |||