Inteligență Artificială - Problema Misionarilor și Canibalilor

I. INTRODUCERE

Formularea problemei:

(Problema misionarilor si canibalilor) Trei misionari şi trei canibali se află pe malurile unui râu, împreună cu o barcă care poate duce la un moment dat unul sau doi oameni. Se cere să se găsească o modalitate de a-i duce pe toţi pe celălalt mal, fără a lăsa niciodată ca numărul de misionari dintr-un loc să fie mai mic decât cel al canibalilor din acel loc.

Problema se va rezolva folosind strategia A*. În următoarea figură este prezentată schematic această problemă:

II. STRATEGIA DE REZOLVARE A*

Prezentare generală:

Rezolvarea unei probleme în inteligenţa artificială necesită specificarea unei structuri simbolice (pentru descrierea stărilor problemei), a unei mulţimi de operatori de transformare a stărilor şi a unei metode de planificare (numită strategie de control), care să indice ordinea de aplicare a operatorilor de transformare astfel încat soluţia problemei să fie găsită cât mai repede. Un algoritm de căutare a soluţiei primeşte ca intrare o problemă şi întoarce o soluţie sub forma unei secvenţe de acţiuni.

Găsirea unei soluţii se realizează prin căutare in spaţiul stărilor.Spaţiul de căutare a soluţiei unei probleme este alcătuit din mulţimea stărilor investigate până în momentul ajungerii în starea finală.

O stare este o configuraţie din universul problemei.

Nodul este structura de date utilizată pentru reprezentarea unei stări.

În procesul de căutare a soluţiei problemei se vor utiliza două liste:

- FRONTIERA – lista nodurilor evaluate (noduri cunoscute, pentru care nu se cunoaşte niciun succesor sau se cunosc doar o parte din succesori);

- TERITORIU – lista nodurilor expandate (noduri cunoscute, pentru care se cunosc toti succesorii).