Backtracking - Backtracking

Pro linky vyhledávací algoritmus použitý v neomezeném optimalizaci , viz ústupu hledání čáry .
Algoritmy pro vyhledávání grafů a stromů
Výpisy
související témata

Backtracking je obecný algoritmus pro hledání řešení některých výpočetních problémů , zejména problémů s omezením spokojenosti , který postupně sestavuje kandidáty na řešení a opouští kandidáta („backtracks“), jakmile zjistí, že kandidát nemůže být dokončen na platnou řešení.

Klasickým učebnicovým příkladem použití zpětného sledování je skládačka osmi královen , která vyžaduje všechna uspořádání osmi šachových královen na standardní šachovnici , aby žádná královna nezaútočila na žádnou jinou. V běžném přístupu zpětného sledování jsou částečnými kandidáty uspořádání k královen v prvních k řadách desky, vše v různých řádcích a sloupcích. Jakékoli částečné řešení, které obsahuje dvě vzájemně útočící královny, může být opuštěno.

Backtracking lze použít pouze u problémů, které připouštějí koncept „částečného kandidáta na řešení“ a relativně rychlý test, zda jej lze případně doplnit k platnému řešení. Je zbytečné například pro vyhledání dané hodnoty v neuspořádané tabulce. Je-li to možné, je zpětné sledování často mnohem rychlejší než výčet hrubou silou všech úplných kandidátů, protože může jediným kandidátem eliminovat mnoho kandidátů.

Zpětná stopa je důležitý nástroj pro řešení problémů s uspokojením omezení , jako jsou křížovky , verbální aritmetika , sudoku a mnoho dalších hádanek. Často je to nejvhodnější technika pro analýzu , problém batohu a další kombinatorické optimalizační problémy. Je také základem takzvaných logických programovacích jazyků, jako jsou Icon , Planner a Prolog .

Zpětné sledování závisí na uživatelem zadaných „ postupech černé skříňky “, které definují problém, který má být vyřešen, na povaze dílčích kandidátů a na tom, jak jsou rozšířeny na úplné kandidáty. Jedná se tedy spíše o metaheuristický než o konkrétní algoritmus - i když na rozdíl od mnoha jiných metaheuristik je zaručeno, že v omezeném čase najde všechna řešení konečného problému.

Pojem „ústupek“ vytvořil v 50. letech americký matematik DH Lehmer . Průkopnický jazyk pro zpracování řetězců SNOBOL (1962) mohl být první, kdo poskytl vestavěné obecné zařízení pro zpětné sledování.

Popis metody

Algoritmus backtracking vyjmenovává sadu dílčích kandidátů, které by v zásadě mohly být dokončeny různými způsoby, aby poskytly všechna možná řešení daného problému. Dokončení se provádí postupně, posloupností kroků rozšíření kandidáta.

Koncepčně jsou dílčí kandidáti reprezentováni jako uzly stromové struktury , potenciální vyhledávací strom. Každý částečný kandidát je rodičem kandidátů, kteří se od něj liší jedním krokem rozšíření; listy stromu jsou částečné kandidáty, které nelze dále rozšiřovat.

Algoritmus backtracking prochází tímto vyhledávacím stromem rekurzivně od kořene dolů v hloubce prvního řádu . V každém uzlu c algoritmus kontroluje, zda lze c dokončit na platné řešení. Pokud to nejde, je přeskočen ( prořezán ) celý podstrom zakořeněný vc . Jinak algoritmus (1) ověří, zda je samotné c platné řešení, a pokud ano, ohlásí to uživateli; a (2) rekurzivně vyjmenuje všechny dílčí stromy c . Dva testy a podřízené prvky každého uzlu jsou definovány postupy danými uživatelem.

Proto je skutečná vyhledávací strom , který je provázán algoritmem je jen část potenciálního stromu. Celková cena algoritmu je počet uzlů skutečného stromu vynásobený náklady na získání a zpracování každého uzlu. Tuto skutečnost je třeba vzít v úvahu při výběru potenciálního stromu vyhledávání a provádění testu prořezávání.

Pseudo kód

Aby bylo možné použít backtracking na konkrétní třídu problémů, je třeba poskytnout data P pro konkrétní instanci problému, který má být vyřešen, a šest procedurálních parametrů , root , reject , accept , first , next a output . Tyto postupy by měly brát instanční data P jako parametr a měly by dělat následující:

  1. root ( P ): vrací částečný kandidát v kořenovém adresáři stromu vyhledávání.
  2. odmítnout ( P , c ): vrátit true pouze v případě, že částečný kandidát c nestojí za dokončení.
  3. přijmout ( P , c ): vrátit true, pokud c je řešením P , a false jinak.
  4. první ( P , c ): vygeneruje první příponu kandidáta c .
  5. next ( P , s ): vygeneruje další alternativní rozšíření kandidáta po rozšíření s .
  6. výstup ( P , c ): použijte řešení c z P , podle aplikace.

Algoritmus zpětného sledování snižuje problém zpětného volání ( root ( P )), kde je zpětný záznam následující rekurzivní postup: 

procedure backtrack(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(s)
        s ← next(P, s)

Pokyny k použití

Odmítají postup by měl být funkce boolean s hodnotou , která vrací hodnotu true pouze tehdy, pokud je jisté, že není možné rozšíření c je platný řešení pro P . Pokud postup nemůže dojít k definitivnímu závěru, měl by se vrátit false . Nesprávný skutečný výsledek může způsobit, že proceduře bt chybí některá platná řešení. Tento postup může předpokládat, že odmítnout ( P , t ) vrací false pro každý předchůdce t o C do vyhledávacího stromu.

Na druhou stranu účinnost algoritmu zpětného sledování závisí na odmítnutí návratu true pro kandidáty, kteří jsou co nejblíže kořenu. Pokud reject vždy vrátí hodnotu false , algoritmus stále najde všechna řešení, ale bude ekvivalentní hledání hrubou silou.

Procedura přijmout by měla vrátit true, pokud c je úplné a platné řešení pro problémovou instanci P , a false jinak. Může předpokládat, že částečný kandidát c a všichni jeho předkové ve stromu prošli testem odmítnutí .

Obecný pseudokód výše nepředpokládá, že platná řešení jsou vždy listy potenciálního vyhledávacího stromu. Jinými slovy připouští možnost, že platné řešení pro P lze dále rozšířit tak, aby poskytlo další platná řešení.

Mezi první a další procedury jsou použity algoritmem ustupování výčet děti uzlu c stromu, to znamená, že kandidáti, které se liší od c jedním prodlužovacím kroku. Volání první ( P , c ) by měla získá první dítě C , v některých pořadí; a hovor další ( P , to ) by měl vrátit příští sourozence uzel s , v uvedeném pořadí. Obě funkce by měly vrátit charakteristického kandidáta "NULL", pokud požadované dítě neexistuje.

Společně funkce root , first a next definují sadu částečných kandidátů a potenciální vyhledávací strom. Měly by být vybrány tak, aby každé řešení P nastalo někde ve stromu a žádný dílčí kandidát se nevyskytoval vícekrát. Navíc by měli připustit účinný a efektivní predikát odmítnutí .

Varianty včasného zastavení

Výše uvedená pseudo-kód bude volat výstup pro všechny kandidáty, které jsou řešením dané instance P . Algoritmus lze upravit tak, aby se zastavil po nalezení prvního řešení nebo zadaného počtu řešení; nebo po otestování zadaného počtu částečných kandidátů nebo po strávení daného množství času CPU .

Příklady

Sudoku řešeno ústupu.

Mezi příklady, kdy lze k řešení hádanek nebo problémů použít zpětné sledování, patří:

Následuje příklad, kdy se pro problém spokojenosti s omezeními používá zpětné sledování :

Omezení spokojenosti

Problém uspokojení obecného omezení spočívá v nalezení seznamu celých čísel x = ( x [1], x [2],…, x [ n ]) , každé v nějakém rozsahu {1, 2,…, m }, které splňují některé libovolná omezení (logická funkce) F .

Pro tuto třídu problémů, instance dat P by být celá čísla m a n , a predikát F . V typickém zpětném řešení tohoto problému lze definovat částečného kandidáta jako seznam celých čísel c = ( c [1], c [2],…, c [k]) , pro libovolné k mezi 0 a n , že mají být přiřazeny k prvním k proměnným x [1], x [2],…, x [ k ] . Kořenovým kandidátem by pak byl prázdný seznam (). Mezi první a další procedury by pak byla 

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)

function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Zde délka ( c ) je počet prvků v seznamu c .

Odmítnutí hovoru ( P , c ) by se mělo vrátit true, pokud omezení F nemůže být splněno žádným seznamem celých čísel n, které začínají k prvky c . Aby zpětné sledování bylo účinné, musí existovat způsob, jak tuto situaci detekovat, alespoň u některých kandidátů c , aniž by byly vyjmenovány všechny ty m n - k n -tuple.

Například pokud F je spojení několika booleovských predikátů, F = F [1] ∧ F [2] ∧… ∧ F [ p ] a každé F [ i ] závisí pouze na malé podmnožině proměnných x [1 ],…, X [ n ] , pak by procedura odmítnutí mohla jednoduše zkontrolovat výrazy F [ i ], které závisí pouze na proměnných x [1],…, x [ k ] , a vrátit true, pokud některý z těchto výrazů vrátí false . Ve skutečnosti je třeba odmítnout pouze kontrolu těch výrazů, které závisí na x [ k ], protože výrazy, které závisí pouze na x [1],…, x [ k - 1], budou testovány dále ve stromu vyhledávání.

Za předpokladu, že odmítnutí je implementováno výše, pak akceptujte ( P , c ) pouze kontrolu, zda je c úplné, tj. Zda má n prvků.

Obecně je lepší uspořádat seznam proměnných tak, aby začínal těmi nejkritičtějšími (tj. Těmi, které mají nejmenší možnosti hodnot, nebo které mají větší dopad na následné volby).

Dalo by se také umožnit další funkci vybrat si, která proměnná by měla být přiřazena při rozšiřování částečného kandidáta, na základě hodnot proměnných, které již byly přiřazeny. Další vylepšení lze získat technikou šíření omezení .

Kromě zachování minimálních hodnot obnovy použitých při zálohování, implementace zpětného sledování běžně udržují proměnnou stopu, aby se zaznamenala historie změn hodnot. Efektivní implementace se vyhne vytvoření záznamu proměnné stopy mezi dvěma po sobě jdoucími změnami, když není k dispozici žádný bod výběru, protože zpětné sledování vymaže všechny změny jako jednu operaci.

Alternativou k proměnné stopě je ponechat časové razítko, kdy byla proměnná provedena poslední změna. Časové razítko je porovnáno s časovým razítkem vybraného bodu. Pokud má výběrový bod přidružený čas později než čas proměnné, je zbytečné vrátit proměnnou, když je výběrový bod odsunut zpět, protože byl změněn před tím, než k výběrovému bodu došlo.

Viz také

Poznámky

Reference

Další čtení

externí odkazy