Блог

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

Мои вопросы:

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

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

Алгоритм A:

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

Алгоритм B:

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

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

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

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

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

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

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

Редактировать

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

 *---* ... *
 --* ... *
  

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

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

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

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

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