В чем разница между поиском обратной трассировки и глубиной поиска?
Какая разница между поиском назад и глубиной поиска?
Ответ 1
Backtracking - более общий алгоритм.
Один начинается с корня (выбирая некоторый node как корень в случае графа) и исследует, насколько это возможно, вдоль каждой ветки перед обратным трассировкой.
Он использует backtracking как часть своих средств работы с деревом, но ограничивается древовидной структурой.
Backtracking, тем не менее, может использоваться для любого типа структуры, где части домена могут быть устранены - независимо от того, является ли это логическим деревом. В примере Wiki используется шахматная доска и конкретная проблема - вы можете посмотреть конкретный ход и устранить его, затем вернуться к следующему возможному ходу, устранить его и т.д.
Ответ 2
Я думаю, этот ответ к другому связанному вопросу предлагает больше информации.
Для меня разница между backtracking и DFS заключается в том, что backtracking обрабатывает неявное дерево, а DFS имеет дело с явным. Это кажется тривиальным, но это много значит. Когда поисковое пространство проблемы посещается путем обратного отслеживания, неявное дерево пересекается и обрезается посередине. Тем не менее для DFS древо/граф, с которым он имеет дело, явно сконструирован, и недопустимые случаи уже были выброшены, то есть обрезаны, до того, как будет выполнен любой поиск.
Таким образом, backtracking - это DFS для неявного дерева, тогда как DFS возвращается без обрезки.
Ответ 3
Обычно поиск по глубине - это путь итерации через фактическую структуру графика/дерева, которая ищет значение, в то время как обратное отслеживание выполняет итерацию через проблемное пространство, ища решение. Backtracking - более общий алгоритм, который не обязательно связан даже с деревьями.
Ответ 4
Я бы сказал, DFS - это особая форма обратного отслеживания; backtracking - это общая форма DFS.
Если мы распространим DFS на общие проблемы, мы можем назвать это обратным трассированием. Если мы используем backtracking для проблем, связанных с деревом/графом, мы можем назвать это DFS.
Они несут ту же идею в алгоритмическом аспекте.
Ответ 5
В поиске по глубине вы начинаете с корня дерева и затем исследуете вдоль каждой ветки, затем возвращаетесь к каждому последующему родительскому node и пересекаете его с дочерними элементами. p >
Backtracking - это обобщенный термин для начала в конце цели и постепенное перемещение назад, постепенно создавая решение.
Ответ 6
Глубина сначала является алгоритмом для перемещения или поиска дерева. См. здесь. Backtracking - гораздо более широкий термин, который используется, когда кандидат на решение формируется, а затем отбрасывается возвратом в прежнее состояние. См. здесь. Глубина первого поиска использует обратную трассировку для поиска первой ветки (кандидат на решение), и если не удалось выполнить поиск в другой ветке (-ах).
Ответ 7
Возврат обычно осуществляется как DFS плюс сокращение поиска. Вы пройдете дерево поиска по глубине, сначала построив частичные решения по пути. DFS методом грубой силы может построить все результаты поиска, даже те, которые практически не имеют смысла. Это также может быть очень неэффективно для построения всех решений (n! Или 2 ^ n). Таким образом, в действительности, как и в случае с DFS, вам также необходимо сократить частичные решения, которые не имеют смысла в контексте фактической задачи, и сосредоточиться на частичных решениях, которые могут привести к действительным оптимальным решениям. Это реальная техника возврата - вы отбрасываете частичные решения как можно раньше, делаете шаг назад и снова пытаетесь найти локальный оптимум.
Ничто не останавливается для обхода дерева пространства поиска с использованием BFS и выполнения стратегии обратного отслеживания по ходу процесса, но на практике это не имеет смысла, поскольку вам необходимо хранить состояние поиска слой за слоем в очереди, а ширина дерева экспоненциально увеличивается до высоты, поэтому мы бы очень быстро потратили много места. Вот почему деревья обычно обходятся с помощью DFS. В этом случае состояние поиска сохраняется в стеке (стек вызовов или явная структура) и не может превышать высоту дерева.
Ответ 8
По словам Дональда Кнута, это то же самое. Вот ссылка на его статью об алгоритме Dancing Links, которая используется для решения таких задач, не связанных с деревьями, как N-queens и Sudoku solver.
Ответ 9
IMO, в любом конкретном node обратного отслеживания, вы пытаетесь глубже сначала разветкиться на каждый из своих дочерних элементов, но прежде чем вы введете какой-либо из дочерних node, вам нужно "стереть" предыдущее дочернее состояние (этот шаг эквивалентен обратному ходу родительскому node). Другими словами, каждое состояние братьев и сестер не должно влиять друг на друга.
Наоборот, во время обычного алгоритма DFS вы обычно не используете это ограничение, вам не нужно стереть (назад) предыдущее состояние сиблингов, чтобы построить следующий брат node.
Ответ 10
Идея - начать с любой точки, проверить, является ли она желаемой конечной точкой, если да, то мы нашли решение, в противном случае перейдем ко всем следующим возможным позициям, а если мы не сможем пойти дальше, вернемся к предыдущей позиции и поищем другие альтернативы, отмечающие этот текущий. путь не приведет нас к решению.
Теперь backtracking и DFS - это 2 разных имени, которые даны одной и той же идее и применяются к 2 разным абстрактным типам данных
Если эта идея применяется к матричной структуре данных, мы называем ее возвращением.
Если та же идея применяется к дереву или графу, то мы называем это DFS.
Клише здесь заключается в том, что матрица может быть преобразована в граф, а граф может быть преобразован в матрицу. Итак, мы на самом деле применяем эту идею. Если на графе, то мы называем это DFS, а если на матрице, то мы называем это возвращением.
Идея в обоих алгоритмах одинакова.
Ответ 11
DFS описывает способ, которым вы хотите изучить или пересечь граф. Основное внимание уделяется концепции углубления, насколько это возможно, учитывая выбор.
Возврат, хотя обычно и осуществляется через DFS, больше фокусируется на концепции сокращения бесперспективных поисковых подпространств как можно раньше.