Алгоритмические структуры данных: алгоритмы поиска с возвратом

алгоритм

1. Что такое алгоритм обратного пути?

1.1 Мысль

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

Алгоритм поиска с возвратом обычно реализуется простейшим рекурсивным методом, после многократного повторения вышеперечисленных шагов могут возникнуть две ситуации:

  1. найти возможный правильный ответ
  2. Не удалось выполнить все возможные пошаговые действия. На этот вопрос нет ответа.

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

1.2 Решения

Решение проблемы с возвратом на самом деле представляет собой процесс обхода дерева решений. Вам нужно подумать о 3 вопросах.

  1. Путь: то есть сделанный выбор.
  2. Список выбора: это выбор, который вы можете сделать в настоящее время.
  3. Конечное условие: то есть условие, которое достигает нижней части дерева решений и больше не может делать выбор (условие ограничения/превышает ли оно границу целевой функции).

2. Шаблон кода

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择 // 前序遍历位置
        // 进入下一层决策树（explore）
        backtrack(路径, 选择列表) // 中序遍历位置
        撤销选择 // 后序遍历位置：回退上一节点

В основе этого лежит рекурсия в цикле for. "Сделать выбор" перед рекурсивным вызовом и "отменить выбор" после рекурсивного вызова. Подобно обходу бинарного дерева, ключевым моментом является выполнение некоторых операций в положение обхода до заказа и обхода после заказа.

3. Анализ реального боя

3.1,проблема полной перестановки

Дана последовательность чисел без повторов, вернуть все возможные ее перестановки.

Пример:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Код:

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(new ArrayList<>(), nums);
        return result;
    }

    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素
    // 结束条件：nums 中的元素全都在 track 中出现
    private void backtrack(List<Integer> track, int [] nums){
        if (track.size() == nums.length) {
            // 满足基本条件
            result.add(new ArrayList<>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            // 排除不合法的选择
            if (track.contains(nums[i])) {
                continue;
            }
            // 做选择
            track.add(nums[i]);
            // 进入下一层决策树
            backtrack(track, nums);
            // 撤销选择
            track.remove(track.size() - 1);
        }
    }
}

3.2,Проблема N ферзей

В коде используются триboolean[]Массив для отслеживания позиции ферзя, текущего столбца и двух диагональных позиций (сверху слева вниз справа и сверху справа вниз слева).

  • boolean[n] colsОтслеживание позиций ферзя столбца
  • boolean[2*n] upleftОтслеживание левой диагональной позиции ферзя
  • boolean[2*n] uprightОтслеживание позиции ферзя по правой диагонали

Пусть координатное положение текущего ферзя на шахматной доске равноA (row, col), вboolean[2*n] upleftиндекс черезint iUpleft = col - row + nоценка выражения,boolean[2*n] uprightиндекс черезint iUpright = col + rowОценка выражения. После расчета будет найдено

  • а такжеAЗначения на той же левой диагоналиiUpleftтакой же
  • а такжеAЗначения на той же правой диагоналиiUprightтакой же

class Solution {
    List<List<String>> result = new ArrayList<>();
    boolean[] upleft;
    boolean[] upright;
    boolean[] cols;
    int n;
    public List<List<String>> solveNQueens(int n) {
        this.upleft = new boolean[2 * n];
        this.upright = new boolean[2 * n];
        this.cols = new boolean[n];
        this.n = n;
        backtrack(new ArrayList<String>(), 0);
        return result;
    }

    // 路径：board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表：第 row 行的所有列都是放置皇后的选择
    // 结束条件：row = n
    private void backtrack(List<String> board, int row){
        if (row == n) {
            // 满足结束条件
            result.add(new ArrayList<String>(board));
            return;
        }
        for (int col = 0; col < n; col++){
            // 左对角线
            int iUpleft = col - row + n;
            // 右对角线
            int iUpright = col + row;
            // 校验
            if (isValid(col, iUpleft, iUpright)) {
                // 若两个对角线或当前列已经有过皇后，则不满足条件，进行剪枝操作
                continue;
            }
            // 选择
            choose(board, col, iUpleft, iUpright);
            // 进入下一层决策树
            backtrack(board, row + 1);
            // 撤销选择
            unchoose(board, col, iUpleft, iUpright);
        }
    }

    // 校验
    // 棋盘上当前皇后的坐标：A (row, col)
    // 通过 col - row + n 表达式计算，与 A 在同一左对角线的值相同，即 iUpleft 相同
    // 通过 col + row 表达式计算，与 A 在同一右对角线的值相同，即 iUpright 相同
    private boolean isValid(int col, int iUpleft, int iUpright) {
        return cols[col] || upleft[iUpleft] || upright[iUpright];
    }

    // 选择
    private void choose(List<String> board, int col, int iUpleft, int iUpright) {
        // 当前行
        char[] currRow = new char[n];
        // 初始化为 .
        Arrays.fill(currRow, '.');
        // 第 col 列，放置皇后，即数组 currRow 第 col 位置，设为 Q
        currRow[col] = 'Q';
        // 做选择
        board.add(new String(currRow));
        cols[col] = true;
        upleft[iUpleft] = true;
        upright[iUpright] = true;
    }

    // 撤销选择
    private void unchoose(List<String> board, int col, int iUpleft, int iUpright) {
        board.remove(board.size() - 1);
        cols[col] = false;
        upleft[iUpleft] = false;
        upright[iUpright] = false;
    }
}

4. Резюме

Алгоритм поиска с возвратом представляет собой задачу обхода нескольких деревьев.Ключ состоит в том, чтобы выполнять некоторые операции в позиции обхода в предварительном порядке и обходе в обратном порядке, а также применять функции сокращения, такие как ограничения и целевые функции, для реализации сокращения. Схема алгоритма следующая:

def backtrack(路径, 选择列表):
    for 选择 in 选择列表:
        做选择 // 前序遍历位置
        // 进入下一层决策树
        backtrack(路径, 选择列表) // 中序遍历位置
        撤销选择 // 后序遍历位置：回退上一节点

Напишитеbacktrackметоде необходимо поддерживать пройденный «путь» и «список выбора», который можно сделать в данный момент; при срабатывании «конечного условия» «путь» записывается в набор результатов.

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择 // 前序遍历位置
        // 进入下一层决策树
        backtrack(路径, 选择列表) // 中序遍历位置
        撤销选择 // 后序遍历位置：回退上一节点
Категории