Почему эти алгоритмы генерации лабиринтов производят лабиринты с разными свойствами?

Question

Я просматривал статью в Википедии об алгоритмах генерации лабиринтов и обнаружил, что в статье четко говорится, что различные алгоритмы генерации лабиринтов (рандомизированный поиск по глубине, рандомизированный Крускал и т. Д.) Создают лабиринты с различными характеристиками.Это, по-видимому, говорит о том, что алгоритмы создают случайные лабиринты с различным распределением вероятностей по множеству всех лабиринтов с одним решением (охватывающие деревья на прямоугольной сетке).

Мои вопросы:

1. Это правильно? То есть, правильно ли я читаю эту статью, и является ли статья правильной?
2. Если да, то почему? Я не вижуИнтуитивно понятная причина, по которой разные алгоритмы будут давать разные распределения.

Answer 1

Ну, я думаю, совершенно очевидно, что разные алгоритмы генерируют разные лабиринты.Давайте просто поговорим о связующих деревьях сетки.Предположим, у вас есть сетка G и у вас есть два алгоритма для создания связующего дерева для сетки:

Алгоритм A:

1. Выберите любой край сетки с вероятностью 99%.горизонтальный, в противном случае вертикальный
2. Добавить ребро в лабиринт, если только его добавление не создаст цикл
3. Останов, когда каждая вершина соединена с каждой другой вершиной (завершено связующее дерево)

Алгоритм B:

1. Как алгоритм A, но с вероятностью 1% вместо 99%

«Очевидно» алгоритм A производитлабиринты с множеством горизонтальных переходов и алгоритм B лабиринты с множеством вертикальных переходов.То есть существует статистическая корреляция между количеством горизонтальных проходов в лабиринте и лабиринтом, создаваемым алгоритмом А.

Конечно, различия между алгоритмами Википедии более сложны, но принцип тот же.Алгоритмы дискретизируют пространство возможных лабиринтов для данной сетки неравномерным, структурированным способом.

LOL Я помню научную конференцию, где исследователь представил свои результаты об ее алгоритме, который сделал что-то «для графиков».Результаты были статистическими и представлены для «случайных графиков».Кто-то спросил из аудитории: «Из какого распределения случайных графиков вы рисовали графики?»Ответ: "э-э ... они были созданы нашей программой генерации графов".Duh!

Answer 2

Интересный вопрос.Здесь мой случайный 2c.

Сравнивая Prim с, скажем, DFS, последний, кажется, имеет склонность к созданию более глубоких деревьев просто из-за того, что первые «прогоны» имеют больше места для создания глубоких деревьев с меньшим количествомветви.С другой стороны, алгоритм Прима, по-видимому, создает деревья с большим количеством ветвлений из-за того, что любая открытая ветвь может быть выбрана на каждой итерации.

Один из способов задать этот вопрос - посмотреть, какова вероятность того, что каждый алгоритм создаст дерево глубины> N. Я догадываюсь, что они будут разными.Более формальный подход к доказательству этого мог бы состоять в том, чтобы назначить некоторые веса каждой части дерева и показать, что это более вероятно, будет принято или попытаться охарактеризовать пространство другим способом, но я буду волнистым и предположу, что это правильно:).Меня интересует, что заставляет вас думать, что не будет , потому что моя интуиция была противоположной.И нет, статья Wiki не дает убедительного аргумента.

РЕДАКТИРОВАТЬ

Один простой способ увидеть это, рассмотреть исходное дерево с двумя дочерними элементами с общимиз k узлов, например,

*---* ... *
 \--* ... *

Выберите случайный узел в качестве начала и конца.DFS создаст один из двух лабиринтов: либо целое дерево, либо его часть с прямым путем от начала до конца.Алгоритм Прима создаст «лабиринт» с прямым путем от начала до конца с дополнительными путями длиной 1 ... k.

Answer 3

Он не является статистическим, пока вы не запросите, чтобы каждый алгоритм давал все возможные решения.

То, что вы воспринимаете как статистический уклон, является лишь смещением в сторону предпочтительного, первого решения.

Это смещение может быть не алгоритмическим (с точки зрения теории множеств), а зависящим от реализации (например, смещение при выборе центральной точки в быстрой сортировке).

Answer 4

Да, это правильно. Вы можете создавать разные лабиринты, запуская процесс разными способами. Некоторые алгоритмы начинаются с полностью закрытой сетки и удаляют стены, чтобы создать путь через лабиринт, в то время как другие начинают с пустой сетки и добавляют стены, оставляя позади путь. Одно это может дать разные результаты.