А* пребарување
А* е алгоритам од типот пребарување прво најдобриот кое користи дополнителна информација. Тој е различен од другите алгоритми од типот пребарување прво најдобриот по тоа што користи евристичка функција h(x) и цена на патот за доаѓање до јазелот g(x) при пресметување на цената f(x)=h(x)+g(x) на јазлите. Информацијата се внесува со евристичката функција. Алгоритмот е претставен на слика 1.

Слика 1:А* пребарувачки алгоритам.

За деталите за имплементација видете во [1] и [2].
Евристичката функција h(x) во А* алгоритамот ја проценува минималната цена за одење од јазелот до целта. Евристиката исто така може да го контролира однесувањето на А*.

Нека C* е минимална цена за одење од јазелот до целта. Ако h(x) = C* A* секогаш ќе го следи најкраткиот пат од јазелот до целта. Дополнително при пребарувањето нема да се разгрануваат јазли кои не се наоѓаат на најкраткиот пат со што алгоритмот е најбрзиот можен алгоритам. h(x) < C* како и во претходниот случај А* ќе го најде најкраткиот пат. Но при пребарувањето ќе се разгрануваат повеќе јазли отколку што е потребно за да се најде најкраткиот пат. h(x) > C* нема гаранција дека А* ќе го најде најкраткиот пат, но алгоритмот е многу побрз отколку во претходниот случај. h(x) >> g(n) А* се претвара во пребарување прво најдобриот h(x) = 0 А* се претвара во пребарување со униформна цена

Пред да започнеме со барање на евристика и пред да наведеме пример за А* алгоритамот ќе се задржиме на комплексноста во однос на меморија и време. Временската комплексност во најлош случај е O(bm) каде b е просечна вредност на разгранување (просечен број на наследници на состојба), а m е максимална длабочина на пребарувачкото дрво. Мемориската комплексност е она што прави проблеми кај А* алгоритмите. Во најлош случај барањата за меморија се експоненцијални што не е поволно. Обично со добра евристика може да се намали потребната меморија и време.
Сега ќе разгледаме различни евристики и нивна примена во проблеми на пребарување на решетка која е претставена на слика 1.1

Слика 1.1: Проблем на пребарување на решетка

Во решетката ѕидовите се сини, јазелот цел е црвен, а портокаловото поле е местото каде во моментот се наоѓа Smiley. Наша задача е да го однесеме Smiley од портокаловото поле до црвеното со што помалку чекори. Smiley може да се движи Горе, Долу, Лево или Десно, но не и дијагонално.
Важно прашање е ако е дадена некоја евристика дали ќе може да го најдеме минималниот пат? За ова се користи термин прифатливост (admissibility). За евристиката да биде прифатлива таа не смее да е поголема (never overestimate) од цената за доаѓање до целта. За подетална информација околу евристики и нивни ососбини како конзистентност и триаголна-нееднаквост видете во [1] на страните 97-101.
Сега ќе ги разгледаме евристиките Менхетен растојание (Manhattan distance) и Евклидово растојание ( Euclidean distance) за А* применети за проблемот на пребарување на решетка.

Менхетен растојание

Менхетен растојание е прифатлива евристика бидејќи Smiley мора секогаш да оди хоризонтално најмалку abs(node.x-goal.x) растојание и abs(node.y-goal.y) вертикално. Ако нема ѕидови на патот на Smiley тогаш h(n) е најмалку минималната цена, а ако има ѕидови тогаш цената на патот на Smiley е h(n)+d, каде d>0 но h(n) никогаш не е поголема од вистинската цена за доаѓање до црвеното поле.

Евклидово растојание

Евклидовото растојание е прифатлива евристика бидејќи најбрзиот начин за Smiley да стигне до црвеното поле е да оди по права линија, а Евклидовото растојание е растојание на права линија. Ако нема ѕидови на патот на Smiley тогаш h(n) е најмалку колку минималната цена, а ако има ѕидови тогаш цената на патот е h(n) +d, каде d>0 но сепак h(n) не е поголема од вистинската цена за доаѓање до целта.
Сега кога знаеме дека Менхетен или Евклидовото растојание ќе ни го дадат оптималниот пат може да продолжиме и безбедно да го пресметаме патот за Smiley да стигне до црвеното поле. За полесни пресметки во продолжение се користи Менхетен растојание како евристика.
На следните цртежи тековното поле е заокружено со сина рамка а вредностите на функциите f(x), g(x) и h(x) се претставуваат на позициите прикажани на слика 1.2.

Слика 1.2. Позиции на вредностите на функциите f(x), g(x) и h(x).

Почетни вредности
На почетокот портокаловото поле е ставено во редот со приоритети со вредности f(x)=h(x), g(x)=0 и h(x)=5.
Прв чекор
Се зема од редот портокаловото поле и се внесуваат наследниците на портокаловото поле во редоследот лево, горе, десно и доле (редоследот е избран за да го направи примерот пократок). Вредностите на функциите f(x), g(x) и h(x) за наследниците се прикажани на следната слика.

Втор чекор
Се зема долниот јазел од редот и се вметнуваат во редот неговите наследници (исто како горниот чекор). Функциите f(x), g(x) и h(x) за наследниците се прикажани на долната слика.

Забележете дека полето од кое доаѓаме не се вметнува во редот. Бидејќи евристиката е прифатлива знаеме дека кога еднаш јазелот ќе се внесе во листа на затворени јазли тој нема пак да се внесува во редот со приоритети.

Трет чекор
Се зема долниот јазел и се внесуваат неговите наследници во редот (во истиот редослед како погоре). Функциите f(x), g(x) и h(x) на наследниците се прикажани на следната слика.

Четври чекор
Се зема од редот десниот јазел и се вметнуваат неговите наследници (во истиот редослед како погоре). Функциите f(x), g(x) и h(x) на наследниците се прикажани на следната слика.

Петти чекор
Се зема од редот десниот јазел и се вметнуваат неговите наследници (во истиот редослед како погоре). Функциите f(x), g(x) и h(x) на наследниците се прикажани на следната слика.

Шести чекор
Се зема од редот десниот јазел кој е цел. Ова е коректно завршување на А*, односно алгоритамот запира кога ќе се земе од редот јазелот цел.

Во тој момент А* завршува и најден е пат со минимална цена. На следната слика е претставен патот од почетниот јазел до целта.

На сликата зелените стрелки се добиваат користејќи ги јазлите родители.
А* е флексибилен и моќен пребарувачки алгоритам кој користи информација за да постигне резултат барем исто толку добар како пребарувањето прво најдобриот или пребарувањето со униформна цена. Со менување на евристиката А* може да постигне оптимални резултати со бавно време на извршување или помалку добри резултати со побрзо време на извршување. Процесот на креирање добра евристика е многу креативен и потребна е анализа за да се докаже прифатливоста и конзистентноста.