Scopul acestui laborator este învăţarea unor tehnici de rezolvare a problemelor de căutare în spaţiul stărilor.
Aspectele urmărite sunt:
Fie un sistem dinamic care se poate afla într-un număr finit de stări. Definim un graf orientat în care nodurile sunt stări, iar arcele reprezintă posibilitatea de a evolua direct dintr-o stare în alta. Graful conține un set de stări iniţiale şi un set de stări finale (scopuri). Problema descrisă de sistem va fi rezolvată prin parcurgerea spaţiului stărilor până când este găsită o cale de la o stare iniţială la o stare finală, în cazul în care problema admite soluţie. Căutarea este un mecanism general, recomandat atunci când o metodă directă de rezolvare a problemei nu este cunoscută.
Exemple de strategii de căutare în spaţiul stărilor:
Fie problema colorării a 7 țări de pe o hartă folosind 3 culori. Scopul este acela de a atribui câte o culoare fiecărei țări, astfel încât nicio țară să nu aibă niciun vecin de aceeași culoare cu aceasta. Soluția problemei va fi o listă de atribuiri din domeniul [„r“, „g“, „b“], care desemnează culorile atribuite fiecărei țări (1, 2, 3, 4, 5, 6, 7).
Această strategie se traduce în următorul cod Prolog:
all_members([], _). % predicat care verifică că toate elementele din prima listă sunt prezente în a doua all_members([X|Rest], In) :- member(X, In), all_members(Rest, In). solve(S) :- L = [_|_], length(L, 7), all_members(L, ["r", "g", "b"]), safe(S). % predicat care verifică faptul că țările nu au culori identice cu niciun vecin
Programul anterior este foarte ineficient. El construieşte extrem de multe atribuiri, fără a le respinge pe cele „ilegale“ într-un stadiu incipient al construcţiei.
Mecanismul de backtracking ne oferă o rezolvare mai eficientă. Știm că orice soluţie pentru problema colorării hărților constă într-o listă de atribuiri a 3 culori, de genul [X1/C1,X2/C2, ... X7/C7], scopul programului de rezolvare fiind să instanţieze adecvat variabilele X1, C1, X2, C2 etc. Vom considera că orice soluție este de forma [1/C1,2/C2, ... 7/C7], deoarece ordinea țărilor nu este importantă. Fie problema mai generală a colorării a N țări folosind M culori. Definim soluţia pentru N=7 ca o soluţie pentru problema generală a colorării hărților, care în plus respectă template-ul [1/Y1,2/Y2, ... 7/Y7]. Semnul „/“ este în acest caz un separator, fără nicio legătură cu operaţia de împărţire.
În Prolog vom scrie:
%% Lungimea soluției este cunoscută și fixă.
template([1/_, 2/_, 3/_, 4/_, 5/_, 6/_, 7/_]).
correct([]):-!.
correct([X/Y|Others]):-
correct(Others),
member(Y, ["r", "g", "b"]),
safe(X/Y, Others).
solve_maps(S):-template(S), correct(S).
Regulă: Atunci când calea către soluţie respectă un anumit template (avem de instanţiat un număr finit, predeterminat, de variabile), este eficient să definim un astfel de template în program.
Observaţie: În exemplul de mai sus am reţinut explicit ordinea celor 7 țări. Redundanţa în reprezentarea datelor ne asigură un câştig în viteza de calcul (câştigul se observă la scrierea predicatului safe).
În această situaţie nu este posibil să definim un template care descrie forma soluţiei problemei. Vom defini o căutare mai generală, după modelul următor:
solve(Solution):-
initial_state(State),
search([State], Solution).
search(+StăriVizitate,-Soluţie) definește mecanismul general de căutare astfel:
initial_state/1)next_state/2)final_state/1)search([CurrentState|Other], Solution):-
final_state(CurrentState), !,
reverse([CurrentState|Other], Solution).
search([CurrentState|Other], Solution):-
next_state(CurrentState, NextState),
\+ member(NextState, Other),
search([NextState,CurrentState|Other], Solution).
Căutarea în lăţime este adecvată situaţiilor în care se doreşte drumul minim între o stare iniţială şi o stare finală. La o căutare în lăţime, expandarea stărilor „vechi“ are prioritate în faţa expandării stărilor „noi“.
do_bfs(Solution):- initial_node(StartNode), bfs([(StartNode,nil)], [], Discovered), extract_path(Discovered, Solution).
bfs(+CoadaStărilorNevizitate,+StăriVizitate,-Soluţie) va defini mecanismul general de căutare în lăţime astfel:
A* este un algoritm de căutare informată de tipul best-first search, care caută calea de cost minim (distanță, cost, etc.) către scop. Dintre toate stările căutate, o alege pe cea care pare să conducă cel mai repede la soluție. A* selectează o cale care minimizează f(n) = g(n) + h(n), unde n este nodul curent din cale, g(n) este costul de la nodul de start până la nodul n și h(n) este o euristică ce estimează cel mai mic cost de la nodul n la nodul final.
astar_search(Start, End, Grid, Path) :- manhattan(Start, End, H), astar(End, [H:Start], [Start:("None", 0)], Grid, Discovered), get_path(Start, End, Discovered, [End], Path).
astar(+End, +Frontier, +Discovered, +Grid, -Result) va defini mecanismul general de căutare A*, astfel:
Prolog oferă un set special de predicate care pot construi liste din toate soluțiile de satisfacere a unui scop. Acestea sunt extrem de utile deoarece altfel este complicată culegerea informațiilor la revenirea din backtracking (o alternativă este prezentată în secțiunea următoare, mai mult în laboratorul viitor).
Predicatul findall pune în Bag câte un element Template pentru fiecare soluție a expresiei Goal. Desigur, predicatul este util atunci când Goal și Template au variabile comune. De exemplu:
even(Numbers, Even):- findall(X,(member(X, Numbers), X mod 2 =:= 0), Even). ?- even([1,2,3,4,5,6,7,8,9], Even). Even = [2, 4, 6, 8].