A* je vyhleda´vacı´ algoritmus, ktery´ byl vytvorˇen v roce 1968. Kombinuje Dijkstru˚v algo-ritmus a heuristicky´ prvek - hladovy´ algoalgo-ritmus. Heuristicky´ obvykle vyjadrˇuje prˇiblizˇny´
zpu˚sob, jak rˇesˇit proble´my, anizˇ by bylo zarucˇeno, zˇe se najde nejlepsˇı´ odpoveˇd’. A prˇesto, zˇe je A* algoritmus postaveny´ prˇı´mo na heuristicke´m prvku, tak zarucˇuje nejkratsˇı´ nale-zenou cestu.
Prˇi vyhleda´va´nı´ mezi dveˇma body vyuzˇı´va´ Dijkstru˚v algoritmus, ktery´ uprˇednostnˇuje uzly blı´zˇe pocˇa´tku a A* se snazˇı´ o redukci prohleda´vany´ch uzlu˚, a proto bere informace z hladove´ho heuristicke´ho hleda´nı´, ktere´ uprˇednostnˇujı´ uzly blı´zˇe cı´li. Ve standartnı´
terminologii pouzˇı´vane´ A*,g(n)vyjadrˇuje prˇesnou cenu cesty z pocˇa´tku do dane´ho uzlu n, ah(n)vyjadrˇuje heuristicky spocˇı´tanou cenu z dane´ho uzlundo cı´le. To je minima´lnı´
de´lka teoreticky nalezene´ cesty z dane´ho uzlu, kde optima´lnı´ cesta je delsˇı´, nebo rovna h(n). A* pote´ vzˇdy pro pocˇı´ta´nı´ vybere uzel, ktery´ ma´ nejnizˇsˇı´ cenuf(n) =g(n) +h(n). Heuristicky´ spocˇı´tany´ prvek, nikdy nesmı´ podhodnotit teoreticky spocˇı´tanou cestu do cı´le. A* algoritmus je take´ kompletnı´,a to ve smyslu, zˇe nalezne cestu, pokud neˇjaka´
existuje, respektive kdyzˇ jsou si pocˇa´tecˇnı´ a konecˇny´ uzel navza´jem vzˇdy dostupne´.
Naprˇı´klad, pokud uzly jsou body v dvourozmeˇrne´m prostoru se sourˇadnicemixiayi, a jedna´ se o Eukleidovsky´ prostor, pak platı´:
h(i) =
[(xi−xt,)2+ (yi−yt)2]
Kdeh(i)je na´sledneˇ nejkratsˇı´ mozˇna´ vzda´lenost z boduido bodut. [14]
Pokud budou cesty ohodnoceny prˇesneˇ jako heuristicky spocˇı´tana´ cena, pak nenı´
potrˇeba kontrolovat nahrazova´nı´ jizˇ nalezene´ cesty. Je to da´no tı´m, zˇe uzel se nemu˚zˇe tak zhorsˇit, aby pak do neˇj byla nalezena levneˇjsˇı´ cesta. Nicme´neˇ, heuristicky´ prvek neuvazˇuje prˇeka´zˇky v grafu. Jakmile prohleda´va´nı´ narazı´ na neˇjakou prˇeka´zˇku, tak se mu˚zˇe cena cesty uzˇ jen zveˇtsˇovat prˇi stejne´m heuristicke´m prvku. Doba hleda´nı´ stoupa´, kdyzˇ se snazˇı´ algoritmus prˇeka´zˇku obejı´t - to nemusı´ by´t mozˇne´. Do algoritmu lze prˇidat prvky hrube´ho prohleda´va´nı´ doprˇedu, ktere´ by hledaly prˇeka´zˇky a pote´ by bylo mozˇne´
urcˇit zdali je vhodne´ zacˇı´t prohleda´vat v uzavrˇene´m prostoru. Zvla´sˇteˇ, kdyzˇ se z tohoto prostoru lze dostat jen jednou cestou a tento prostor neobsahuje konecˇny´ bod. [4] [13]
V prˇı´loze je uka´zka pod na´zvemAStar.gif
Pro pouzˇitı´ v rea´lne´m cˇase ma´ A* dveˇ nevy´hody. Prvnı´ nevy´hodou je potrˇebny´ vy´-pocˇetnı´ cˇas pro nalezenı´ cesty z pocˇa´tecˇnı´ho bodu do konecˇne´ho. Druhou je spotrˇebova´nı´
velke´ho mnozˇstvı´ pameˇti beˇhem beˇhu algoritmu. To znemozˇnˇuje pouzˇitı´ velke´ho mnozˇ-stvı´ vyhleda´va´nı´ v jednu chvı´li, protozˇe kazˇde´ vyhleda´va´nı´ potrˇebuje udrzˇovath(n),g(n) af(n)pro kazˇdy´ procha´zeny´ uzeln. V rˇesˇenı´ programu bylo pouzˇito pole pro zapama-tova´nı´ informacı´ oh(n)ag(n), jestli je uzel procha´zeny´ a sousednı´ uzel ze ktere´ho prˇisˇla nejkratsˇı´ cestag(n). [5]
Jiny´ zpu˚sob rˇesˇenı´ je prioritnı´ fronta otevrˇeny´ch, tj. jesˇteˇ nenavsˇtı´veny´ch uzlu˚. Jakmile jsou vsˇechny sousednı´ uzly takto otevrˇene´ho uzlu prohleda´ny, zmeˇnı´ se stav uzlu na
”uzavrˇeny´”nebo ”neaktivnı´”a je odstraneˇn z fronty otevrˇeny´ch uzlu˚. Kazˇdy´ jeden cyklus programu jeden uzel odstranı´ z prioritnı´ fronty a naopak jich neˇkolik prˇibude. Ve fronteˇ jsou uzly serˇazeny podle hodnotyf()a je vybı´ra´n pro pocˇı´ta´nı´ vzˇdy ten s nejnizˇsˇı´ hodno-tou. Algoritmus zacˇı´na´ tak, zˇe se prˇida´ pocˇa´tecˇnı´ uzel do prioritnı´ fronty a prohledajı´ se jeho sousednı´ uzly. Pote´ je z fronty odstraneˇn a vybere se dalsˇı´ uzel s nejnizˇsˇı´ hodnotou f().
Na obra´zku 8 lze videˇt vsˇechny zkousˇene´ cesty s bodu A s jedinou vyznacˇenou optima´lnı´ cestou do boduB. Vsˇechny takove´ cesty vyjadrˇujı´ hodnotug(n)z pocˇa´tecˇnı´ho uzlu.
Obra´zek 8: Prostor procha´zeny´ch cest z bodu A do bodu B pomocı´ A* algoritmu
3 Implementace zada´nı´ a uka´zky ko ´ du
3.1 Implementace Delaunayho triangulace
Bylo zvoleno rˇesˇenı´ Delaunayho triangulace pomocı´ kruzˇnice opsane´ trˇem vybrany´m bodu˚m. Nejprve byly zvoleny trˇi body body a pote´ se procha´zı´ vsˇechny ostatnı´ body, zda-li nejsou v kruzˇnici opsane´ a to dı´ky testu nerovnosti:
(x−x0)2+ (y−y0)2−r2 ≤0
, kdex ay jsou sourˇadnice zkousˇene´ho bodu, x0 a y0 je strˇed kruzˇnice a r je polomeˇr kruzˇnice. Tato rovnice je ovsˇem pro otestova´nı´ vsˇech bodu˚ vy´pocˇetneˇ slozˇita´. Na vy´pocˇet je jednodusˇı´ vypocˇı´tat hodnotu determinantu:
Ax Ay A2x+A2y 1 Bx By Bx2+By2 1 Cx Cy Cx2+Cy2 1 Dx Dy Dx2+D2y 1
, kdeA,BaCjsou trˇi body vybrane´ pro kruzˇnici opsanou a bodDje zkousˇeny´ bod. Zjisˇt’uje se, zda tento bod nelezˇı´ uvnitrˇ kruzˇnice. Prˇi testova´nı´ je du˚lezˇita´ orientace bodu˚A,BaC zda jsou psa´ny po smeˇru hodinovy´ch rucˇicˇek v kruzˇnici opsane´, nebo naopak. Podle toho vyjde determinant kladny´, nebo za´porny´ vzhledem k vneˇjsˇı´m/vnitrˇnı´m bodu˚m. Proto se jednodusˇe otestuje, zdali je strˇed kruzˇnice vepsane´ kladny´ nebo za´porny´ pro vy´sledek determinantu.
Take´ mu˚zˇe nastat situce zˇe bude determinant pro na´hodny´ bodDnulovy´, pak tento bod lezˇı´ na kruzˇnici opsane´. Tak je porusˇena jednoznacˇnost Delaunayho triangulace a nabı´zı´ se vı´ce rˇesˇenı´, jak bodyA,B,CaDspojit.