Această aplicație web vă permite să vizualizați o reprezentare grafică a unei serii de algoritmi diferiți de căutare grafică, în timp ce rezolvați o serie de probleme de 8 puzzle la alegere.
Începem
În partea stângă a acestei aplicații, veți vedea panoul de control. Folosind Panoul de Control, puteți configura următoarele aspecte ale aplicației:
- Initial State și Goal State
- Ce algoritm de căutare să utilizați
- Ce funcție euristică să utilizați, dacă folosiți un algoritm de căutare informată
- Și dacă doriți să folosiți modul single-step sau burst mode
Câteodată, fiecare dintre aceste opțiuni va fi descrisă mai detaliat mai jos.
Initial and Goal States
Pentru a seta stările Initial sau Goal, puteți face clic fie pe butonul „Edit state” (Editează starea), fie pe reprezentarea grafică a stării.
Ar trebui să vedeți o fereastră de tip pop-up ca cea de mai jos:
Pentru a modifica o piesă, faceți clic pe piesa pe care doriți să o înlocuiți, apoi introduceți noua valoare la tastatură. Acest lucru va schimba țigla cu cea care a deținut anterior acea valoare.
Algoritm de căutare
N-Puzzle suportă cinci algoritmi de căutare grafică diferiți. Primele trei sunt Algoritmi de căutare neinformați:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
Celelalte două sunt Algoritmi de căutare informați:
- A* Search
- Greedy Search
Dacă alegeți un Algoritm de căutare informată, va trebui să selectați și o funcție euristică.
Funcție euristică
N-Puzzle acceptă trei Funcții euristice diferite:
- Distanța euclidiană
- Distanța Manhattan (distanța dintre oraș și blocuri)
- Tiles Out-of-place
Modul cu un singur pas sau în rafală
N-Puzzle poate fi utilizat în două moduri. Modul implicit este modul Single-Step, care vă permite să „derulați” o căutare, pas cu pas. Acest lucru este util pentru a înțelege mai bine cum funcționează un algoritm de căutare.
Celălalt mod este modul Burst. Odată pornit, Burst Mode continuă să ruleze o căutare până când este găsită starea de obiectiv. O căutare în modul Burst poate fi oprită, dar nu poate fi „derulată”.
Arborele de căutare
Reprezentarea stării
În timp ce o căutare este activă, veți putea vedea o reprezentare vizuală a arborelui de căutare. Fiecare nod din acest arbore de căutare reprezintă un aranjament de dale (sau stare) și este desenat ca o cutie care este împărțită în 4 secțiuni.
Diagrama următoare prezintă un nod preluat dintr-o căutare Greedy:
Secțiunea cea mai mare este starea puzzle. Sub aceasta veți vedea două secțiuni mai mici.
După starea puzzle sunt două secțiuni. Secțiunea din stânga este adâncimea nodului. Secțiunea din dreapta este scorul euristic. Scorul euristic este utilizat numai cu Algoritmi de căutare informați, deci dacă utilizați Breadth-first, Depth-first sau Iterative Deepening Search, scorul euristic va fi omis.
Ultima secțiune înregistrează ordinea în care au fost extinse nodurile. De exemplu, nodul rădăcină va fi întotdeauna „#1”, iar următorul nod extins va fi marcat ca fiind „#2”.
Culoarea nodurilor
Pentru a face arborele de căutare mai „lizibil”, marginea fiecărui nod este codificată în culori în funcție de starea sa curentă.
Diagrama următoare prezintă algoritmul A* (cu euristica distanței euclidiene) aplicat la o problemă care poate fi rezolvată în doar două mutări:
Corile pot fi interpretate după cum urmează:
| Culoare | Semnificație |
|---|---|
| Albastru | Dacă un nod se află în lista deschisă, atunci acesta va fi evidențiat în albastru. |
| Roșu | După fiecare iterație a unui algoritm de căutare, nodul care va fi extins în continuare va fi evidențiat cu roșu. Acest lucru se aplică chiar și atunci când nodul obiectiv a fost găsit. |
| Cenușiu | Dacă o stare a fost explorată, aceasta va fi gri. De exemplu, în etapa 2) din diagrama de mai sus, starea inițială a fost colorată în gri pentru a indica faptul că a fost explorată. În etapa 3), un nod care reprezintă starea inițială este redescoperit, dar nu va fi extins, deoarece starea inițială a fost extinsă prin intermediul nodului rădăcină. |
| Verde | După ce a fost găsită starea obiectiv, aceasta va fi evidențiată cu verde. |
| Gold | După ce a fost găsit un nod care reprezintă starea obiectivului, toate nodurile de pe calea de întoarcere la nodul rădăcină vor fi evidențiate cu auriu. |
| Purple | Când se utilizează Iterative Deepening Search, nodurile neexplorate care depășesc adâncimea maximă nu vor fi adăugate la lista deschisă. Aceste noduri vor fi colorate în violet. |
Liste deschise și închise
În timp ce algoritmii de căutare sunt în curs de execuție, sunt menținute două liste. Prima este lista deschisă – aceasta este utilizată pentru a ține evidența nodurilor care au fost descoperite, dar care nu au fost încă explorate.
A doua este lista închisă – aceasta este utilizată pentru a ține evidența nodurilor care au fost explorate sau a nodurilor care nu vor fi explorate deoarece reprezintă stări care au fost deja explorate prin intermediul altor noduri.
Când o căutare este activă, numărul de noduri din Listele Deschise și Închise va fi vizibil în colțul din stânga sus:
Credite
.