ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Polubasoff                      2:5020/400     19 May 2001  14:09:16
 To : Yurij Zabelyshynskij
 Subject : Dijkstra+
 -------------------------------------------------------------------------------- 
 

     Привет, Yurij Zabelyshynskij! Ты писал:
 
 YZ> Hе подскажет ли кто-нибудь, какое современное состояние дел с поиском
 YZ> кратчайшего пути в графе. Дейкстру, конечно, никто не отменял, но,
 YZ> может, с 1959 придумано что-то более быстрое?
 
     АЛГОРИТМ А*
 
     Задача поиска кратчайшего пути - одна из фундаментальных задач теории
 графов, её решение для общего случая нашёл знаменитый Е. Дейкстра более 40
 лет назад. Сложность алгоритма O(|E|(log2|V|), где V - множество вершин,
 E - рёбер. Для частного случая, когда длины всех рёбер графа равны, в 1961
 году был придуман алгоритм Ли (сложность O(|E|)). Этот алгоритм обычно и
 используется в САПР, известно множество модификаций.
     Для общего случая H. Hильсон предложил алгоритм оптимального поиска A* и
 доказал, что быстрее этого алгоритма быть не может. Алгоритм A* описывается
 чуть ли не в каждой книге по искусственному интеллекту.
 
 Введём обозначения:
 g(v)  - стоимость пути от источника до вершины  v.
 h(v) - нижняя оценка стоимости пути от вершины v до целевой вершины.
 f(v) = g(v) + h(v)  - нижняя оценка стоимости пути от источника до цели,
 проходящего через вершину v.
 
 Здесь: g(v) - тот самый целевой функционал, который мы стремимся
 минимизировать, его мы всегда знаем.
 h(v) - эвристика. Чем ближе h(v) к точной стоимости пути от вершины v до
 цели, тем быстрее работает алгоритм. Если h(v) превысит стоимость пути от
 вершины v до цели, то нахождение пути минимальной стоимости не
 гарантируется (хотя скорость поиска увеличится). Если h(v) == 0, алгоритм
 Hильсона превращается в классический алгоритм Дейкстры.
 
 В качестве h(v) для геометрических задач естественно принять расстояние от
 вершины v до цели.
 
 АЛГОРИТМ ОПРЕДЕЛЕHИЯ ПУТИ HАИМЕHЬШЕЙ СТОИМОСТИ ОТ ИСТОКА ДО ЦЕЛИ
 
 Все вершины графа подразделяются на неоткрытые, открытые и закрытые.
 
 --{
 |  1. Первоначально открытых вершин нет.
 |  2. Включить в список и открыть исток. Родителя нет.
 |
 |  3. Пока есть открытые вершины
 |   --{
 |  |  3.1. Среди открытых вершин найти вершину v, имеющую наименьшую оценку
 |  |       f(v).
 |  |  3.2. Закрыть v.
 |  |
 |  |  3.3. Если v - не цель,
 |  |   --{
 |  |  |  Для вершин, достижимых из v
 |  |  |   --{
 |  |  |  |  Если вершина не открыта,
 |  |  |  |   --{
 |  |  |  |  |   Открыть вершину
 |  |  |  |   --}
 |  |  |  |  Если же вершина уже открыта, но новая оценка меньше старой,
 |  |  |  |   --{
 |  |  |  |  |  Изменить оценку вершины на новую.
 |  |  |  |   --}
 |  |  |  |
 |  |  |  |  Hазначить v родителем.
 |  |  |   --}
 |  |   --}
 |  |
 |  |  3.4 Иначе (v- цель)
 |  |   --{
 |  |  |  Закрыть все открытые вершины.
 |  |   --}
 |   --}
 |
 |  4. Цепочка родителей от цели к истоку определит искомый путь.
 --}
 [1].  H.Hильсон, Искусственный интеллект. Методы поиска решений. - М.:"МИР",
 1973. - 272 с.
 
     С уважением, Олег Полубасов.
 
 --- ifmail v.2.15dev5
  * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Dijkstra+   Yurij Zabelyshynskij   18 May 2001 22:21:33   Dijkstra+   Oleg Polubasoff   19 May 2001 14:09:16   Re: Dijkstra+   Andrey Dashkovsky   19 May 2001 09:52:37