Pornind de la o stare initiala (stg) vrem sa ajungem la starea finala (dreapta), in cat mai putini pasi. O cautare in spatiul tuturor starilor nu mai este posibila din cauza numarului mare de stari (9! > 300,000)
Pentru a alege cat mai bine urmatoarea stare, A* combina costul de a ajunge in acea stare cu o euristica ce estimeaza costul de acolo pana in starea finala.
In cazul de fata, euristicile presupuse au fost:
- numarul de blocuri nelalocul lor (starea initiala vs. finala)
- suma distantelor Manhattan ale fiecarei valori din celulele initiale raportate la pozitiile in care se afla in celulele finale (mai multe despre asta aici)
In fine, implementarea mea se afla aici, pentru cazul considerat, am obtinut acelasi numar de pasi, insa cea de-a doua euristica a fost mult mai rapida.
UPDATE:
Pseudocodul de mai sus furnizat de AI-planning este putin defectuos... am refacut implementarea si ea se afla aici. In prima versiune, o stare nu era considerata decat o singura data, dupa care trecea in "allNodes". In noua versiune, o stare poate fi considerata si a doua oara, daca promite o distanta mai mica pana la solutie fata de cat promitea anterior (adica am descoperit solutia printr-o alta cale).
UPDATE:
Pseudocodul de mai sus furnizat de AI-planning este putin defectuos... am refacut implementarea si ea se afla aici. In prima versiune, o stare nu era considerata decat o singura data, dupa care trecea in "allNodes". In noua versiune, o stare poate fi considerata si a doua oara, daca promite o distanta mai mica pana la solutie fata de cat promitea anterior (adica am descoperit solutia printr-o alta cale).
Niciun comentariu:
Trimiteți un comentariu