Definitive
În coadă
Muchii verificate

  • Curent
  • În coadă
  • Definitive
  • Drum
  • Estimare în linie dreaptă
Un clic pe un nod setează

Mai multe despre căutarea A*

Căutarea A*

Căutarea A* găsește un drum minim de la un start la o țintă, ca algoritmul lui Dijkstra, dar știe aproximativ unde este ținta. Fiecare nod primește o estimare a distanței rămase, linia dreaptă până la țintă, iar căutarea continuă mereu din nodul cu cea mai mică sumă dintre distanța de până acum și acea estimare. Faceți clic pe un nod ca să porniți din el, alegeți o țintă și avansați pas cu pas ca să vedeți cum căutarea se îndreaptă spre țintă și lasă neatinse colțuri întregi ale grafului. Apăsați Redare pentru a urmări căutarea sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Faceți clic pe un nod ca să devină start; comutați clicul pe Țintă și faceți clic pe alt nod ca să devină țintă. Numărul de pe fiecare muchie este lungimea ei, numărul de pe fiecare nod este distanța lui de până acum, iar linia întreruptă este estimarea în linie dreaptă a distanței rămase. Rândul de sub graf este coada, cu cel mai mic scor primul, cu scorul fiecărui nod: distanța de până acum plus estimarea. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Faceți clic pe un nod ca să devină start. Comutați clicul pe Țintă și faceți clic pe alt nod ca să devină țintă.
  2. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde în căutare.
  3. Urmăriți scorurile din coadă și estimarea în linie dreaptă, desenată întrerupt. La final, comparați nodurile de care a avut nevoie A* cu algoritmul lui Dijkstra.

Cum funcționează căutarea A*

Dați startului distanța 0 și puneți-l într-o coadă. Fiecare nod din coadă are un scor: distanța de până acum plus o estimare a distanței rămase. Repetați: luați nodul cu cel mai mic scor și marcați-i distanța ca definitivă. Dacă este ținta, opriți-vă. Altfel, pentru fiecare vecin care nu este definitiv, adunați lungimea muchiei la distanța nodului; dacă rezultatul este mai mic decât distanța de până acum a vecinului, micșorați-o, rețineți nodul ca drum până acolo și puneți vecinul în coadă cu noul scor.

De ce estimarea nu trebuie să fie niciodată prea mare

A* găsește un drum minim atâta timp cât estimarea nu spune niciodată că ținta este mai departe decât este de fapt: o estimare admisibilă. Linia dreaptă este una, pentru că niciun drum între două locuri nu este mai scurt decât linia dreaptă. O estimare prea mare îl poate face pe A* să rateze cel mai bun traseu; o estimare de 0 peste tot transformă A* în algoritmul lui Dijkstra, care este sigur, dar caută în toate direcțiile. Cu cât estimarea este mai bună, cu atât A* are nevoie de mai puține noduri. În aplicație, fiecare muchie este la fel de lungă cum este desenată, rotunjită în sus, deci linia dreaptă este o estimare sigură.

Întrebări frecvente

Ce este căutarea A*?

Un algoritm de găsire a drumului care găsește un drum minim de la un start la o țintă. Funcționează ca algoritmul lui Dijkstra, dar își ordonează coada după distanța de până acum plus o estimare a distanței rămase, așa că se îndreaptă spre țintă în loc să se întindă în toate direcțiile.

Ce este o euristică admisibilă?

O estimare a distanței până la țintă care nu este niciodată mai mare decât distanța minimă reală. Cu o estimare admisibilă, A* găsește întotdeauna un drum minim. Distanța în linie dreaptă pe o hartă este exemplul clasic.

Este A* mai rapid decât algoritmul lui Dijkstra?

De obicei da, când aveți nevoie de drumul către o singură țintă și aveți o estimare bună: A* face definitive mai puține noduri, pentru că nodurile aflate departe de țintă primesc scoruri mari. Cu o estimare de 0 face exact ce face algoritmul lui Dijkstra. Algoritmul lui Dijkstra este alegerea mai bună când aveți nevoie de distanțele până la toate nodurile.

Unde este folosit A*?

În jocurile video, pentru a muta personaje în jurul obstacolelor, în planificatoarele de rute, în planificarea mișcării roboților și în programele care rezolvă puzzle-uri precum jocul 15, unde estimarea numără cât de departe sunt piesele de locurile lor.

Este graful meu trimis undeva?

Nu. Graful este creat și parcurs în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor