Možností je hodně. Nejpřehlednější mi připadá použít rekurzi (ale, samozřejmě, jde to i bez ní) a zavést si speciální návratovou hodnotu chyba, kterou může funkce navrátit místo správného řešení (pokud jej nenašla).
funkci backtrack(částečné_řešení) definujeme takto:
pokud částečné_řešení je už celé řešení:
navrací částečné_řešení
jinak:
pro každou možnost, jak rozšířit částečné_řešení na rozšířené_částečné_řešení:
pokud se zdá rozšířené_částečné_řešení být správně:
výsledek = backtrack(rozšířené_částečné_řešení)
pokud výsledek není chyba:
navrací výsledek
pokud funkce neskončila doteď, navrací chybu
Backtracking je způsob řešení hrubou silou, kdy pozvolna rozšiřujeme částečné řešení zadaného problému a snažíme se odhalit špatné řešení (slepé cestičky) co nejdřív. Oproti skutečnému řešení hrubou silou si můžeme výrazně pomoct, protože dokud je řešení jen částečné, je možné jej doplnit na ohromné množství úplných řešení řešení; pokud už z částečného řešení odhalíme, že všechna jsou špatná, nemusíme se s nimi jednotlivě vůbec zabývat. Můžeme si to hezky představit jako strom řešení, kde každý vrchol je částečné řešení; navrchu (v kořeni stromu) je počáteční stav, kdy nevíme vůbec nic, a listy stromu jsou všechna možná úplná řešení (z nichž většina je špatných). Když zjistíme, že některé částečné řešení je špatné, uřízneme celou jeho větev a vrátíme se ve stromu o úroveň výše.
V úloze osmi dam na šachovnici (nebo N dam na šachovnici NxN, v obecnějším případě) máme nějak rozestavět daný počet šachových královen tak, aby žádná přímo neohrožovala jinou. Tenhle problém se dá řešit velmi rychle a dokonce je na to jednoduchý obecný předpis. Ale máme zadáno jej řešit backtrackingem. Za částečné řešení si tedy vezmeme šachovnici, na které je méně než N královen, a jako špatné jej vyřadíme, pokud se už tak některé dvě ohrožují. Řešení budeme vždy rozšiřovat tak, že zkusíme přidat další královnu; když se ukáže, že se sice zatím žádné dvě neohrožují, ale další královnu není kam postavit, označíme tohle částečné řešení zase za chybné. Nakonec se nám podaří přidat všech osm královen a program skončí.
Není těžké si to na papíře vyzkoušet a podrobně popsat rozhodování. Ukázkový program v Pythonu vypadá takhle:
class Dama:
def __init__(self, x, y):
self.x, self.y = x, y
def __repr__(self):
return "Dama na "+str(self.x)+"x"+str(self.y)
def pridej_damu(damy):
if len(damy) == 8:
return damy
for x in range(8):
for y in range(8):
for dama in damy:
if x == dama.x or y == dama.y or x-y == dama.x-dama.y or x+y == dama.x+dama.y:
break
else:
vysledek = pridej_damu(damy + [Dama(x, y)])
if vysledek:
return vysledek
return False
damy = []
print (pridej_damu(damy))
Můžete si ten kód ale zkusit přepsat do Ruby a případně jej vylepšit tak, abychom zkoušeli další dámu pokládat rozumněji - až za sloupec, kam jsme dali tu poslední. U maturity ho nemusíte umět napsat, ale nikdo to vlastně nezakazuje.
Máme jedinou volnost: můžeme si vybírat, v jakém pořadí budeme zkoušet všechny možnosti, jak řešení rozšiřovat. Když dobře tipujeme, který postup povede ke správnému řešení (říká se tomu heuristika), můžeme na něj natrefit rychleji. U některých úloh nám dobré tipování taky může pomoct do budoucnosti, protože pomocí toho (někdy) snáze odhalíme špatné řešení.
Někdy chceme řešení najít všechna; i na to se dá backtracking bez problémů použít, stačí celá řešení nenavracet a jen je přidat do nějakého seznamu na výsledky.
Dále je pro backtracking důležité odhalit špatné řešení co nejdřív, při troše štěstí jich vyřídit i několik zároveň. To je případ zrychlení, když začínáme zkoušet další královny dávat až na následující řádek po té předchozí.