В чем разница между обратным отслеживанием и глубиной первого поиска?

Я думаю ответ к другому связанному вопросу предлагает больше понимания.

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

Итак, backtracking - это DFS для неявного дерева, в то время как DFS возвращается без обрезки.

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

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

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

Depth first-это алгоритм обхода или поиска дерева. Смотрите здесь. Возврат-это гораздо более широкий термин, который используется везде, где формируется кандидат на решение, а затем отбрасывается путем возврата в прежнее состояние. Смотрите здесь. Поиск глубины первый использует обратное отслеживание для поиска первой ветви (кандидата на решение) и, если не удалось найти другую ветвь(ы).

Я бы сказал, что DFS-это специальная форма обратного отслеживания; обратное отслеживание-это общая форма DFS.

Если мы распространим DFS на общие проблемы, мы можем назвать это обратным отслеживанием. Если мы используем возврат к проблемам, связанным с деревом/графом, мы можем назвать его DFS.

Они несут ту же идею в алгоритмическом аспекте.

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

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

Backtracking обычно реализуется как DFS plus search pruning. Вы пересекаете глубину дерева пространства поиска-сначала строите частичные решения по пути. Грубая сила DFS может построить все результаты поиска, даже те, которые практически не имеют смысла. Это также может быть очень неэффективно для построения всех решений (n! или 2^n). Поэтому на самом деле, как вы делаете DFS, вам нужно также обрезать частичные решения, которые не имеют смысла в контексте реальной задачи, и сосредоточиться на частичном решения, которые могут привести к правильным оптимальным решениям. Это и есть собственно техника отхода-вы отбрасываете частичные решения как можно раньше, делаете шаг назад и снова пытаетесь найти локальный оптимум.

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

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

теперь backtracking и DFS-это 2 разных имени, присвоенных одной и той же идее, применяемой к 2 различным абстрактным типам данных.

Если идея применяется к матричной структуре данных мы назовем это отступлением.

если та же идея применяется на дереве или графике, то мы называем его DFS.

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

идея в обоих алгоритмах одинакова.