Алгоритъм за търсене A*
A* е набор от стъпки (алгоритъм), който компютрите могат да използват, за да разберат как бързо да стигнат до две места. Ако имате списък с места и колко трудно е да стигнете от едното направо до другото, с помощта на A* можете бързо да откриете най-бързия път. Алгоритъмът е свързан с алгоритъма на Дийкстра, но прави интелигентни предположения, така че да не прекарва толкова дълго време в търсене на бавни пътища. Това е добра поредица от стъпки, ако искате само пътя между две места. Ако искате да намерите много пътища от една и съща карта, има по-бързи начини, които намират всички отговори наведнъж, като например алгоритъма на Флойд-Уоршал. A* няма да работи, ако искате да посетите няколко места по време на едно пътуване (задачата за пътуващия търговец).
Стъпките
A* първо се нуждае от списък на всички места, до които можете да отидете, а след това от списък на разстоянието между тях. След това ще ви посочи най-бързия начин да стигнете от място А до място Z.
За пример ще кажем, че A е свързан с местата B и C, а B и C са свързани с D и E. D и E са свързани с Z. Има 4 възможни начина да отидете от A до Z. Можете да отидете A-B-D-Z, A-C-D-Z, A-B-E-Z или A-C-E-Z. Компютърът, използващ A*, първо поглежда колко трудно е да се стигне от A до B и от A до C. Това е "цената" за тези места. Цената на дадено място означава колко трудно е да се стигне от А до това място. След като запише двете разходи, компютърът разглежда колко трудно е да се стигне от B до D и добавя това към разходите на B. Той записва това като цена на D. След това компютърът поглежда колко трудно е да се стигне от C до D и добавя това към разходите на C. Това е различна цена за D и ако тя е по-малка от тази, която вече има, той ще замени старата. Компютърът иска да знае само най-добрия път, затова пренебрегва пътя с по-висока цена. Той ще запомни само един от A-B-D и A-C-D, в зависимост от това кой е по-бърз.
Компютърът продължава и намира най-бързия начин да стигне до E. Накрая той преминава от D до Z и намира цена, а от E до Z и намира цена. Той получава крайната цена за Z и това е най-малката цена, която може да получи. Сега компютърът знае кой път е най-бърз и има отговор. Компютърът може да направи подобна поредица от стъпки, но с много, много повече места. Всеки път той ще разглежда мястото, което е най-близо до А, и ще сумира разходите за съседите на това място.
Горната поредица от стъпки се нарича алгоритъм на Дийкстра. Алгоритъмът на Дийкстра може да бъде бавен, тъй като ще търси на много места, които може да се намират в погрешна посока от Z. Ако попитате компютъра как да стигнете от един град до близък, алгоритъмът на Дийкстра може да се окаже, че търси в друга държава.
A* решава този проблем. A* ви позволява да кажете на компютъра колко ще е разстоянието от всяко място до края. Компютърът може да използва предположението, за да определи приблизително колко време ще отнеме да се стигне от определено място до Z. Вместо да избере само мястото, което е най-близо до А, той ще разгледа това, което вероятно ще има най-малък общ сбор. Той намира тази обща сума, като добавя разходите към очакваното оставащо разстояние. По този начин той може да търси само в посока, в която нещата вероятно ще се подобрят. Не е проблем, ако предположението не е перфектно, но дори едно обикновено лошо предположение може да накара програмата да работи много по-бързо. Ако се опитвате да намерите път между две места в реалния свят, доброто предположение е просто разстоянието между тях по права линия. Реалният път по пътищата ще бъде по-дълъг, но това позволява на програмата да го познае и тя няма да тръгне в грешна посока.
В литературата по математика и информатика това предположение често е функция на мястото и се нарича евристика. Всяко място е връх, а всеки път между две места е ребро. Това са думи от теорията на графите.
