Algoritmus A-Star je grafový algoritmus sloužící k nalezení "nejkratší" cesty v ohodnoceném grafu vedoucí ze zadaného počátečního uzlu do cílového. Poprvé jej roku 1968 popsali P. Hart, N. Nilsson a B. Raphael. Jeho vstupem je ohodnocený graf, počáteční uzel a cílový uzel, výstupem je nejkratší cesta z počátečního uzlu do cílového, nebo zpráva o tom, že žádná taková cesta neexistuje.

Algoritmus je v principu shodný s prohledáváním do šířky s tím rozdílem, že namísto obyčejné fronty používá frontu prioritní, ve které jsou cesty seřazeny podle hodnoty speciální funkce f. Tato funkce je definována pro každou cestu p a je součtem tzv. heuristické funkce (h) posledního uzlu cesty p a její zbývající délky (g). Čím je hodnota funkce f(p) nižší, tím vyšší má daná cesta p prioritu. Stručně řečeno, algoritmus se dívá do "minulosti" (jak daleko musel ujít, než na konec cesty p došel) i do "budoucnosti" (jak daleko ještě zhruba zbývá ujít z posledního uzlu cesty p do cíle).

Dále se předpokládá, že cesty ve frontě neobsahují kružnice a pro každý cílový uzel se v ní nachází nanejvýš jedna cesta, a to ta nejkratší doposud nalezená.

Pořadí cest ve frontě je určeno následující funkcí:

£ f(x) = h(x) + g(x) £
  • f(x) - předpokládaná délka cesty x
  • h(x) - hodnota heuristické funkce pro koncový uzel cesty x
  • g(x) - délka cesty x
diagram

Předpokládaná délka této cesty je (1 + 5) + 21 = 27.

Heuristická funkce musí splňovat důležité podmínky - musí být větší než nula a tzv. přípustná (admissible). To znamená, že její hodnota pro libovolný uzel musí být nižší nebo rovna skutečné vzdálenosti z daného uzlu do cíle. Jinými slovy, její hodnota nikdy nemůže být větší než je skutečná vzdálenost z daného uzlu do cíle.

£ h(x) \leq h(y) + \mathrm{cost}(x,y) £

Heuristická funkce vzniká na základě (alespoň hrubé) znalosti struktury problému. Hledá-li se tedy například nejkratší cesta z města S do města G, lze jako heuristickou funkci města X použít zbývající vzdálenost z města X do města G. V tomto (idealizovaném) případě bude hodnota heuristické funkce přibližně rovna skutečné hodnotě.

Kroky algoritmu

  • Vytvoř prázdnou množinu cest F.
  • Do množiny F vlož cestu nulové délky obsahující počáteční uzel s.
  • Dokud není množina F prázdná, opakuj:
  • Z množiny F vyber nejkratší cestu p (s nejnižší hodnotou f(p)) a odeber ji.
  • Končí-li cesta v cílovém uzlu, vrať ji a ukonči výpočet.
  • Vytvoř nové cesty použitím všech možných operátorů na koncový uzel cesty p, které neobsahují smyčky.
  • Jestliže dvě cesty končí ve stejném uzlu, odstraň všechny kromě té nejkratší (s nejnižší hodnotou f(x)).
  • Přidej cestu p do množiny F.
  • Je-li množina F prázdná, oznam, že žádná cesta z počátečního do cílového uzlu neexistuje.

Příklad

Inicializace

Do množiny cest F je vložena cesta nulové délky, která začíná i končí počátečním uzlem S. U této cesty nemá smysl počítat jakoukoliv délku, protože je zaručeno, že bude v dalším kroku vybrána.

diagram

V tomto ohodnoceném grafu je počátečním uzlem S a cílovým G. U grafu je třeba zkontrolovat, zda je použitá heuristická funkce přípustná. V tomto případě to platí, protože je její hodnota vždy menší než hodnota skutečná.

Množina cest F(Délka cesty) + heuristikaPoznámka
S--

Krok 1

Z množiny F je vybrána jediná cesta, která se v ní nachází. Nekončí v cílovém uzlu, výpočet tedy pokračuje. Z jejího posledního uzlu S lze pokračovat do uzlů A, B, C. Nové cesty budou vloženy do množiny F.

Množina cest F(Délka cesty) + heuristikaPoznámka
S - B(1) + 3 = 4-
S - A(5) + 2 = 7-
S - C(10) + 1 = 11-

Krok 2

Z množiny F je vybrána nejkratší cesta S-B. Nekončí v cílovém uzlu, výpočet tedy pokračuje. Z jejího posledního uzlu B lze pokračovat do uzlu D. Nová cesta bude vložena do množiny F.

Množina cest F(Délka cesty) + heuristikaPoznámka
S - A(5) + 2 = 7-
S - B - D(1 + 5) + 2 = 8-
S - C(10) + 1 = 11-

Krok 3

Z množiny F je vybrána nejkratší cesta S-A. Nekončí v cílovém uzlu, výpočet tedy pokračuje. Z jejího posledního uzlu A lze pokračovat do uzlu C. Množina F však již cestu končící v uzlu C obsahuje, a tak bude zachována jen ta nejkratší z nich. V tomto případě je již známá cesta kratší, takže nebude do množiny F přidána.

Množina cest F(Délka cesty) + heuristikaPoznámka
S - B - D(1 + 5) + 2 = 8-
S - C(10) + 1 = 11-
S - A - C(5 + 6) + 1 = 12do C známe kratší cestu, tuto odebrat

Krok 4

Z množiny F je vybrána nejkratší cesta S-B-D. Nekončí v cílovém uzlu, výpočet tedy pokračuje. Z jejího posledního uzlu D lze pokračovat do uzlu C.Množina F však již cesty končící v uzlu C obsahuje, a tak bude zachována jen ta nejkratší z nich. V tomto případě je nová cesta kratší, takže bude do množiny F vložena, zatímco cesta S-C bude z množiny F odebrána.

Množina cest F(Délka cesty) + heuristikaPoznámka
S - B - D - C(1 + 5 + 1) + 1 = 9-
S - C(10) + 1 = 11do C známe kratší cestu, tuto odebrat

Krok 5

Z množiny F je vybrána nejkratší cesta S-B-D-C. Nekončí v cílovém uzlu, výpočet tedy pokračuje. Z jejího posledního uzlu C lze pokračovat do uzlů A, E, G. Nové cesty budou vloženy do množiny F.

Množina cest F(Délka cesty) + heuristikaPoznámka
S - B - D - C - E(1 + 5 + 1 + 1) + 1 = 9-
S - B - D - C - G(1 + 5 + 1 + 5) + 0 = 12-
S - B - D - C - A(1 + 5 + 1 + 6) + 2 = 15-

Krok 6

Z množiny F je vybrána nejkratší cesta S-B-D-C-E. Nekončí v cílovém uzlu, výpočet tedy pokračuje. Z jejího posledního uzlu E lze pokračovat do uzlů G. Množina F však již cesty končící v uzlu G obsahuje, a tak bude zachována jen ta nejkratší z nich. V tomto případě je nová cesta kratší, takže bude do množiny F vložena, zatímco cesta S-B-D-C-G bude z množiny F odebrána.

Množina cest F(Délka cesty) + heuristikaPoznámka
S - B - D - C - E - G(1 + 5 + 1 + 1 + 2) + 0 = 10-
S - B - D - C - G(1 + 5 + 1 + 5) + 0 = 12do C známe kratší cestu, tuto odebrat
S - B - D - C - A(1 + 5 + 1 + 6) + 2 = 15-

Krok 7

Z množiny F je vybrána nejkratší cesta S-B-D-C-E-G. Ta končí v cílovém uzlu, výpočet tedy končí.

Výsledek

Nejkratší nalezená cesta je S-B-D-C-E-G s délkou 10. Tato cesta je výstupem algoritmu.

diagram

Časová složitost

Asymptotická složitost algoritmu A-Star silně závisí na použité heuristické funkci, která ovlivňuje množství cest uvažovaných během výpočtu. Obecně se však dá říci, že jeho asymptotická složitost nikdy nebude horší než složitost prohledávání do šířky, což je € O(E + V) €, kde €V€ je počet uzlů a €E€ je počet hran.

Podobnost s ostatními algoritmy

  • Prohledávání do šířky
    • všechny hrany mají stejné ohodnocení, heuristická funkce je konstantní
    • h(x) = C
    • cost(x,y) = C
  • Uniform Cost Search
    • heuristická funkce je konstantní
    • h(x) = C
  • Greedy Search
    • všechny hrany mají stejné ohodnocení
    • cost(x,y) = C

Implementace

package graph.algorithm.path;

import graph.model.Graph;

import java.util.*;
import java.util.function.ToIntFunction;

public class AStar {
    /**
     * Finds 'optimal' path from start to goal using a heuristic (A-Star algorithm).
     * @param graph graph
     * @param start start node
     * @param goal goal node
     * @param weighter edge weighter to estimate distance of an edge
     * @param heuristic heuristic to estimate remaining distance from a specific node to goal
     * @param <NODE> node type
     * @param <EDGE> edge type
     * @return A-Star solution
     */
    public static <NODE, EDGE> AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic) {
        final AStarOutput<NODE> output = initializeOutput(graph, start, heuristic);

        final Collection<NODE> unprocessed = new LinkedList<>();
        unprocessed.add(start);

        while (!unprocessed.isEmpty()) {
            final NODE current = Collections.min(unprocessed, Comparator.comparingInt(output::getTotalEstimatedDistance));
            unprocessed.remove(current);

            if (current.equals(goal)) {
                // we have found the goal node
                break;
            }

            for (final Map.Entry<NODE, EDGE> adjacent : graph.successorsWithEdges(current).entrySet()) {
                final NODE next = adjacent.getKey();
                final EDGE edgeToNext = adjacent.getValue();
                final int edgeToNextDistance = weighter.applyAsInt(edgeToNext);
                final int alternativeDistance = output.getDistanceSoFar(current) + edgeToNextDistance;

                if (alternativeDistance < output.getDistanceSoFar(next)) {
                    final int newTotalEstimatedDistance = alternativeDistance + heuristic.applyAsInt(next);
                    output.setDistanceSoFar(next, alternativeDistance);
                    output.setPrevious(next, current);
                    output.setTotalEstimatedDistance(next, newTotalEstimatedDistance);
                    unprocessed.add(next);
                }
            }
        }

        return output;
    }

    private static <NODE, EDGE> AStarOutput<NODE> initializeOutput(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<NODE> heuristic) {
        final AStarOutput<NODE> output = new AStarOutput<>();

        for (final NODE node : graph.nodes()) {
            // set previous node in optimal path as unknown
            output.setPrevious(node, null);
            // set distance as unknown (max possible value)
            output.setDistanceSoFar(node, Integer.MAX_VALUE);
        }

        // this is zero by definition
        output.setDistanceSoFar(start, 0);
        // total estimated cost from start to goal
        output.setTotalEstimatedDistance(start, heuristic.applyAsInt(start));

        return output;
    }
}

Zdrojový kód Pokrytí testy

Reference