Ziua 2 - Algoritmul A*

Canibali și Misionari

Reminder cerință din ziua 1:

În Colab: Canibali și Misionari

Pe malul râului se află 3 canibali și 3 misionari. Lângă ei se află o barcă cu maxim 2 locuri. Toată lumea vrea să ajungă pe partea cealaltă a râului, dar nimeni nu știe să înoate.

Nici pe barcă, nici pe vreun mal nu trebuie să fie vreodată mai mulți canibali decât misionari (altfel o să îi mănânce). În barcă trebuie să fie mereu minim un om și maxim M oameni. Permutările între mal și barcă au loc instantaneu, așadar nu ne punem problema ordinii în care coboară sau urcă oamenii în barcă.

Care este o secvență de acțiuni în urma căreia toți oamenii să ajungă pe celălalt mal fără ca misionarii să ajungă prânz pentru canibali?

Rezolvați pe hârtie

Exercițiul 1

Formalizează problema canmis. Creează o clasă Nod cu toate informațiile relevante unei stări a jocului. La inițializare, nodul va avea câmpurile:

• numărul de canibali pe malul stâng (by default 3);
• numărul de misionari pe malul stâng (by default 3);
• poziția bărcii (-1 pentru malul stâng, 1 pentru malul drept).

Implementează următoarele metode:

• constructorul clasei -> __init__
• egalitatea -> __eq__
• transformarea în obiect de tip string a informației nodului curent -> __str__
• transformarea în obiect de tip string a informației elementelor dintr-o listă -> __repr__

Observații:

• Informația nodului curent va fi afișată de forma:

Stare curentă:
3 misionari, 3 canibali  | 0 misionari, 0 canibali
Barca se află pe malul stâng

• Informația elementului dintr-o listă va fi afișată de forma:

(3, 3, -1)

Unde tuplul reprezintă (<număr misionari pe malul stâng>, <număr canibali pe malul stâng>, <malul pe care se află barca>)

Implementați următoarele funcții ajutătoare:

• drumRadacina() - care va returna o listă cu toate nodurile ca obiecte (nu informația nodurilor) de la rădăcină până la nodul curent;
• vizitat() - returnează True dacă nodul curent (self) a fost deja vizitat pe drumul de la rădăcină până la părintele lui, False altfel
• succesori() - generează lista de stări succesoare valide

Soluție pentru funcția succesori:

Exercițiul 2

Găsește cel mai scurt drum pentru a transporta toți oamenii pe malul drept folosind algoritmul BFS

Pentru validarea codului:

import time

def printDrumRadacina(nod):
  ''' Returneaza un string cu formatarea drumului de la radacina pana la nodul curent '''
  drum = nod.drumRadacina()
  afisare = str(drum[0])

  for i in range(1, len(drum)):
    state = drum[i - 1]
    stateCurent = drum[i]

    afisare += f'\n\tPasul {i}: Barca a plecat de pe malul ' + \
    f'{"stang" if state.barca == -1 else "drept"} ' + \
    f'cu {abs(state.misionari - stateCurent.misionari)} misionari ' + \
    f'si {abs(state.canibali - stateCurent.canibali)} canibali\n\n' + \
    str(stateCurent)

  return afisare

start_time = time.time()
nodFinal = bfs()
end_time = time.time()

drum = printDrumRadacina(nodFinal)

if drum:
  print(drum)
else:
  print("Nu exista solutie.")

print(f"\nTimpul de rulare: {end_time - start_time} secunde.")

Output:

    Stare curenta:
    3 misionari, 3 canibali | 0 misionari, 0 canibali
    Barca se afla pe malul stang

        Pasul 1: Barca a plecat de pe malul stang cu 0 misionari si 2 canibali

    Stare curenta:
    3 misionari, 1 canibali | 0 misionari, 2 canibali
    Barca se afla pe malul drept

        Pasul 2: Barca a plecat de pe malul drept cu 0 misionari si 1 canibali

    Stare curenta:
    3 misionari, 2 canibali | 0 misionari, 1 canibali
    Barca se afla pe malul stang

        Pasul 3: Barca a plecat de pe malul stang cu 0 misionari si 2 canibali

    Stare curenta:
    3 misionari, 0 canibali | 0 misionari, 3 canibali
    Barca se afla pe malul drept

        Pasul 4: Barca a plecat de pe malul drept cu 0 misionari si 1 canibali

    Stare curenta:
    3 misionari, 1 canibali | 0 misionari, 2 canibali
    Barca se afla pe malul stang

        Pasul 5: Barca a plecat de pe malul stang cu 2 misionari si 0 canibali

    Stare curenta:
    1 misionari, 1 canibali | 2 misionari, 2 canibali
    Barca se afla pe malul drept

        Pasul 6: Barca a plecat de pe malul drept cu 1 misionari si 1 canibali

    Stare curenta:
    2 misionari, 2 canibali | 1 misionari, 1 canibali
    Barca se afla pe malul stang

        Pasul 7: Barca a plecat de pe malul stang cu 2 misionari si 0 canibali

    Stare curenta:
    0 misionari, 2 canibali | 3 misionari, 1 canibali
    Barca se afla pe malul drept

        Pasul 8: Barca a plecat de pe malul drept cu 0 misionari si 1 canibali

    Stare curenta:
    0 misionari, 3 canibali | 3 misionari, 0 canibali
    Barca se afla pe malul stang

        Pasul 9: Barca a plecat de pe malul stang cu 0 misionari si 2 canibali

    Stare curenta:
    0 misionari, 1 canibali | 3 misionari, 2 canibali
    Barca se afla pe malul drept

        Pasul 10: Barca a plecat de pe malul drept cu 0 misionari si 1 canibali

    Stare curenta:
    0 misionari, 2 canibali | 3 misionari, 1 canibali
    Barca se afla pe malul stang

        Pasul 11: Barca a plecat de pe malul stang cu 0 misionari si 2 canibali

    Stare curenta:
    0 misionari, 0 canibali | 3 misionari, 3 canibali
    Barca se afla pe malul drept


    Timpul de rulare: 0.0072934627532958984 secunde.

Soluție pentru BFS:

Algoritmul A*

Algoritmul A* se folosește pentru a găsi un drum de cost minim de la un nod-start la un nod-scop într-un graf ponderat.

Exemplu

Fie graful de mai jos:

• nodStart - nodul 0 (galben)
• noduriScop - [4, 6] (mov)
• informațiile din cercuri - informația fiecărui nod
• informațiile de pe muchii - costul drumurilor
• informațiile din pătrate - estimarea costului fiecărui nod

Informații generale

Date de intrare:

• graful (nodurile, muchiile împreună cu costurile lor)
• nodul din care începe căutarea (nodul-start)
• un scop dat sub forma unei condiții pe care trebuie să o îndeplinească nodul căutat (se poate oferi chiar nodul propriu-zis, condiția fiind relația de egalitate cu acest nod). Vom numi mai departe nodul care îndeplinește condiția nod-scop
• o estimare (euristică) a costului de la fiecare nod din graf la nodul (nodurile) scop.

Notații:

• $f$ - costul unui drum
• $\hat{f}$ - costul estimat al unui drum
• $g(nod_c)$ - costul unui drum de cost minim de la nodul start la un nod curent, $nod_c$, din drum
• $h(nod_c)$ - costul efectiv al drumului de cost minim de la nodul curent la nodul scop pe un anumit drum
• $\hat{h}(nod_c)$ - costul estimat de la nodul curent la nodul scop (euristica)

Pentru un drum dat D, avem formula: $f_D$ = $g_D(nod_c$) + $h_D(nod_c$), unde $nod_c$ e un nod din drumul D

Deoarece pe parcursul construirii arborelui de parcurgere nu cunoaștem costul adevărat de la nodul curent la nodul scop (graful fiind descoperit pe măsura ce e parcurs), ne vom folosi în algoritm de formula costului estimat: $\hat{f}_D$ = $g_D$($nod_c$) + $\hat{h}_D$($nod_c$).

Admisibilitate:

Spunem că euristica este admisibilă dacă îndeplinește condiția: $\hat{h}(nod) \leq h(nod)$

Regula de consistență:

Având o muchie $n_1 \rightarrow n_2$, euristica calculată în nodul $n_1$ trebuie să fie mai mică sau egală decât costul muchiei $n_1 \rightarrow n_2$ adunat la euristica nodului $n_2$

$\hat{h}(n1) \leq cost(n1 \rightarrow n2) + \hat{h}(n2)$

Pașii algoritmului

Se consideră două liste: OPEN (cu nodurile descoperite care înca nu au fost expandate) și CLOSED (cu nodurile descoperite și expandate).

1. În lista open se pune la început doar nodul de pornire.
2. Inițial lista closed e vidă
3. Cât timp lista open nu e vidă se execută repetitiv pașii următori:
   • Se extrage primul nod, n, din lista open și se pune în closed.
   • Dacă nodul n este nod scop, se oprește căutarea și se afișează drumul de la nodul-start până la nodul n.
   • Se extinde nodul n, obținând succesorii lui în graf. Nu se vor lua în considerare succesorii care se află în drumul de la nodul start la n. Toți succesorii îl au ca părinte pe n. Toți succesorii care nu se află deja în open sau closed sunt inserați în lista open astfel încât aceasta să fie în continuare ordonată crescător dupa f.
   • Pentru succesorii care sunt deja în open sau closed, în cazul în care pentru drumul care trece prin n, s-a obținut un f mai mic, li se schimbă părintele în n și li se actualizează f-ul, iar nodurile din open sunt repoziționate în lista astfel încât să rămână ordonată crescător după f.
   • Pentru nodurile din closed (care au fost deja expandate) ar trebui refăcut calculul pentru nodurile succesoare lor, prin urmare cel mai simplu este să le readăugăm direct în open.

Implementare

Pentru implementare putem considera niște clase ajutătoare, care ar fi adaptate la particularitățile problemei curente rezolvate cu A*.

Clasa Nod reprezintă clasa prin care se memorează informațiile despre nodurile din graf. Poate avea următoarele proprietăți:

• informație - referință către informația nodului
• părinte - referință către nodul-părinte din arbore. Pentru rădăcina arborelui, părintele va avea valoarea None.
• g - costul de la rădăcina arborelui până la nodul curent
• f - costul estimat pentru drumul care pornește de la rădăcină și trece prin nodul curent
• h - estimarea făcuta pentru nod (valoarea funcției euristice pentru nod)

și următoarele metode:

• expandează / succesori - care va returna o listă cu toți succesorii posibili ai nodului curent
• scop - care testează dacă nodul e nod scop

Exerciții

În Colab: A Star

Exercițiul 1

Modifică 3 costuri de pe graful din exemplu astfel încât estimarea să își păstreze proprietatea de admisibilitate

Rezolvare aici

Exercițiul 2

Demonstrează că orice euristică consistentă este și admisibilă

Rezolvare aici

Exercițiu 3

Dă un exemplu de euristică admisibilă și consistentă pentru Lupul Capra și Varza

Rezolvare aici

Exercițiul 4 - Canibali și misionari

Preia clasa Nod din colabul cu probleme de căutare și modific-o pentru a reține informațiile necesare pentru aplicarea algoritmului A*.

Adăugă următoarele câmpuri în constructorul clasei Nod:

• g - parametru care reprezintă costul drumului de la nodul start la nodul curent, cu valoarea implicită 0;
• h - parametru care reprezintă costul estimat al drumului de la nodul curent la nodul scop, cu valoarea implicită 0;
• f - costul estimat al unui drum, calculat ca sumă a parametrilor g și h

Implementează metoda def __lt__(self, cls) care compară două noduri pe baza costului f.

Adaugă funcția estimeaza_h(), care va returna un număr rațional reprezentând estimarea costului de la nodul curent până la cel mai apropiat nod scop.

Modifică funcția de calcul succesori astfel încât să calculeze pentru noii succesori și valorile din g, h și f.

# Rezolvă aici

Pentru validarea codului:

a = Nod(3, 3, -1, 2, 3)
print(a.f == 5)
print(a.f)
print()

print(a.estimeaza_h() == 3.0)
print(a.estimeaza_h())
print()

b = a.succesori()
print(b[0].f == 6.0)
print(b[0].f)

Exercițiul 5 - A*

Găsește drumul de cost minim pentru problema canmis folosing algoritmul A*

# Rezolvă aici

Pentru validarea codului:

import time

def printDrumRadacina(nod):
  ''' Returneaza un string cu formatarea drumului de la radacina pana la nodul curent '''
  drum = nod.drumRadacina()
  afisare = str(drum[0])

  for i in range(1, len(drum)):
    state = drum[i - 1]
    stateCurent = drum[i]

    afisare += f'\n\tPasul {i}: Barca a plecat de pe malul ' + \
    f'{"stang" if state.barca == -1 else "drept"} ' + \
    f'cu {abs(state.misionari - stateCurent.misionari)} misionari ' + \
    f'si {abs(state.canibali - stateCurent.canibali)} canibali\n\n' + \
    str(stateCurent)

  return afisare

start_time = time.time()
nodFinal = aStar()
end_time = time.time()

drum = printDrumRadacina(nodFinal)

if drum:
  print(drum)
else:
  print("Nu exista solutie.")

print(f"\nTimpul de rulare: {end_time - start_time} secunde.")

Mai multă teorie și demonstrații despre algoritm în paperul original