Алгоритм A* — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
Алгоритм '''А*'''("A star", "А звёздочка") {{---}} информированный  алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
Алгоритм '''А*'''("A star", "А звёздочка") {{---}} информированный  алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
==Эвристика==
 
==Эвристика==
В процессе работы алгоритма для вершин используется функция <tex>f(v) = g(v) + h(v)</tex>, где <tex>g(v)</tex> - наименьшая стоимость пути в <tex>v</tex> из стартовой вершины, <tex>h(v)</tex> - эвристическое приближение стоимости пути от v до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
+
В процессе работы алгоритма для вершин используется функция <tex>f(v) = g(v) + h(v)</tex>, где <tex>g(v)</tex> - наименьшая стоимость пути в <tex>v</tex> из стартовой вершины, <tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от v до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
К примеру, если <tex>(h(v) == 0)</tex>, то А* превращается в [http://chernykh.net/images/stories/Person/deiksteira.jpg Дейкстру ]. Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.
+
К примеру, если <tex>(h(v) == 0)</tex>, то алгоритм посетит вершины в том же порядке, что и [[алгоритм Дейкстры]]. Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.
  
  
 
==Псевдокод==
 
==Псевдокод==
А* просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент похожи на наилучший, причем алгоритм учитывает путь уже пройденный до текущей вершины.  
+
А* просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими, причем алгоритм учитывает путь уже пройденный до текущей вершины.  
 
[[Файл:Astar_progress_animation.gif|thumb|right|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
 
[[Файл:Astar_progress_animation.gif|thumb|right|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
 
  void A*(start,goal)  
 
  void A*(start,goal)  
Строка 46: Строка 46:
 
  }
 
  }
  
==Доказательство оптимальности и корректности==
 
Полное доказательство расположено [http://www.cs.auckland.ac.nz/compsci709s2c/resources/Mike.d/astarNilsson.pdf здесь]. Здесь приведем основные факты.
 
Алгоритм является допустимым(корректным) если он гарантированно находит оптимальный путь из <tex>S</tex> до целевой вершины.
 
Допустимые алгоритмы могут различаться числом рассмотренных вершин и порядком просмотра вершин.
 
 
===Допустимость А*===
 
 
Лемма 1. Для любой незакрытой вершины <tex>n</tex> и любого оптимального пути <tex>P</tex> из <tex>S</tex> в <tex>n</tex> существует открытая вершина <tex>n'</tex>, лежащая на этом пути, для которой найденная стоимость пути из <tex>S</tex> оптимальна.
 
 
Теорема 1. Если для любой вершины эвристика не переоценивает настоящую стоимость минимального пути до целевой вершины, то А* допустим.
 
 
===Оптимальность А*===
 
 
Лемма 2. Предположим, что в процессе работы А* вершина <tex>n</tex> была закрыта и эвристика монотонна. Тогда вычисленный до нее путь из стартовой вершины оптимален.
 
 
Теорема 2. Пусть А допустимый алгоритм информированный не больше чем А* и эвристика допустима и монотонна.Тогда если А* рассмотрела в процессе выполнения некоторую вершину <tex>n</tex>, то А тоже рассмотрит эту вершину.
 
  
 
==Ссылки==
 
==Ссылки==
Строка 67: Строка 51:
 
*[http://en.wikipedia.org/wiki/A*_search_algorithm A*_search_algorithm Wikipedia]
 
*[http://en.wikipedia.org/wiki/A*_search_algorithm A*_search_algorithm Wikipedia]
 
*[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей и различных оптимизациях А* в частности]
 
*[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей и различных оптимизациях А* в частности]
*[http://dl.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM Статья на ACM Digital Library]
+
*[http://dl.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM Статья на ACM Digital Library, в которой подробно написано обоснование корректности алгоритма]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах ]]
 
[[Категория: Кратчайшие пути в графах ]]

Версия 03:40, 21 декабря 2011

Алгоритм А*("A star", "А звёздочка") — информированный алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

Эвристика

В процессе работы алгоритма для вершин используется функция [math]f(v) = g(v) + h(v)[/math], где [math]g(v)[/math] - наименьшая стоимость пути в [math]v[/math] из стартовой вершины, [math]h(v)[/math] — эвристическое приближение стоимости пути от v до конечной цели. [math]h(v)[/math] должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку. К примеру, если [math](h(v) == 0)[/math], то алгоритм посетит вершины в том же порядке, что и алгоритм Дейкстры. Если [math]h(v)[/math] всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.


Псевдокод

А* просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими, причем алгоритм учитывает путь уже пройденный до текущей вершины.

Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.
void A*(start,goal) 
{
    closed := {}; // Множество вершин расстояние до которых мы уже оценили
    open.push(start);// Очередь с приоритетом 
    f[start] = g[start] + h[start];
    parent[start] = start;
    while (open.size() != 0) 
    {
        x := open.pop(); 
        if (x == goal) 
            return succsess(x);// Кратчайший путь найден         
        closed.push(x);   
        for (y : xy in E) 
        {
            if (y in closed)      
                continue;
            tmp := g[x] + d[x,y]  // Стоимость пути до y
            if (y not in open) 
            {
                open.push(y);
                tentative_is_better = true;
            }
            else            
                if (tmp < g[y])                 
                    tentative_is_better := true   
                else
                    tentative_is_better := false  
            if (tentative_is_better == true)// 
            {
                parent[y] = x;
                g[y] = tmp;
                f[y] = g[y] + h[y];
            }
        }
    }
    return failure; // Наша цель недостижима из start
}


Ссылки