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

Question

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Удачи!

Answer 5

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