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

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

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

Цей алгоритм вважається кращим і ефективнішим, ніж підхід Brute Force. На відміну від Bruteforce, який пробує всі можливі рішення, Backtracking зосереджується на пошуку лише одного остаточного рішення відповідно до обмеження. Це також економить час і пам’ять, скасовуючи останній крок (зворотний шлях) і пробуючи інший варіант після досягнення тупика. Крім того, він зупиняється, щойно знайдено правильне рішення.

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

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

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

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

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

Крок 1) Ініціалізація: Почніть з початкового порожнього/часткового рішення.

Крок 2) Вибір: на основі конкретних критеріїв і обмежень виберіть один варіант для розширення поточного рішення.

Крок 3) Розвідка: рекурсивне розв’язання, розглядаючи обраного кандидата та просуваючись у процесі вирішення проблеми.

Крок 4) Перевірка обмежень: Перевірте, чи поточне часткове рішення порушує будь-які обмеження на кожному кроці. Якщо так, поверніться до попереднього кроку та спробуйте інший кандидат.

Крок 5) Припинення: процес зворотного відстеження зупиняється, коли знайдено дійсне рішення або вичерпано всі комбінації.

Крок 6) Повернення назад: Якщо поточна опція не вирішує задану проблему, вона повертається до попереднього стану. Потім він розглядає новий варіант вирішення даної проблеми.

Крок 7) Повторіть: продовжуйте виконувати ці кроки, доки проблему не буде вирішено або не досліджено всі варіанти.

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

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

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Загальні терміни, пов’язані з проблемами повернення назад

Ось кілька основних термінів, пов’язаних із технікою зворотного відстеження:

Вектор рішення: Представляє рішення у вигляді n-кортежів, наприклад (X1, X2, …, Xn).
Обмеження: правила, що обмежують значення X, неявні та явні.
Простір рішення: усі дійсні значення X, що задовольняють явні обмеження.
Дерево державного простору: представляє простір рішень у вигляді дерева.
Державний простір: Описує шляхи в дереві простору станів.
Стан проблеми: вузли в дереві пошуку, що представляють часткові рішення.
Стани рішення: Стани, що утворюють дійсні кортежі рішень у S.
Відповідь Держави: Задовольняти неявні обмеження та отримувати бажані рішення.
Перспективний вузол: Приводить до бажаних рішень і залишається здійсненним.
Неперспективний вузол: Веде до нездійсненних станів, які далі не досліджуються.
Живий вузол: створено за допомогою невивчених дітей.
E-Node: Живий вузол із постійним дочірнім поколінням.
Мертвий вузол: Подальше розширення всіх дочірніх елементів не створено.
Генерація першого вузла глибини: Використовує останній активний вузол як наступний E-вузол.
Обмежувальна функція: максимізує або мінімізує B(x1, x2, …, Xa) для оптимізації.
Статичні дерева: Формулювання дерева незалежно від примірника проблеми.
Динамічні дерева: Формулювання дерева залежить від прикладу проблеми.

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

Ми можемо вибрати техніку Backtracking для вирішення складної проблеми, коли:

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

Типи задач зворотного відстеження

Існує три типи проблем в алгоритмах зворотного відстеження: проблеми прийняття рішень, проблеми оптимізації та проблеми перерахування. Давайте дізнаємося про них нижче.

Проблема рішення: У цьому типі проблеми мета полягає в тому, щоб визначити, чи існує можливе рішення. Перевіряємо відповіді «так» і «ні». Наприклад, проблема n-ферзів. Це проблема прийняття рішення, яка досліджує ймовірність розміщення n ферзів на шахівниці n × n без нападу один на одного.
Проблема оптимізації: у задачах оптимізації мета полягає в тому, щоб знайти найкраще можливе рішення серед багатьох варіантів. Це може включати визначення максимального та мінімального значень певної функції чи змінної. Наприклад, розглянемо проблему рюкзака, де метою є максимізація загальної вартості предметів у сумці, дотримуючись обмеження ваги.
Проблема перерахування: Його мета - знайти всі можливі рішення даної проблеми. Ми перераховуємо всі дійсні варіанти без будь-яких пропусків. Прикладом може бути створення всіх можливих літерних комбінацій із заданого набору символів.

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

Існують різні програми зворотного відстеження. Деякі з них пояснюються нижче з їхнім псевдокодом.

Sudoku Solver: Ця задача містить підсітку 3×3 із повторюваними числами. Техніка зворотного відстеження покаже, що рішення повертає false, що вказує на необхідність іншого розміщення номерів.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

Проблема N-ферзя: підхід зворотного відстеження визначає, як виставити ферзів на шахівниці розміром N × N, щоб жодна з них не загрожувала одна одній.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Проблема суми підмножини: використовується для пошуку підмножини чисел із даного набору, яка в сумі дає певну цільову суму.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Проблема гамільтонового циклу: Зворотне відстеження можна застосувати, щоб знайти закритий тур у графі, який відвідує кожну вершину рівно один раз.
Щур в лабіринті Проблема: Техніка повернення назад використовується для визначення шляху щура від початкової точки лабіринту до виходу.

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

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

Техніка ретроспективи використовується для вирішення складних завдань. Він має багато переваг, таких як:

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

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

Техніка зворотного відстеження також має певні обмеження, наприклад складність у часі. Ця методика має такі недоліки:

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

Різниця між зворотним відстеженням і рекурсією

Рекурсія	Зворотний трек
Викликає себе, доки не буде досягнуто базового випадку.	Використовує рекурсію для перегляду всіх можливостей, поки не буде знайдено найкращий можливий результат.
Підхід «знизу вверх».	Підхід зверху вниз.
Жодне значення не відкидається.	Нежиттєздатні рішення відкидаються.

Висновок

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

Крім того, моделі машинного навчання можуть керувати рішеннями про відстеження на основі попередньо вивчених шаблонів.

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