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

внешний интерфейс алгоритм

предисловие

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

❝

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

❞

Если вы не знаете, что такое алгоритм поиска с возвратом или знаете что-то, но как он реализован回溯, то эта статья может быть полезной для вас.

Затем мы представим алгоритм возврата вокруг следующих точек👇

  • источник
  • Основная мысль
  • Алгоритмическая структура
  • классический пример

Свяжитесь с 👉TianTianUp, если у вас возникнут проблемы, вы можете связаться с автором, я готов сопровождать вас, чтобы вместе изучить и обсудить проблему.

Источник алгоритма возврата

Прежде всего, мы должны понять, что такое алгоритм поиска с возвратом и каково его происхождение.

Согласно определению, данному Википедией👇

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

Общий шаг решения задач с алгоритмами возврата:

❝

1. Для заданной задачи определить пространство решений задачи, которое содержит хотя бы одно (оптимальное) решение задачи.

2. Определить структуру пространства решений, которую легко найти, чтобы ее можно было использовать回溯法Удобный поиск по всему пространству решений.

3. Поиск в пространстве решений в глубину и использование функции обрезки, чтобы избежать недопустимых поисков в процессе поиска.

❞

Объясни проще👇

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

Основная мысль

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

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

Основная мысль:

  • Начните с одного пути дерева решений. Если вы можете продвинуться вперед, вы продвинетесь. Если вы не можете продвинуться, вы отступите. Попробуйте другой путь.

Например, возьмем для объяснения задачу о восьми ферзях:

  • Первая ступенька гладкая, то есть в первом ряду ставим первую королеву.
  • На втором шаге нам нужно разместить ферзя во втором ряду, пройти и поставить ферзя в положение, соответствующее требованиям.
  • Третий шаг, то есть в третьей строке, нам нужно пройти и найти позицию, которая соответствует требованиям, если она не соответствует требованиям, нам нужно"Отменить второй шаг", то положение второго ферзя нужно изменить, а положение второго ферзя нужно изменить до тех пор, пока не будет удовлетворено положение третьего ферзя.
  • Когда вы меняете позицию второго ферзя и не можете удовлетворить позицию третьего ферзя, нам нужно"Отменить первый шаг", переставьте первую позицию ферзя, а затем выполните последующие операции по порядку.

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

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

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

Алгоритмическая структура

На самом деле, почистив определенное количество вопросов, вы обнаружите, что для этой ретроспективной идеи есть определенные процедуры, затем дается псевдокод👇

Далее мое собственное понимание. Я чувствую, что если вы последуете этому шагу, вам будет легче понять 👇

Есть 3 шага, чтобы обдумать этот тип вопроса:

  1. "дорожка": Запишите сделанный выбор.
  2. "список выбора": В общем, используйте массив для хранения выбираемых операций.
  3. "конечное условие": Вообще говоря, это конечная точка рекурсии, то есть конечная точка поиска.
result = []

function backtrack(路径, 选择列表) {
    if('满足结束条件') {
        // 这里就是对答案做更新,依据实际题目出发
        result.push(路径)
        return
    } else {
        for(let i = 0; i < 选择列表.length; i++) {
            // 对一个选择列表做相应的选择
            
            做选择
            
            backtrack(路径, 选择列表)
            
            // 既然是回溯算法,那么在一次分岔路做完选择后
            // 需要回退我们之前做的操作
            
            撤销选择
        }
    }
}

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

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

Когда эта схема неразумна, нужно ли очищать ранее отмеченную сетку? Если хорошенько подумать, то это очень разумно.Когда текущий план не сработает, мы сделаем этот"шаг отменить".

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

как написать обратную связь

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

  • Сначала нарисуйте дерево рекурсии и найдите переменную состояния (это можно понимать как параметр функции поиска с возвратом).
  • Определение рекурсивного выхода обычно основано на конкретных условиях темы.
  • Найдите список вариантов (обычно связанных с параметрами функции).
  • Обрезка, в некоторых случаях может быть уместна обрезка.
  • Делайте выбор, вызывайте рекурсивно и переходите на следующий уровень.
  • Отменить выбор.

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

2 примера

Далее мы используем три темы в качестве примеров, чтобы увидеть, как использовать вышеупомянутые算法框架решить проблему👇

Все прописные и строчные буквы ⭐

❝

Ссылка на сайт:Все прописные и строчные буквы

❞

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

Пример:

❝

Ввод: S = "a1b2" Вывод: ["a1b2", "a1B2", "A1b2", "A1B2"]

❞
❝

Ввод: S = "3z4" Вывод: ["3z4", "3Z4"]

❞
❝

Ввод: S = "12345" Вывод: ["12345"]

❞

намекать:

❝

Длина S не превышает 12. S состоит только из цифр и букв.

❞

Источник: LeetCode Ссылка: https://leetcode-cn.com/problems/letter-case-permutation Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

Ну а на этот вопрос можно взять картинку для примера, я воспользуюсь картинкой из интернета здесь👇

字母全排列
полный алфавит

Для цифр пропускаем сразу, для букв это не что иное, как два состояния, прописные и строчные буквы, тогда у нас следующая идея👇

  • Если мы столкнемся с числами, новые ветки не будут задействованы, поэтому мы просто ищем в обратном направлении, В этом случае нам нужно искать числа только один раз.
  • Для одной буквы нам нужно"искать 2 раза", ищите один раз строчные буквы и один раз прописные буквы.
  • Мы можем поддерживать индекс, если мы встречаем число, индекс +1, продолжаем рекурсию, если мы встречаем букву, нам нужно рекурсивно дважды, предполагая, что когда буква в нижнем регистре, мы рекурсивно один раз (индекс+1), а затем вернуть букву при откате. Преобразовать в верхний регистр и снова выполнить рекурсию.
  • Конец рекурсии: то есть до тех пор, пока не будет найдена вся строка, индекс, который мы сохранили ранее, может использоваться в качестве условного суждения в это время.

Если мы будем следовать этой линии мышления, мы сможем написать полный код для решения проблем.

код👇

回溯算法代码-1
Код алгоритма возврата-1

Код нажмите здесь ☑️

Подмножество 🐍⭐⭐

❝

Ссылка на сайт:Подмножество

❞

Учитывая набор целочисленных массивов nums без повторяющихся элементов, вернуть все возможные подмножества (множества мощности) массива.

Объяснение: Набор решений не может содержать повторяющиеся подмножества.

Пример:

❝

Ввод: числа = [1,2,3] вывод: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

❞

Источник: LeetCode Ссылка: https://leetcode-cn.com/problems/subsets Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

При решении такого рода задач, если вы не очень хорошо это понимаете, вы можете сначала нарисовать картинку Из приведенного выше вопроса мы можем нарисовать структуру, похожую на дерево, а затем посмотреть, как пройти по дереву решений, посмотреть, если его можно подрезать, и прямо Узнавать по картинкам в интернете👇

子集的递归树
рекурсивное дерево подмножеств

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

Прежде всего, мы должны организовать наше мышление 👇

  • Эта задача должна состоять в том, чтобы найти все узлы дерева!
  • Для этого дерева мы можем обойти его ветви, выбрать одну из ветвей, а затем продолжить работу вниз.Если мы не выбираем эту ветвь, выбор другой ветви - это другой случай, поэтому каждый раз, когда мы перечисляем следующее число Когда, это два варианта: выбирать или не выбирать.
  • Рассмотрите возможность использования индексного указателя для записи"узел"Состояние , т. е. номер текущего рекурсивного исследованияnums[index]
  • Условие окончания рекурсии: index === nums.length, на данный момент это означает, что все числа просматриваются, текущее подмножество добавляется к решению задачи и текущая рекурсивная ветвь завершается.
  • Каждый раз, когда вы заканчиваете ветку, то есть завершаете рекурсию, вам нужно отозвать текущую выборку, (удалить из списка), вернуться в состояние до выбора и сделать другую выборку, то есть не выбирать текущую количество, вернуться вниз и продолжить генерировать подмножества.

Согласно приведенному выше псевдокоду, мы можем в принципе решить эту проблему👇

回溯算法题解-2
Алгоритм поиска с возвратом Проблема Решение-2

Код нажмите здесь ☑️

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

Краткое изложение дополнительных тем

Ниже приведен набор хороших вопросов по алгоритму поиска с возвратом, которые я видел в Интернете.Если вы все еще ищете его, вы можете посмотреть здесь.

тип ссылка на тему
подмножество, комбинация Подмножество,Подмножество II,комбинация,объединенная сумма,Комбинированная сумма II
полный массив полный массив,Полная перестановка II,полная перестановка строк,Все прописные и строчные буквы
поиск Решить судоку,поиск слова,Королева Н,разделенный палиндром,бинарные часы

❤️ Всем спасибо

Если вы считаете этот контент полезным:

  1. Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент
  2. Обратите внимание на публичный аккаунт"Интерфейс UpUp", свяжитесь с автором, мы будем учиться и прогрессировать вместе.
  3. Если вы считаете, что это хорошо, вы также можете прочитать последние статьи TianTian (спасибо за вашу поддержку и поддержку 🌹🌹🌹):

В этой статье используетсяmdniceнабор текста

Категории