Algoritmus zpětného sledování

Co je Backtracking Algorithm?

Backtracking je algoritmus, který hledá možné kombinace k vyřešení výpočetní problémy. Postupně vytváří kandidáty a odstraňuje ty, kteří nesplňují daná omezení. Tato technika je velmi užitečná v situacích, kdy musíte vybrat schůdné řešení z více možných výsledků.

Tento algoritmus je považován za lepší a efektivnější než přístup Brute Force. Na rozdíl od Bruteforce, který zkouší všechna možná řešení, se Backtracking zaměřuje na nalezení pouze jednoho konečného řešení podle daného omezení. Šetří také čas a paměť tím, že vrátí poslední krok (zpět) a po dosažení slepé uličky vyzkouší jinou možnost. Navíc se zastaví, jakmile je nalezeno platné řešení.

Backtracking je široce používaná technika, protože dokáže vyřešit složité problémy bez vyčerpávající spotřeby zdrojů. Je to užitečné zejména pro problémy, kde musí být splněna řada omezení, jako je sudoku, problém n queen a plánování. Inteligentním procházením potenciálních řešení může backtracking najít odpověď, která splní všechny podmínky. Díky tomu je neocenitelný pro úkoly, které vyžadují jak přesnost, tak efektivitu.

Jak funguje algoritmus zpětného sledování?

Algoritmy zpětného sledování jsou technikou řešení problémů, která zahrnuje nalezení platných řešení krok za krokem. Pokud omezení kroku nesplňují určité podmínky, algoritmus se vrátí k předchozímu kroku.

Poté pokračuje dalšími možnými kombinacemi, které splňují daná omezení. Protože existuje mnoho možných kombinací, vybere jednu z nejuspokojivějších možností a problém vyřeší postupně. Tato algoritmická technika je užitečná, když potřebujete vyřešit jednu nebo více možných možností. Odstoupení znamená zrušení vaší volby, kdykoli nastane situace, která nepřinese platné řešení.

Algoritmus zpětného sledování má k vyřešení problému obecně následující kroky:

Krok 1) Inicializace: Začněte s počátečním prázdným/částečným řešením.

Krok 2) Výběr: Na základě konkrétních kritérií a omezení vyberte jednu možnost pro rozšíření aktuálního řešení.

Krok 3) Průzkum: Rekurzivně řešte tím, že zvážíte vybraného kandidáta a posunete se vpřed v procesu řešení problémů.

Krok 4) Kontrola omezení: Zkontrolujte, zda aktuální dílčí řešení v každém kroku neporušuje nějaká omezení. Pokud ano, vraťte se k předchozímu kroku a vyzkoušejte jiného kandidáta.

Krok 5) Ukončení: Proces zpětného sledování se zastaví, když je buď nalezeno platné řešení, nebo jsou vyčerpány všechny kombinace.

Krok 6) Backtracking: Pokud aktuální volba nevyřeší daný problém, vrátí se do předchozího stavu. Následně zváží novou možnost řešení daného problému.

Krok 7) Opakujte: Pokračujte v těchto krocích, dokud nebude problém vyřešen nebo dokud neprozkoumáte všechny možnosti.

Rekurzivní povaha algoritmu zpětného sledování

Algoritmy zpětného sledování jsou rekurzivní povahy. To znamená, že algoritmus volá sám sebe s různými parametry, dokud nenajde řešení nebo nevyzkouší všechny možnosti:

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)

Běžné termíny související s problémy se zpětným sledováním

Zde jsou některé základní pojmy související s technikou Backtracking:

• Vektor řešení: Reprezentuje řešení jako n-tice, jako (X1, X2, …, Xn).
• Omezení: Pravidla omezující hodnoty X, implicitní a explicitní.
• Prostor řešení: Všechny platné hodnoty X splňující explicitní omezení.
• Státní vesmírný strom: Představuje prostor řešení jako strom.
• Státní prostor: Popisuje cesty ve stromu stavového prostoru.
• Problémový stav: Uzly ve vyhledávacím stromu představující dílčí řešení.
• Stavy řešení: Stavy tvořící platné n-tice řešení v S.
• Odpovědět státy: Uspokojte implicitní omezení a poskytněte požadovaná řešení.
• Nadějný uzel: Vede k požadovaným řešením a zůstává proveditelný.
• Neperspektivní uzel: Vede k neuskutečnitelným stavům, dále nezkoumané.
• Živý uzel: Vytvořeno s neprozkoumanými dětmi.
• E-Uzel: Živý uzel s probíhající generací potomků.
• Mrtvý uzel: Nevygeneruje se žádné další rozšíření všech dětí.
• Generování prvního uzlu hloubky: Jako další E-uzel použije nejnovější aktivní uzel.
• Funkce ohraničení: Maximalizuje nebo minimalizuje B(x1, x2, …, Xa) pro optimalizaci.
• Statické stromy: Formulace stromu nezávislá na instanci problému.
• Dynamické stromy: Formulace stromu se liší podle instance problému.

Kdy použít algoritmus zpětného sledování?

Techniku ​​Backtracking můžeme zvolit pro řešení složitého problému, když:

• Existuje mnoho možností: Backtracking je vhodný, pokud v každém kroku procesu řešení problému existuje mnoho možností. Tyto možnosti se mohou týkat výběru položek a tahů.
• Žádná jasná nejlepší volba: Pokud není dostatek informací pro určení nejlepší volby mezi dostupnými možnostmi, lze použít algoritmus Backtracking.
• Rozhodnutí vede k dalším možnostem: Můžete si vybrat technika zpětného sledování k systematickému přezkoumání voleb.
• Je třeba prozkoumat všechna možná řešení: Backtracking systematicky zkoumá všechna řešení pomocí řady rozhodnutí postavených na sobě.

Typy problémů se zpětným sledováním

V algoritmech zpětného sledování existují tři typy problémů: rozhodovací problémy, optimalizační problémy a problémy s výčtem. Pojďme se o nich dozvědět níže.

1. Problém s rozhodováním: U tohoto typu problému je cílem zjistit, zda existuje proveditelné řešení. Kontrolujeme odpovědi „ano“ a „ne“. Například problém n-královen. Je to rozhodovací problém, který zkoumá pravděpodobnost umístění n dam na n × n šachovnici, aniž by se navzájem napadaly.
2. Problém s optimalizací: V optimalizačních problémech je cílem najít nejlepší možné řešení mezi mnoha možnostmi. To může zahrnovat stanovení maximální a minimální hodnoty určité funkce nebo proměnné. Vezměme si například problém batohu, kde je cílem maximalizovat celkovou hodnotu věcí v tašce při dodržení jejího hmotnostního limitu.
3. Problém s výčtem: Jeho cílem je najít všechna možná řešení daného problému. Uvádíme všechny platné možnosti bez vynechání. Příkladem může být generování všech možných kombinací písmen z dané sady znaků.

Aplikace Backtracking & Příklady

Backtracking má různé aplikace. Některé z nich jsou vysvětleny níže s jejich pseudokódem.

1. Sudoku Solver: Tento problém obsahuje podmřížku 3×3 s duplicitními čísly. Technika backtracking ukáže, že řešení vrací hodnotu false, což naznačuje potřebu umístění jiného čísla.

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

2. Problém N-Queen: Přístup zpětného sledování určuje, jak prezentovat královny na šachovnici N × N tak, aby se žádná z nich vzájemně neohrožovala.

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

3. Problém podmnožiny součtu: Používá se k nalezení podmnožiny čísel z dané množiny, která dává dohromady konkrétní cílový součet.

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)

4. Problém hamiltonovského cyklu: Backtracking lze použít k nalezení uzavřené prohlídky v grafu, která navštíví každý vrchol právě jednou.
5. Problém krysy v bludišti: Technika backtracking se používá k nalezení cesty krysy od výchozího bodu bludiště k východu.

Výhody a nevýhody algoritmu Backtracking

Výhody algoritmu Backtracking

Techniky backtracking se používají k řešení složitých problémů. Má mnoho výhod jako:

• Technika backtracking je účinná pro zvládnutí omezení.
• Tato metoda je vhodná pro řešení optimalizačních problémů.
• Tato technika funguje na různé typy problémů.
• Tento postup může pomoci prozkoumat všechna možná řešení.
• Protože se vrací zpět, šetří více paměti než technika Bruteforce.

Nevýhody algoritmu Backtracking

Techniky zpětného sledování mají také určitá omezení, například časovou složitost. Tato technika má následující nevýhody:

• Zaručené řešení neexistuje.
• Je pomalejší kvůli mnoha kombinacím.
• Má vysokou časovou náročnost kvůli mnoha možnostem.
• Není vhodný pro omezení v reálném čase, protože nalezení nejlepšího řešení může trvat dlouho.
• Účinnost závisí na úrovni složitosti problému.

Rozdíl mezi backtrackingem a rekurzí

Závěr

Backtracking je užitečná algoritmická strategie pro řešení složitých problémů systematickým zkoumáním proveditelných řešení a v případě potřeby zpětným sledováním. Můžeme očekávat, že techniky zpětného sledování se posílí se zlepšením výpočetního výkonu a účinnosti algoritmů. Tyto pokroky jim umožní efektivně řešit větší a složitější problémy.

Modely strojového učení navíc mohou vést zpětná rozhodnutí na základě dříve naučených vzorců.

Všechny tyto technologické inovace způsobí revoluci v algoritmech zpětného sledování a udělají z nich výkonný a všestranný nástroj pro řešení komplikovaných problémů v různých oblastech.