Блог

Я видел много сообщений об объяснениях обратного отслеживания в SO, но часть, которая меня все еще смущает, заключается в том, когда я на самом деле использую шаблон обратного отслеживания (выбрать-исследовать-отменить выбор) в отличие от обычного мышления DFS при решении проблем? Я понимаю, что оба они по сути являются обратным отслеживанием, но с точки зрения решения проблем традиционный подход DFS кажется намного более интуитивным, когда вы видите проблему такого рода. Но я хотел знать, когда ваш разум должен перейти «выбрать-исследовать-отменить выбор».

Например: если вы хотите напечатать все пути от корня к листу, простой подход к решению проблем DFS имеет большой смысл, тогда как при печати перестановок строки мы используем стратегию «выбрать-исследовать-отменить выбор». Мне трудно классифицировать проблемы по этим 2 сегментам. (Категоризация — это текущая стратегия, которую я использую, чтобы заставить мой разум думать в определенном направлении. Если есть какая-либо другая стратегия для решения, любой желающий может поделиться.)

Вот шаблон, на который я ссылаюсь:

 function dfs(node, state):
    if state is a solution:
        report(state) # e.g. add state to final result list
        return

    for child in children:
        if child is a part of a potential solution:
            state.add(child) # make move
            dfs(child, state)
            state.remove(child) # backtrack
  

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

Могут быть и другие разные подходы к обратному отслеживанию, но это больше зависит от эвристики. Если вы посмотрите на графовые алгоритмы (например, алгоритмы семейства «A-star»), вы увидите множество стилей алгоритмов обратного отслеживания, которые отличаются от DFS. Разница в том, на какие эвристики они полагаются, и порядок поиска: точно так же, как с небольшими изменениями, вы можете получить BFS вместо DFS.

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