Problema
Un robot trebuie sa ajunga din S in T evitand obstacolele. Fiecare celula libera este un nod; deplasarile intre celule vecine sunt muchii. In exemplu, fiecare deplasare are costul 1.
Traseul verde este un traseu posibil de cost 12; nu este singurul drum minim.
Modelarea si algoritmul
1. Construim graful celulelor accesibile.
2. Atribuim costuri nenegative tranzitiilor.
3. Dijkstra gaseste costurile minime; A* poate folosi distanta Manhattan drept euristica.
4. Reconstituim drumul din predecesori.
Ce este contraintuitiv?
Cel mai scurt traseu geometric nu este neaparat cel mai sigur sau cel mai economic. Daca adaugam costuri pentru risc, robotul poate prefera un ocol.