Поиск в деревьях графиков с помощью алгоритмов Глубина / Ширина вначале / A *

Question

У меня есть пара вопросов о поиске в графиках / деревьях:

Предположим, у меня пустая шахматная доска, и я хочу переместить пешку из точки А в В.

A. При использовании поиска по глубине или по ширине мы должны использовать открытые и закрытые списки? Это список, в котором есть все элементы, которые нужно проверить, и другие со всеми другими элементами, которые уже были проверены? Возможно ли это сделать даже без этих списков? А как насчет A *, это нужно?

B. При использовании списков, после того как вы нашли решение, как вы можете получить последовательность состояний от A до B? Я предполагаю, что когда у вас есть элементы в открытом и закрытом списке, вместо того, чтобы просто иметь (x, y) состояния, у вас есть «расширенное состояние», сформированное с помощью (x, y, parent_of_this_node)?

C. Состояние A имеет 4 возможных хода (вправо, влево, вверх, вниз). Если я сделаю первый шаг влево, должен ли он в следующем состоянии вернуться в исходное состояние? Это «правильный» ход? Если нет, то должен ли я каждый раз пересекать дерево поиска, чтобы проверить, в каких штатах я был?

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

E. Есть ли разница между деревьями поиска и графиками? Это просто разные взгляды на одно и то же?

Answer 1

A. При использовании глубины сначала поиск или в ширину первый поиск мы должны использовать открытый а закрытые списки?

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

С BFS вам нужно поддерживать открытый список (иногда называемый fringe). В противном случае алгоритм просто не может работать. Когда вы дополнительно поддерживаете закрытый список, вы (опять же) сможете обнаружить / избежать циклов. С BFS дополнительное пространство для закрытого списка может быть не таким уж плохим, так как вы все равно должны поддерживать край. Отношение между размером полосы и размером закрытого списка сильно зависит от структуры пространства поиска, поэтому это необходимо рассмотреть здесь. Например. для коэффициента ветвления, равного 2, оба списка имеют одинаковый размер, и эффект от наличия закрытого списка не выглядит очень плохим по сравнению с его преимуществами.

А как насчет А *, нужно ли это?

A *, поскольку его можно рассматривать как некоторый специальный (информированный) тип BFS, нуждается в открытом списке. Пропуск закрытого списка является более деликатным, чем с BFS; Также принимается решение об обновлении расходов внутри закрытого списка. В зависимости от этих решений алгоритм может перестать быть оптимальным и / или полным в зависимости от типа используемой эвристики и т. Д. Я не буду вдаваться в подробности.

B.

Да, закрытый список должен образовывать какое-то обратное дерево (указатели идут к корневому узлу), чтобы вы могли извлечь путь решения. Для этого вам обычно нужен закрытый список. Для DFS ваш текущий стек - это точно путь решения (здесь нет необходимости в закрытом списке). Также обратите внимание, что иногда вас интересует не путь, а только решение или его существование.

С.

Прочитайте предыдущие ответы и найдите части, в которых говорится об обнаружении циклов.

D.

Чтобы избежать циклов с закрытым списком: не расширяйте узлы, которые уже находятся внутри закрытого списка. Примечание: с учетом стоимости пути (помните A *) все может стать сложнее.

E. Есть ли разница между поиск деревьев и графиков?

Вы могли бы рассматривать поиски, которые поддерживают закрытый список, чтобы избежать циклов, как поиск в графе, и поиск без одного поиска в дереве.

Answer 2

A) Можно избежать открытых / закрытых списков - вы можете попробовать все возможные пути, но это займет ОЧЕНЬ много времени.

B) Как только вы достигли цели, вы используете информацию parent_of_this_node, чтобы «идти назад» от цели. Начните с цели, возьмите ее родителя, возьмите родителя родителя и т. Д., Пока не достигнете начала.

C) Я думаю, что это не имеет значения - ни в коем случае шаг, который вы описываете, не приведет к более короткому пути (если ваши шаги не имеют отрицательного веса, в этом случае вы не можете использовать Dijkstra / A *). В моем коде A * я проверяю этот случай и игнорирую его, но делаю все, что проще всего для кодирования.

D) Это зависит - я считаю, что Дейкстра никогда не сможет снова открыть один и тот же узел (кто-то может исправить меня?). * Определенно может вернуться к узлу - если вы найдете более короткий путь к тому же узлу, вы сохраните этот путь, в противном случае вы его игнорируете.

E) Не уверен, я никогда ничего не делал специально для деревьев.

Здесь есть хорошее введение в A *: http://theory.stanford.edu/~amitp/GameProgramming/ в нем много деталей о том, как реализовать открытый набор, выбрать эвристику и т. д.

Answer 3

A. Открытые и закрытые списки являются общими деталями реализации, а не частью алгоритма как такового. Обычно поиск в дереве по глубине выполняется без какого-либо из них, например, каноническим способом является рекурсивный обход дерева.

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

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

D. Да, список посещенных состояний - это то, что вы называете закрытым списком. Вы также хотите проверить открытый список, чтобы убедиться, что вы не планируете проверять данное состояние дважды. Вам не нужно искать любое дерево как таковое, поскольку вы обычно храните эти вещи в линейных структурах. Алгоритм в целом ищет дерево (или график) и генерирует дерево (из узлов, представляющих пространство состояний), но вы явно не просматриваете древовидную структуру в любой точке алгоритма.

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