Основы поиска в глубину

Question

Я пытаюсь улучшить свой текущий алгоритм для задачи 8 Квинс, и это первый раз, когда я действительно имею дело с разработкой алгоритмов / алгоритмов. Я хочу реализовать поиск в глубину в сочетании с перестановкой различных значений Y, описанных здесь: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

Я реализовал перестановочную часть, чтобы решить эту проблему, но у меня возникли небольшие проблемы, когда я сосредоточился на поиске в глубину. Он описывается как способ обхода дерева / графа, но генерирует ли он граф дерева? Кажется, единственный способ сделать этот метод более эффективным только в том случае, если поиск в глубину генерирует древовидную структуру, которую необходимо пройти, путем реализации некоторой логики для генерации только определенных частей дерева.

По сути, мне нужно было бы создать алгоритм, который генерирует сокращенное дерево лексиграфических перестановок. Я знаю, как реализовать логику сокращения, но я просто не уверен, как связать ее с генератором перестановок, так как я использовал next_permutation.

Есть ли какие-либо ресурсы, которые могли бы помочь мне с основами глубинных поисков или создания лексикографических перестановок в виде дерева?

Answer 1

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

В случае проблемы «Восемь королев», если вы разместите ферзя так, чтобы он мог атаковать другую королеву, вы можете прервать эту ветку; это не может привести к решению.

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

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

В более общем смысле, если вы атакуете действительно большую проблему (например, шахматы), вы можете быть удовлетворены решением, которое не является точным, поэтому вы можете прервать ветвь, которую вероятно не может привести к решению, которое вы уже нашли.

Answer 2

Книга под названием «Введение в алгоритмы» Анани Левитан содержит правильное объяснение вашего понимания.Он также предоставил решение проблемы 8 королев так, как вы ее описали.Это поможет вам наверняка.

Насколько я понимаю, для поиска одного решения вам не нужна перестановка, все, что вам нужно, это dfs.Это будет достаточно в поиске решения

Answer 3

Сам алгоритм DFS не генерирует дерево / граф. Если вы хотите построить дерево и график, то построить его так же просто, как и выполнить поиск. Если вы хотите найти только один вариант, для этого будет достаточно плоской структуры данных LIFO, такой как связанный список: при посещении нового узла добавьте его в список. Когда вы покидаете узел для возврата в поиске, отключите его.