Skip to content
Menu
CDhistory
CDhistory

N-Puzzle

Posted on noiembrie 4, 2021 by admin

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
  • Initial and Goal States
  • Algoritm de căutare
  • Funcție euristică
  • Modul cu un singur pas sau în rafală
  • Arborele de căutare
  • Reprezentarea stării
  • Culoarea nodurilor
  • Liste deschise și închise
  • Credite

Î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

.

Lasă un răspuns Anulează răspunsul

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Articole recente

  • Acela s-a întors: NYC sau Boston pentru 99 de dolari
  • Părinții lui Kate Albrecht – Aflați mai multe despre tatăl ei, Chris Albrecht, și despre mama ei, Annie Albrecht
  • Temple Fork Outfitters
  • Burr (roman)
  • Trek Madone SLR 9 Disc

Arhive

  • februarie 2022
  • ianuarie 2022
  • decembrie 2021
  • noiembrie 2021
  • octombrie 2021
  • septembrie 2021
  • august 2021
  • iulie 2021
  • iunie 2021
  • mai 2021
  • aprilie 2021
  • DeutschDeutsch
  • NederlandsNederlands
  • SvenskaSvenska
  • DanskDansk
  • EspañolEspañol
  • FrançaisFrançais
  • PortuguêsPortuguês
  • ItalianoItaliano
  • RomânăRomână
  • PolskiPolski
  • ČeštinaČeština
  • MagyarMagyar
  • SuomiSuomi
  • 日本語日本語
©2022 CDhistory | Powered by WordPress & Superb Themes