Kapitola 14: Backtracking a Řez – Cesta bludištěm

Představte si, že jste v obrovském bludišti. Hledáte poklad. Dojdete na křižovatku a vydáte se doleva. Po chvíli narazíte na zeď. Co uděláte? Sednete si a začnete brečet? Ne! Vrátíte se na poslední křižovatku a zkusíte cestu doprava. Přesně takhle funguje Prolog. Je to neúnavný průzkumník, který automaticky zkouší všechny možnosti, dokud nenajde řešení, nebo dokud nevyčerpá všechny cesty. Tomuto procesu se říká Backtracking (Zpětné navracení).

14.1 Princip myši v bludišti

Prolog si pamatuje každou křižovatku (místo, kde měl na výběr z více pravidel). Když narazí na neúspěch (FAIL), automaticky se vrátí na poslední křižovatku a zkusí další možnost.

BACKTRACKING (ZPĚTNÉ NAVRACENÍ) Automatický mechanismus Prologu pro hledání řešení. Když aktuální cesta selže, Prolog se vrátí k poslednímu bodu rozhodnutí a zkusí alternativní cestu.
Robot v bludišti
Obrázek 14.1: Backtracking v akci. Robot narazil na zeď (FAIL) a vrací se na křižovatku.

14.2 Řez (Cut) - Operátor !

Někdy ale nechceme, aby se Prolog vracel. Představte si, že jste našli klíč k pokladu. Nemá smysl se vracet a hledat jiný klíč. Chcete říct: "Tohle je ta správná cesta, ostatní možnosti zahoď." K tomu slouží operátor řezu, který se píše jako vykřičník !.

ŘEZ (CUT) - ! Speciální cíl, který vždy uspěje, ale "odřízne" možnost návratu (backtrackingu). Říká Prologu: "Už se nevracej za tento bod, toto rozhodnutí je konečné."

Příklad: Maxima ze dvou čísel

max(X, Y, X) :- X >= Y, !.  % Pokud je X větší, výsledek je X a KONEC (!).
max(X, Y, Y).               % Jinak je to Y.

Bez vykřičníku by Prolog mohl zbytečně zkoušet druhé pravidlo, i když první uspělo. S vykřičníkem říkáme: "Pokud jsi zjistil, že X >= Y, tak výsledek je X a už o tom nediskutuj."

Řešené příklady: Barvení mapy

Příklad 14.1: Barvení mapy (Backtracking v akci)
Máme mapu tří států (CZ, SK, PL). Sousední státy nesmí mít stejnou barvu. Máme k dispozici tři barvy.

barva(cervena). barva(modra). barva(zelena).

obarvi(CZ, SK, PL) :-
    barva(CZ),           % Zkus obarvit CZ
    barva(SK), CZ \= SK, % Zkus obarvit SK, aby to nebylo stejné jako CZ
    barva(PL), CZ \= PL, SK \= PL. % Zkus obarvit PL, aby to nebylo stejné jako CZ a SK

Jak to funguje:

  1. Prolog dá CZ = cervena.
  2. Zkusí SK = cervena. Chyba! (CZ \= SK neplatí).
  3. Backtracking: Vrátí se k výběru barvy pro SK.
  4. Zkusí SK = modra. To jde.
  5. Zkusí PL = cervena. Chyba! (CZ \= PL neplatí).
  6. ... a tak dále, dokud nenajde kombinaci, která funguje.

Klíčový koncept: Automat vs. Manuál

Backtracking je automatická převodovka Prologu – dělá to sám a vy se nemusíte starat. Řez (!) je ruční brzda nebo zamknutí dveří. Dává vám kontrolu nad tím, kudy Prolog půjde, a umožňuje vám program zrychlit (tím, že zakážete zbytečné hledání).

Otázky k zamyšlení

  1. Co se stane, když v bludišti narazíte na zeď (FAIL) a už nemáte žádnou jinou křižovatku, kam se vrátit? (Celý dotaz selže a Prolog odpoví false).
  2. Proč může být operátor řezu ! nebezpečný? (Můžete omylem odříznout i správné řešení, pokud ho použijete špatně).
  3. Jak souvisí backtracking s prohledáváním do hloubky (DFS)? (Je to v podstatě to samé – Prolog jde co nejhlouběji jednou cestou, než se vrátí).

🧪 Laboratoř: Hledání a optimalizace