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

Question

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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