Aké je podrobné vysvetlenie algoritmu A?

Algoritmus A* (A-star) je heuristický vyhľadávací algoritmus používaný v informatike na nájdenie najkratšej cesty medzi dvoma uzlami v grafe. Ide o rozšírenie Dijkstrovho algoritmu, ktorý nájde najkratšiu cestu, ale nepoužíva heuristiku.

Intuícia

A* používa heuristiku, informácie o problémovej doméne, ktoré pomáhajú pri jej hľadaní. Tieto heuristiky sa často nazývajú prípustné alebo heuristiky vzdialenosti, pretože nikdy nepreceňujú skutočné náklady na dosiahnutie cieľa. V mnohých prípadoch A* nájde optimálne riešenia, aj keď to nie je vždy zaručené.

Ako funguje A*?

A* udržiava počas vyhľadávania dve sady uzlov:OPEN (Fringe) a CLOSED

OTVORIŤ obsahuje všetky uzly, ktoré boli vygenerované, ale ešte nie sú úplne vyhodnotené. Je usporiadaný podľa F skóre (diskutované nižšie) jeho členov, s najnižším F skóre vpredu.

ZATVORENÉ obsahuje všetky uzly, ktoré boli úplne vyhodnotené.

Algoritmus začína umiestnením počiatočného uzla do polohy OPEN, zatiaľ čo cieľový uzol sa spočiatku nachádza v polohe CLOSED. V každom kroku algoritmu A* odstráni uzol v OPEN s najnižším skóre F, rozšíri ho a pridá všetkých jeho susedov do OPEN. Ak sused ešte nie je v režime OTVORENÉ alebo ZATVORENÉ, A* preň vypočíta skóre G (skutočné náklady na dosiahnutie suseda zo štartovacieho uzla) a skóre H (odhad nákladov na dosiahnutie cieľa od suseda). a pridá ho do OPEN. Ak je sused už v režime OPEN, nové skóre G sa porovná s aktuálnym skóre G, a ak je nové skóre G nižšie, sused sa aktualizuje. Ak je sused už v ZATVORENÉM stave, nové skóre G sa porovná s aktuálnym skóre G, a ak je nové skóre G nižšie, sused sa presunie z ZATVORENÉ do OTVORENÉ a aktualizuje sa.

Ukončenie

Algoritmus končí jedným z dvoch spôsobov. Po prvé, ak je cieľom sused expandovaného uzla, algoritmus vráti cestu k cieľu. Po druhé, ak sa OPEN stane prázdnym, algoritmus sa neúspešne ukončí, čo znamená, že neexistuje platná cesta od počiatočného uzla k cieľu.

Zložitosť

Časová zložitosť A* algoritmu v najhoršom prípade je exponenciálna vo veľkosti grafu. V praxi však A* funguje dobre pri mnohých problémoch a často nájde optimálne riešenia v primeranom čase.

• Predchádzajúca strana: Môžete podať správu zo seminára o umelom pasažierovi? 
• Ďalšia strana: Čo je cieľom xiangqi?