Алгоритъм А*

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

В областта на компютърните науки, алгоритъмът за търсене А* (произнася се А звезда) е алгоритъм за намиране на път в граф между начален и краен връх в този граф.

Алгоритъмът А * е сред най-често срещаните и най-широко използваните при решаване на задачи, които изискват намиране на път в граф. Стартирането на алгоритъма за търсене А * гарантира намирането на оптималния маршрут между върха източник и свързания с него връх-цел.

В определени системи за намиране на пътни маршрути се предпочитат алгоритми, които позволяват предварително претърсване на граф за постигане на по-добри резултати. Въпреки това в практиката е установено, че А* превъзхожда редица подходи.

Питър Харт, Нилс Нилсон и Бертрам Рафаел от Станфордския изследователски институт (сега SRI International) първи описват алгоритъма през 1968 г. Той е разширение на алгоритъма на Дейкстра от 1959 г. А* постига по-добри времеви резултати чрез използване на евристични методи.

Описание[редактиране | редактиране на кода]

A* използва най-добро първо търсене и намира оптималния път от даден връх до целевия връх (от една или повече възможни цели).

А* следва оптималния път воден от приоритета на опашката.

Използва  оценъчна (knowledge-plus-heuristic cost) функция от възел x (обикновено представена като f(x)), за да определи реда по който търсенето обхожда възлите в дървото. Тази функция е сбор от две функции:

  • g(x): цената на оптималния път от начален възел до възел х.
  • h(x):  цената на предполагаемия оптималния път от възел x до някои целеви възел.

Предполагаемият оптимален път не трябва да надминава разстоянието до целевия връх.

В приложения за намиране на маршрут , h(x) може да представлява разстоянието по права линия до целта, тъй като това е най-малкото разстояние между две точки.

Ако h удовлетворява допълнителното условие за всяка граница (x, y) на графа (където с d се отбелязва дължината на границата),  то тя се нарича монотонна или постоянна. В този случай, А* се прилага по ефективно, тъй като няма нужда върховете да се обработват отново. Така А* става еквивалентен на алгоритъма на Дейкстра с понижена цена d'(x, y) := d(x, y) + h(y) - h(x).

История[редактиране | редактиране на кода]

През 1968 г. Нилс Нилссон предлага евристичен подход за ориентиране в пространство с препятствия. Алгоритъмът за намиране на път, 

наречен А1, е по-бърза версия от тогавашния най-добър подход Алгоритъм на Дейкстра, за намиране на най-кратките пътища в графи. Бертам Рафаел предлага няколко съществени подобрения в този алгоритъм, наричайки подобрената версия А2. След това Питър Е. Харт прави малки промени и въвежда аргумент, който затвърждава А2 като най-добрия възможен към момента алгоритъм за намиране на най-кратките пътища. В последствие Харт, Нилссон и Рафаел заедно разработват доказателство, че подобреният А2 алгоритъм е най-добър за намиране на пътища при ясно дефинирани условия.

Процес[редактиране | редактиране на кода]

Както всички алгоритми за търсене и А* първо претърсва пътищата, които е вероятно да водят до крайната цел. 

Това, което различава А* от greedy best-first search е, че той “взима под внимание” разстоянието, което е вече изминато;

Започвайки от първия връх (на граф), той поддържа опашка от върхове, които трябва да се обходят. Колкото по-малко е f(x) за определен връх х, толкова по-голям е неговият приоритет. На всяка стъпка от алгоритъма, върхът с най-малка стойност f(x) се премахва от опашката от върхове за преминаване, и едновременно с това се обновяват f и g стойностите на неговите съседни и се добавят към опашката.

Алгоритъмът продължава докато целевия връх има най-малката f стойност в сравнение с всеки друг връх в опашката или докато опашката се изпразни. Целевите върхове могат да бъдат преминавани многократно, ако там има други върхове с малка f стойност, тъй като те могат да водят до по-кратък път към целта. F стойността на целта в този случай е дължината на най-краткия път.

Псевдокод[редактиране | редактиране на кода]

Кода по-долу описва алгоритъма.

function A*(start, goal)   

    closedset := the empty set    // The set of nodes already evaluated.

    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node

    came_from := the empty map    // The map of navigated nodes.

    g_score[start] := 0    // Cost from start along best known path.

    // Estimated total cost from start to goal through y.

    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty

        current := the node in openset having the lowest f_score[] value

        if current = goal

            return reconstruct_path(came_from, goal)

        remove current from openset

        add current to closedset

        for each neighbor in neighbor_nodes(current)

            if neighbor in closedset

                continue

            tentative_g_score := g_score[current] + dist_between(current, neighbor)

            if neighbor not in openset or tentative_g_score < g_score[neighbor] 

                came_from[neighbor] := current

                g_score[neighbor] := tentative_g_score

                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

                if neighbor not in openset

                    add neighbor to openset

    return failure

function reconstruct_path(came_from, current)

    total_path := [current]

    while current in came_from:

        current := came_from[current]

        total_path.append(current)

    return total_path

Пример[редактиране | редактиране на кода]

Пример за А* алгоритъм в действие, където върховете са свързани с пътища и h(x) е права линия до целевата точка:

AstarExample.gif

Свойства[редактиране | редактиране на кода]

Като Обхождането по ширина, А* е завършен алгоритъм и винаги ще намери решение ако съществува такова.

Ако функцията heuristic h е допустима, това означава, че тя никога няма да надцени действителния минимален разход за постигане на целта, тогава А* е сам по себе си допустим(или оптимален) ако не използваме затворен сет. Ако се използва затворен сет, тогава h трябва да бъде монотонна(или последователна) за да може А* да бъде оптимален. Това означава, че за всяка двойка от съседни възли X и Y, където d(x, y) показва дължината на ръба между тях, трябва да имаме:

h(x)\le d(x, y)+h(y)

Това гарантира, че за всеки път X от първоначалния възел до x:

L(x)+h(x)\le L(X)+d(x, y)+h(y)=L(Y)+h(y)

Където L е функция, която означава дължината на път, Y е пътят X разширен за да включва y.С други думи е невъзможно да се намали(общото разстояние дотук + оставащото) чрез разширяване на път за да се обхване съседна възлова точка. (Това е аналогично на ограничението за неотрицателни ъглови тежести в Dijkstra's algorithm). Монотонността предполага допустимост, когато heuristic прецени, че самият възел е нула сам по себе си, тъй като(допускайки P = (f, v1,v2,...,vn, g) да е най-краткия път от който и да е възел f до най-близката цел g):

h(f) \le d(f, v_1)+h(v_1) \le d(f, v_1) +d(v_1, v_2) + h(v_2) \le \ldots \le L(P) + h(g) = L(P)

А* е също така оптимално ефективен за всеки heuristic h, което означава, че никой оптимален алгоритъм използващ същата heuristic функция ще разшири по-малко възли от А*, освен когато има  множество частични решения, където h точно прогнозира стойността на оптималния път.Дори в този случай, за всяка графа съществува някакъв ред на разделяне на връзките в опашката, така че А* проверява възможно най-малко възли.

Специални случаи[редактиране | редактиране на кода]

Dijkstra's algorithm, като още един пример за лагоритъм за търсене, може да се разглежда като специален случай на А*, където h(x) = 0 за всички x. Depth-first search може да бъде имплементиран чрез използване на А* тъй като има глобален брояч C, инициализиран с много голяма стойност. Всеки път, когато обработваме възел ние присвояваме С на всички новооткрити съседни възли.След всяка отделна задача, ние намаляваме брояча С с едно.По този начин колкото по-рано се намери възел, толкова по-голяма h(x) стойност има той. Трябва да се отбележи, обаче, че както Алгоритъм на Дейкстра така и Depth-first search могат да бъдат използвани по-ефективно, без да включването на h(x) стойност на всеки възел.

Детайли по имплементацията[редактиране | редактиране на кода]

Има няколко прости оптимизации или детайли, които могат значително да повлияят на производителността на А*. Първото, което трябва да се отбележи е че, начина по който приоритетната опашка работи с връзките може да има значим ефект върху производителността в някои ситуации.Ако връзките са разбити, така че опашката се държи по LIFO начин, А* ще работи като Depth-first search сред равни по разход пътища(избягвайки проучването на повече от едно също толкова оптимално решение).

Когато се търси път в края на търсенето, често се запазва препратка до родителя на съответния възел.В края на търсенето тези препратки могат да бъдат използвани за възстановяването на оптимален път. Ако тези препратки се съхраняват, тогава може да бъде важно, че същият възел не се появява в приоритетната опашка повече от веднъж (всеки запис, съответстващ на различен път към възела и всеки запис с различен разход). Страндартен подход в случая е да се провери дали даден възел, който е на път да бъде добавен, вече съществува в приоритетната опашка. Ако е така, тогава приоритетът и указателите към родителя са променени, за да отговарят на път с по-малък разход. Стандартна приоритетна опашка, базирана на бинарен куп, не поддържа директно търсенето на някой от елементите си, но може да бъде разширена с хеш таблица, която насочва елементи към тяхната позиция в стека.Това позволява на операцията, която намаля приоритета, да бъде извършена в логаритмично.Алтернативно, Фибоначи може да изпълни същата операция за constant amortized time. 

Допустимост и оптималност[редактиране | редактиране на кода]

Алгоритъмът А* е приемлив, защото преминава през по-малко върхове, спрямо всеки друг алгоритъм за търсене със същата евристика. Това е така, защото алгоритъмът използва „оптимистична“ оценка на разходите за пътя на всеки един връх, през който той счита да премине-оптимистичната оценка се състои в това, че истинският разход за пътя изминат през този връх към целта ще бъде поне толкова голямо, колкото на прогнозата. Но критично дотолкова, доколкото А* „знае“, че оптимистичната оценка може да бъде постижима.

Тук е основната идея на доказателството:

Когато А* завърши своето търсене, той вече е намерил път, чиито действителни разходи са по-малки от определените разходи за всеки път през всички отворени върхове. Тъй като тези прогнози са оптимистични A* може спокойно да ги пренебрегне. С други думи А* никога няма да пренебрегне възможността за път с по-ниски разходи, ако е допустимо.

Да предположим сега, че друг алгоритъм за търсене Б завърши своето търсене с път, чийто действително направен разход е не по-малък от очакваните разходи за път през някой отворен връх. Въз основа на информацията, с която евристичния алгоритъм А* има, алгоритъм Б не може да изключи възможността, че пътя през този връх е с по-нисък разход.

Това е вярно, само ако и двете твърдения са изпълнени:

  • A* използва приемлива евристика. В противен случай не е гарантирано, че „а звезда“ ще изведе по-малко върхове спрямо някой друг алгоритъм за търсене със същата евристика.
  •  A* решава само един проблем за търсене, а не поредица от такива. В противен случай не е гарантирано, че A* ще изведе по-малко върхове от точкови евристични алгоритми за търсене.

Граница на релаксация[редактиране | редактиране на кода]

Критерия за допустимост гарантира оптимален път за решение, това означава също, че А* трябва да проучи всички еднакво приемливи пътища, за да намери оптималния сред тях. Възможно е да се ускори търсенето за сметка на оптималността чрез облекчаване на критерия за допустимост. Много често ние искаме да свържем тази релаксация, за да можем да гарантираме, че решението за път е не по-лошо от (1 + ε) пъти от оптималното решение за път. Това твърдение е посочено като ε- допустимо.

Има редица ε-допустими алгоритми:

  • Претеглена А*. Ако ha(n) е допустима евристична функция, в претеглената А* използва  hw(n) = ε ha(n), ε > 1 като евристична функция и изпълнява А* търсенето като обикновено ( което  в крайна сметка се случи по-бързо, отколкото използвайки  ha тъй като възникват по-малко върхове).Следователно пътят открит от алгоритъма за търсене може да коства най-много ε пъти от най-малката стойност за път през графа.
  •  Статично претеглената използва стойността на функцията f(n) = g(n) + (1 + ε)h(n).
  •  Динамично претеглената използва стойността на функцията f(n) = g(n) + (1 + ε w(n))h(n), където FirstFormulaAsearch.png, и d(n) е дълбочината на търсенето и N e очакваната дължина на пътя решение.
  •  Изследвана динамична тежест използва представителна извадка на върхове  с по-добра оценка и включва евристична грешка.
  •  A* използва 2 евристични функции. Първата е FOCAL списък, който се използва, за да се изберат възможни върхове, а втората hF  се използва за да се избере най-добрия връх от FOCAL списъка.
  • Aε избира върхове с функцията  A f(n) + B hF(n), където А и B са константи. Ако не могат да бъдат избрани върхове, алгоритъмът ще спре с функцията C f(n) + D hF(n) , където С и D са константи
  • Алфа А* се опитва да поддържа в дълбочина първото разработване от предпочитащите разширени върхове. Алфа А* използва функцията на разходите fα(n) = (1 + wα(n)) f(n), където   SecondPictureAsearch.png  и  λ  и Λ са константи, като λ  < Λ, π(n) е родител на n и  ñ е най-близкия разширен връх

Комплексност[редактиране | редактиране на кода]

Комплексността на времето на А* зависи от нейната евристика. В най-лошия случай на търсене на неограничено пространство, броят на разширените върхове е експоненциален в дължината на решението(най-кратък път) d: O(b^d), където b e фактор на възлите(средният брой наследници на състояние). Това предполага, че съществува цел и е достъпна от началното състояние, ако не е  и пространството на състоянието е безкрайно, алгоритъмът ще е безкраен. Комплексността на времето е полином, когато търсеното пространство е дърво, има една единствена цел на състоянието и евристичната функция h има следното условие: ThirdPictureAsearch.png, където h* е оптимална евристика, с точния разход, за да стигнете от х до целта. С други думи грешката на h няма да расте по-бързо от логаритъма на „перфектната евристика“ на h*, която връща реалното разстояние от х до целта.

Приложения[редактиране | редактиране на кода]

А* обикновено се използва търсене на път в приложения като игрите, но първоначално е бил измислен като алгоритъм за обхождане на графи. Той намира приложение за разрешаване на различни проблеми, включително и присвояването, използвайки стохастична граматика.

Вижте също[редактиране | редактиране на кода]