У цьому підручнику ви дізнаєтесь, що таке алгоритм зворотного відстеження. Крім того, ви знайдете приклад підходу для зворотного відстеження.
Алгоритм зворотного відстеження - це алгоритм вирішення проблем, який використовує підхід грубої сили для пошуку бажаного результату.
Підхід грубої сили випробовує всі можливі рішення та вибирає бажані / найкращі рішення.
Термін зворотне відстеження передбачає, що якщо поточне рішення не є придатним, тоді поверніться та спробуйте інші рішення. Таким чином, у цьому підході використовується рекурсія.
Цей підхід використовується для вирішення проблем, які мають кілька варіантів вирішення. Якщо ви хочете отримати оптимальне рішення, вам слід перейти до динамічного програмування.
Державне космічне дерево
Дерево просторових станів - це дерево, що представляє всі можливі стани (рішення чи нерозв’язання) задачі від кореня як початкового стану до листа як кінцевого стану.
Державне космічне дерево
Алгоритм зворотного відстеження
Backtrack (x), якщо x не є рішенням, повертає false, якщо x є новим рішенням, додайте до списку рішень backtrack (розгорніть x)
Приклад підходу для зворотного відстеження
Проблема: Ви хочете знайти всі можливі способи влаштування 2 хлопчиків та 1 дівчинки на 3 лавки. Обмеження: Дівчина не повинна знаходитися на середній лаві.
Рішення: Всього їх 3! = 6 можливостей. Ми спробуємо всі можливості та отримаємо можливі рішення. Ми рекурсивно випробовуємо всі можливості.
Усі можливості:
Усі можливості
Наступне дерево простору станів показує можливі рішення.
Дерево держав з усіма рішеннями
Програми алгоритму зворотного відстеження
- Щоб знайти всі гамільтонові шляхи, присутні на графіку.
- Для вирішення проблеми N Queen.
- Лабіринт вирішення проблеми.
- Проблема лицарського туру.
