logo

TechCodeview

Алгоритм зворотного відстеження

Алгоритми зворотного відстеження це як стратегії вирішення проблем, які допомагають досліджувати різні варіанти, щоб знайти найкраще рішення. Вони працюють, випробовуючи різні шляхи, і якщо один не працює, вони повертаються назад і пробують інший, доки не знайдуть правильний. Це схоже на вирішення головоломки, випробовуючи різні деталі, поки вони ідеально не підійдуть один до одного.

Відстеження назад

Зміст



Що таке алгоритм зворотного відстеження?

Відстеження назад це алгоритмічна техніка розв’язування задач, яка передбачає поступове знаходження рішення шляхом спроб різні варіанти і скасування їх, якщо вони ведуть до a мертвий кінець .

Він зазвичай використовується в ситуаціях, коли вам потрібно дослідити кілька можливостей для вирішення проблеми, як-от пошук шляху в лабіринті або вирішення головоломок, як-от Судоку . Коли досягається глухий кут, алгоритм повертається до попередньої точки прийняття рішення та досліджує інший шлях, поки не буде знайдено рішення або не вичерпано всі можливості.

Як працює алгоритм зворотного відстеження?

А алгоритм зворотного відстеження працює шляхом рекурсивного дослідження всіх можливих рішень проблеми. Він починається з вибору початкового рішення, а потім вивчає всі можливі розширення цього рішення. Якщо розширення призводить до рішення, алгоритм повертає це рішення. Якщо розширення не призводить до рішення, алгоритм повертається до попереднього рішення та намагається застосувати інше розширення.

Нижче наведено загальний опис того, як працює алгоритм зворотного відстеження:

  1. Виберіть вихідне рішення.
  2. Вивчіть усі можливі розширення поточного рішення.
  3. Якщо розширення призводить до рішення, поверніть це рішення.
  4. Якщо розширення не приводить до рішення, поверніться до попереднього рішення та спробуйте інше розширення.
  5. Повторюйте кроки 2-4, доки не дослідите всі можливі рішення.

Приклад алгоритму зворотного відстеження

приклад: Пошук найкоротшого шляху через лабіринт

введення: Лабіринт, представлений у вигляді двовимірного масиву, де 0 являє собою відкритий простір і 1 являє собою стіну.

Алгоритм:

  1. Почніть із початкової точки.
  2. Для кожного з чотирьох можливих напрямків (вгору, вниз, вліво, вправо) спробуйте рухатися в цьому напрямку.
  3. Якщо рух у цьому напрямку веде до кінцевої точки, поверніть пройдений шлях.
  4. Якщо рух у цьому напрямку не веде до кінцевої точки, поверніться до попередньої позиції та спробуйте інший напрямок.
  5. Повторюйте кроки 2-4, доки не буде досягнуто кінцевої точки або не будуть досліджені всі можливі шляхи.

Коли використовувати алгоритм зворотного відстеження?

Алгоритми зворотного відстеження найкраще використовувати для вирішення проблем, які мають такі характеристики:

  • Існує кілька можливих рішень проблеми.
  • Проблему можна розбити на менші підпроблеми.
  • Підзадачі можна вирішувати самостійно.

Застосування алгоритму зворотного відстеження

Алгоритми зворотного відстеження використовуються в широкому спектрі програм, зокрема:

  • Розгадування головоломок (наприклад, судоку, кросвордів)
  • Пошук найкоротшого шляху через лабіринт
  • Проблеми планування
  • Проблеми розподілу ресурсів
  • Проблеми оптимізації мережі

Основи алгоритму зворотного відстеження:

  • Різниця між технікою Backtracking і Branch-N-Bound
  • Яка різниця між зворотним відстеженням і рекурсією?

Стандартні проблеми з алгоритмом зворотного відстеження:

  • Проблема лицарського туру
  • Щур в лабіринті
  • N Королева Проблема | Відкат-3
  • Проблема суми підмножини
  • м Розмальовка Задача
  • Гамільтонів цикл
  • Судоку | Відкат-7
  • Пазл-магніт
  • Видаліть недійсні дужки
  • Підхід зворотного відстеження для генерації n бітових кодів Грея
  • Напишіть програму для друку всіх перестановок заданого рядка

Прості проблеми з алгоритмом зворотного відстеження:

  • Зворотний пошук для пошуку всіх підмножин
  • Перевірте, чи заданий рядок є сумарним рядком
  • Порахувати всі можливі шляхи між двома вершинами
  • Знайти всі різні підмножини заданої множини
  • Знайти, чи існує шлях від джерела довжиною більше k
  • Надрукувати всі шляхи від даного джерела до пункту призначення
  • Надрукуйте всі можливі рядки, які можна створити, поставивши пробіли

Середні проблеми з алгоритмом зворотного відстеження:

  • Воєнний буксир
  • 8 проблема з королевою
  • Комбінаційна сума
  • Алгоритм Варнсдорфа для задачі туру Найта
  • Знайдіть шляхи від кутової клітини до середньої клітини в лабіринті
  • Знайдіть максимальну можливу кількість, виконавши щонайбільше K обмінів
  • Щур у лабіринті з дозволеними кількома кроками або стрибками
  • N ферзя в O(n) просторі

Складні проблеми з алгоритмом зворотного відстеження:

  • Power Set у лексикографічному порядку
  • Проблема розриву слів за допомогою зворотного відстеження
  • Розбиття множини на K підмножин з рівною сумою
  • Найдовший можливий маршрут у матриці з перешкодами
  • Знайдіть найкоротший безпечний шлях на шляху з мінами
  • Вивести всі паліндромні розділи рядка
  • Друк усіх рішень у задачі N-Queen
  • Вивести всі найдовші спільні підпослідовності в лексикографічному порядку

Швидкі посилання:

  • Вивчіть структуру даних і алгоритми | Підручник DSA
  • 20 найкращих запитань на співбесіді щодо алгоритму зворотного відстеження
  • «Відео» про зворотне відстеження