Случайно-первый поиск?

Два наиболее распространенных способа перемещения графика: поиск в ширину и поиск по глубине. Оба этих алгоритма поиска следуют общему шаблону:

Создайте рабочий список W, засеянный стартом node s.
Пока рабочий список не пуст:
- Удалить первый элемент рабочего списка; назовите его v.
- Если v не посещается:
  - Отметить v как посетил.
  - Для каждого node u, непосредственно связанного с v, добавьте u в W.

В первом поиске поиск рабочего списка W реализуется как очередь FIFO, в то время как при поиске по глубине a стек LIFO. Если W является приоритетной очередью, вы получаете единообразный поиск.

А назад я спросил вопрос о структуре данных для выбора случайных элементов из пакета. Если вы реализуете вышеупомянутый рабочий список W, используя этот случайный мешок, вы получаете алгоритм "случайного первого поиска", который случайным образом исследует узлы в графе, начиная с начального node.

Мой вопрос таков: существуют ли какие-либо известные алгоритмы, использующие этот тип поиска? То есть существуют ли алгоритмы, которые работают путем создания случайного связующего дерева графика таким образом?

Ответ 1

Автоматическая генерация головоломок - это приложение, для которого поиск в случайном порядке является полезной стратегией.

Предположим, вы хотите создать экземпляр комбинаторной головоломки, например Sudoku. Один из подходов - генерировать случайный, полностью разрешенный экземпляр, а затем удалять номера, пока существует уникальное решение. Как вы создаете этот случайный решаемый экземпляр в первую очередь? Вы начинаете с пустой сетки и применяете алгоритм случайного первого решения. Фактически, довольно просто использовать один и тот же код для генерации и решения, переключаясь между случайными и первыми стратегиями для выбора следующего числа, чтобы попробовать.

Это именно то, что мы сделали при написании игры Nintendo DS Zendoku, и я написал подробную статью о нашем подходе.

См. также этот ответ, в котором обсуждается генерация лабиринта с использованием рандомизированного алгоритм Prim.

Ответ 2

Это точно реализация наилучшего первого поиска при случайной эвристике.

Ответ 3

Я не знаю, есть ли имя для конкретного алгоритма, который вы описываете. Это похоже на имитированный отжиг. В теории оптимизации существует также понятие случайного поиска но оно полагается на функцию оценки, в то время как то, что вы описываете, не кажется, Там также этот Бакалавриат The Brodeur and Childs, который имеет хорошее резюме случайных алгоритмов для поиска графа, включая обсуждение того, когда их можно было использовать.

Ответ 4

Похоже, вы пытаетесь найти баланс между BFS и DFS. Это происходит в игровом программировании, где обрезка используется, чтобы сузить ширину, чтобы больше циклов можно было потратить на глубину. Некоторые примеры - это итеративная углубляющаяся глубина первого поиска и лучший первый поиск. Отправную точку можно найти здесь: http://en.wikipedia.org/wiki/Alpha-beta_pruning#Other_algorithms

Ответ 5

Отъезд A*. Вы можете настроить свою эвристическую функцию на то, что подойдет вашим данным лучше всего - вроде как ответ moooeeeep, но с чуть более подробной информацией и ссылкой на wikipedia. Если вам нужна эвристика, в которой есть случайность, тогда вы можете написать ее.

Обычно графики имеют для них какую-то структуру, и имеет смысл искать их структурированным способом (если вы ищете путь, тогда имеет смысл искать node, который связан с другим node, вы уже искали, а не случайный node, который может быть отключен.) В большинстве случаев я запускаю эти алгоритмы на ациклических графах /DAG или деревьях (подключает DAG). Если у меня действительно нет логической структуры в моих данных, я обычно не пытаюсь сделать из него график, а затем применить к нему теорию графов. Я думаю, это зависит от того, насколько вы производите случай.

Удачи!