Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процессе обнаружения решения лабиринта. Во время исследования лабиринта мы должны принять решения, включающие который путь исследовать. Когда сталкиваешься с выбором путей, мы решаем, пойти ли на север, юг, восток, или запад. Подход отслеживания в обратном порядке, чтобы найти путь через лабиринт включает рассмотрение всех возможных путей, пока мы не находим решения.
Рисунок 1 лабиринт
Отслеживание в обратном порядке включает преследование одного возможного решения, пока алгоритм не решает, что оно не является решением. Если алгоритм отслеживания в обратном порядке обнаруживает, что выбранная возможность не является решением, алгоритм "backs up" рассматривает другую возможность возможных решений. Например, мышь должна найти решение лабиринта, чтобы добраться до сыра в рисунке 1. Давайте займем место мыши в ситуации и увидем, как мы можем использовать отслеживание в обратном порядке, чтобы найти решение. Сразу, в позиции A, у нас есть выбор между севером или югом. Например, мы выберем север, но мы будем помнить, что есть другой путь, ведущий на юг, который мы не исследовали. Идя на север, мы быстро узнаем, что этот путь приводит в тупик. В этой ситуации мы должны вернуться в обратном порядке в позицию A и пойти по другому. Двигаясь на юг от позиции A в позицию B, где мы можем продолжать перемещаться на юг или исследовать путь на восток. Если мы хотим идти на восток, мы должны будем, конечно, принять много других решений. Если один из этих путей приводит к решению, наш поиск завершен. Если все пути, отклоняющиеся на восток приводят в тупики, мы должны вернуться в обратном порядке в позицию B и исследовать путь, который ведет на юг. Этот процесс гарантирует решение лабиринта, так как он рассматривает все возможные пути.
Алгоритмы «отслеживание в обратном порядке», которые используют рекурсию, управляет в основном тем же самым путем как другие рекурсивные алгоритмы. Подобный любому другому рекурсивному алгоритму, программисты разрабатывают алгоритмы отслеживания в обратном порядке вокруг base case, которые решаются без рекурсии. В примере лабиринта существует base case, когда мышь рядом с выходом лабиринта (в позиции C). В этой ситуации выбор пойти на восток очевиден, и рекурсивный поиск не нужен. Рекурсивные алгоритмы отслеживания в обратном порядке также уменьшают проблему до наименьшей подзадачи. Рекурсия, примененная в примере лабиринта, эффективно делает лабиринт меньшего размера и меньшим, пока это не достигает основного случая.
Пример: Восемь Королев