Алгоритъм за обратно проследяване

Какво е алгоритъм за обратно проследяване?

Backtracking е алгоритъм, който търси възможни комбинации за решаване изчислителни проблеми. Той постепенно изгражда кандидати и премахва тези, които не отговарят на зададените ограничения. Тази техника е много полезна в ситуации, в които трябва да изберете осъществимо решение сред множество възможни резултати.

Този алгоритъм се счита за по-добър и по-ефективен от подхода Brute Force. За разлика от Bruteforce, който изпробва всички възможни решения, Backtracking се фокусира върху намирането само на едно окончателно решение според дадените ограничения. Освен това спестява време и памет, като отменя последната стъпка (backtrack) и опитва друга опция след достигане на задънена улица. Освен това спира веднага щом бъде намерено валидно решение.

Обратното проследяване е широко използвана техника, тъй като може да решава сложни проблеми без изтощителна консумация на ресурси. Той е особено полезен за проблеми, при които трябва да бъдат изпълнени многобройни ограничения, като судоку, проблем с 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)

Често срещани термини, свързани с проблеми с обратно проследяване

Това са някои основни термини, свързани с техниката Backtracking:

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

Кога да използвате алгоритъм за обратно проследяване?

Можем да изберем техниката Backtracking за решаване на сложен проблем, когато:

Има много възможности за избор: Обратното проследяване е подходящо, ако съществуват много опции на всяка стъпка от процеса на решаване на проблем. Тези опции могат да се отнасят до избора на елементи и ходове.
Няма ясен най-добър избор: Когато няма достатъчно информация за определяне на най-добрия избор сред наличните опции, може да се използва алгоритъм за обратно проследяване.
Решението води до повече възможности за избор: Можете да изберете техника за обратно проследяване за систематичен преглед на изборите.
Трябва да проучите всички възможни решения: Backtracking систематично изследва всички решения, като взема поредица от решения, базирани едно на друго.

Видове проблеми с обратно проследяване

Има три вида проблеми в алгоритмите за обратно проследяване: проблеми с вземане на решения, проблеми с оптимизация и проблеми с изброяване. Нека научим за тях по-долу.

Проблем с решението: При този тип проблем целта е да се определи дали съществува осъществимо решение. Проверяваме отговорите „да“ и „не“. Например проблемът с n-дами. Това е проблем с решение, който изследва вероятността да се поставят n дами на n × n шахматна дъска, без да се атакуват една друга.
Проблем с оптимизация: При проблемите с оптимизацията целта е да се намери най-доброто възможно решение сред много опции. Това може да включва определяне на максималните и минималните стойности на определена функция или променлива. Например, помислете за проблема с раницата, където целта е да се увеличи максимално общата стойност на елементите в чантата, като същевременно се спазва ограничението за тегло.
Проблем с изброяването: Целта му е да намери всички възможни решения на даден проблем. Изброяваме всяка валидна опция без никакви пропуски. Пример за това е генерирането на всички възможни буквени комбинации от даден набор от знаци.

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

Има различни приложения на Backtracking. Някои от тях са обяснени по-долу с техния псевдо код.

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.

Недостатъци на алгоритъма за обратно проследяване

Техниките за обратно проследяване също имат някои ограничения, като времева сложност. Тази техника има следните недостатъци:

Няма гарантирано решение.
По-бавно е поради много комбинации.
Има висока времева сложност поради много възможности.
Не е подходящ за ограничения в реално време, тъй като намирането на най-доброто решение може да отнеме много време.
Ефективността зависи от степента на сложност на проблема.

Разлика между обратно проследяване и рекурсия

Рекурсия	връщане назад
Извиква се до достигане на основния случай.	Използва рекурсия за преглед на всички възможности, докато се намери най-добрият възможен резултат.
Подход отдолу нагоре.	Подход отгоре надолу.
Нито една стойност не се отхвърля.	Нежизнеспособните решения се отхвърлят.

Заключение

Обратното проследяване е полезна алгоритмична стратегия за решаване на сложни проблеми чрез систематично изследване на осъществими решения и обратно проследяване, когато е необходимо. Можем да очакваме техниките за обратно проследяване да се подобрят с подобрения в изчислителната мощност и ефективността на алгоритмите. Тези подобрения ще им позволят да се справят ефективно с по-големи и по-сложни проблеми.

Освен това моделите за машинно обучение могат да ръководят решенията за обратно проследяване въз основа на предварително научени модели.

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