Модернизация алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции

Динамическое взвешивание использует функцию стоимости f (n) = g (n) + (1+ ε w (n)) h (n), где где d (n) — глубина поиска, а N — ожидаемая длина пути решения. В выборочном динамическом взвешивании используется выборка узлов для лучшей оценки и исключения ошибки эвристики. Aε* использует две эвристические функции. Первый — это список FOCAL, который используется для выбора узлов-кандидатов, а второй hF используется для выбора наиболее перспективного узла из списка FOCAL. Aε выбирает узлы с функцией Af (n) + BhF (n), где A и B — константы. Если ни один узел не может быть выбран, алгоритм будет возвращаться с функцией Cf (n) + DhF (n), где C и D — постоянные. Вычислительная сложность Временная сложность A* зависит от эвристики. В худшем случае неограниченного пространства поиска количество развернутых узлов является экспоненциальным в глубине решения (кратчайший путь) d: O (bd), где b — коэффициент ветвления (среднее число преемников на каждое состояние). Это предполагает, что целевое состояние существует вообще и доступно из начального состояния; Если это не так, и пространство состояний бесконечно, алгоритм не завершится. Эвристическая функция оказывает большое влияние на практическую эффективность поиска A*, поскольку хорошая эвристика позволяет A* отсекать многие узлы bd, которые расширяют неинформированный поиск. Его качество может быть выражено через эффективный коэффициент ветвления b*, который может быть определен эмпирически для случая задачи путем измерения количества расширенных узлов, N и глубины решения, а затем решения N + 1 = 1 + b * + (b *)2 +. .. + (b *)d .Хорошей эвристикой обладают те, у которых низкий эффективный коэффициент ветвления (оптимальное значение b * = 1).Временная сложность является полиномиальной, когда поисковое пространство является деревом, существует одно целевое состояние, а эвристическая функция h удовлетворяет следующему условию: h (x) -h * (x) — = O (log h * (x)) где h* - оптимальная эвристика, точная стоимость перехода от x к цели.

Другими словами, ошибка h не будет расти быстрее, чем логарифм «идеального эвристического» h *, который возвращает истинное расстояние от x до цели. Но еще большую проблему, чем временная сложность, представляют собой потребляемые алгоритмом ресурсы памяти. В худшем случае ему приходится помнить экспоненциальное количество узлов. A* с итеративным углублением (итеративное углубление A*, IDA*), A* с ограничением памяти (ограниченные по памяти A*, MA*), упрощённый MA* (упрощенный MA*, SMA*) и рекурсивный поиск по первому наихудшему совпадению (рекурсивный поиск с наилучшим началом, RBFS) .Оптимизация А*. Существует несколько способов изменить алгоритм поиска, чтобы получить хорошие результаты при использовании ограниченных ресурсов:

Лучевой поиск. Одним из способов борьбы с ограничением по памяти является наложение ограничений на количество узлов в списке Open; когда список полон и необходимо добавить новый узел, просто выбрасывается узел с наихудшим значением. Список Closed также может быть уничтожен, если каждая ячейка хранит в себе длину наилучшего пути и обратный указатель. Этот алгоритм не гарантирует оптимальности пути, так как узел ведущий к нему может быть выброшен, но все равно может позволить найти разумный путь. Алгоритм последовательных приближений для A* (IDA*). Алгоритм последовательных приближений, использованный для IDDFS, как упоминалось ранее, может быть использован и для A*. Это полностью избавляет от необходимости хранить списки Open и Closed. Делается простой рекурсивный поиск, собирается наколенная стоимость пути g (n), и поиск прекращается при достижении значением f (n) = g (n) + h (n) заданных пределов. Начинать нужно с пределом остановки равным h (start), и в каждой последовательной итерации, устанавливать новый предел остановки равным минимальному значению f (n), которое превысило прежнюю границу. Аналогично для IDDFS среди методов полного перебора, IDA* - асимптотически оптимален в расходе времени и памяти среди эвристических методов. Недопустимая эвристика h (n). Как обсуждалось выше, если эвристическое приближение оставшейся стоимости пути слишком мало, то A* может быть очень неэффективным. Но если приближение слишком высоко, то для найденного пути не гарантируется оптимальность. В играх в которых диапазон изменения стоимостей ландшафта широк — от болот до автострад — можно поэкспериментировать с различными промежуточными значениями, чтобы найти точный баланс между эффективностью поиска и качеством найденного пути. Существуют и другие модификации A*, однако они не подтвердили свою полезность для поиска пути в геометрическом пространстве. Отношения к другим алгоритмам.

Что отличает A * от жадного алгоритма поиска наилучшего первого — это то, что он учитывает уже пройденную стоимость / расстояние, g (n).Некоторые общие варианты алгоритма Дейкстры можно рассматривать как частный случай A *, где эвристикаh (n) = 0для всех узлов, в свою очередь, и Dijkstra и A * - частные случаи динамического программирования. Сам A * является частным случаем обобщения ветвей и границ и может быть выведен из прямого-дуального алгоритма для линейного программирования[.

http://logic.pdmi.ras.ru/~sergey/teaching/mlau12/08-svm.pdf (С.Николенко SVM и kernel methods, 2012 г.), Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А. И.

Штерна.— М.: Наука. Гл. ред. физ.-мат. лит., 1990.— 488 c.— ISBN 5−02−13 080−7]. Варианты А*•Anytime Repairing A* (ARA*)[22]•Block A*•D*•Field D*•Fringe•Fringe Saving A* (FSA*)•Generalized Adaptive A* (GAA*)• Алгоритм последовательных приближений для А* (IDA*)•Информированный поиск (Informational search) [18]•Jump point search•Lifelong Planning A* (LPA*)•Simplified Memory bounded A* (SMA*)•Theta*•Anytime A* [23]•Realtime A* [24]•Anytime Dynamic A*•Time-Bounded A* (TBA*)[25]A* также может быть адаптирован к двунаправленному алгоритму поиска, при этом особое внимание следует уделить критерию остановки.

4.2. Пример реализации алгоритма А* Алгоритм поиска A* («А звезда» или «А стар», от англ. A star) — алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью. Данный алгоритм является наилучшим алгоритмом для поиска оптимальных путей в различных пространствах. Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута идущего через этот узел.

Типичная формула эвристики выражается в виде: f (n) = g (n) + h (n)где:f (n) — значение оценки, назначенное узлу n ;g (n) — наименьшая стоимость прибытия в узел n из точки старта А;h (n) — эвристическое приближение стоимости пути к цели В от узла n. Таким образом, этот алгоритм сочетает в себе учет длины предыдущего пути из алгоритма Дейкстры с эвристикой из алгоритма «лучший-первый». Так как некоторые узлы могут обрабатываться повторно (для поиска оптимальных путей к ним позднее) необходимо ввести новый список Closed для их отслеживания. A* имеет множество интересных свойств. Он гарантированно находит кратчайший путь, до тех пор пока эвристическое приближение h (n) является допустимым, то есть он никогда не превышает действительного оставшегося расстояния до цели. Этот алгоритм наилучшим образом использует эвристику: ни один другой алгоритм не раскроет меньшее число узлов, не учитывая узлов с одинаковой стоимостью. На рис. 7 а -б, можно увидеть как A* справляется с ситуациями проблемными для других алгоритмов. Описание алгоритма:

1. Начинаем со стартовой точки A и добавляем ее в «открытый список» клеток, которые нужно обработать. Открытый список это что-то наподобие списка покупок. В данный момент есть только один элемент в списке, но позже мы добавим еще. Список содержит клетки, которые может быть находятся вдоль пути, который вы выберете, а может и нет. Проще говоря, это список клеток, которые нужно проверить.

2. Ищем доступные или проходимые клетки, граничащие со стартовой точкой, игнорируя клетки со стенами, водой или другой непроходимой областью. И также добавляем их в открытый список. Для каждой из этих клеток сохраняем точку A, как «родительскую клетку». Эта родительская клетка важна, когда мы будем прослеживать наш путь.

3. Удаляем стартовую точку A с вашего открытого списка и добавляем ее в «закрытый список» клеток, которые вам больше не нужно проверять. Исходный граф показан на рисунке 8: здесь стартовый узел -S, цель (финишный узел) — G, стоимость пути обозначена для каждой дуги, а эвристики показаны в таблице. Рисунок 8. Исходный граф Как уже было сказано выше решение с использованием алгоритма А* существенно зависит от использования конкретной эвристики.

В приведенном ниже численном примере ребра являются существующими железными дорогами, а эвристика h (x) — минимальное возможное расстояние на физической карте до цели. Алгоритм ищет железнодорожный маршрут между двумя городами. Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f (x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g (x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h (x)).Функция h (x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h (x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. Оценки эвристик в задачах оптимизации для физических расстояний является очевидным и бесспорным. В то же время использование алгоритма поиска А* в задачах иного рода (например, оптимального управления, экономических) является отдельным трудным вопросом и определяет неоднозначные решения с позиций различных эвристик. Алгоритм был изначально предназначен для оптимизации перемещения в робототехнике по поверхности, на которую можно наложить координатную сетку. Если постановка задачи предполагает возможность перемещения в четырех основных направлениях, то в качестве эвристики рекомендуется выбор манхэттенского расстояния: h (v) =∣v.x — goal. x∣ + ∣v.y — goal. y∣.Если к перемещениям в четырех основных направлениях добавляются диагональные перемещения, то в качестве метрики рекомендуется выбор расстояния Чебышева: h (v) =max (∣v.x — goal. x∣, ∣v.y — goal. y∣).Если передвижение не связано с сеткой, то используется евклидова метрика:.Здесь (v.x;v.y) — координаты текущей «открытой точки»; (goal.x;goal.y) — координаты конечной «целевой» точки.Таблица. Значения эвристик Узел.

Эвристическая оценка расстояния до целиhS7A6B2C1G0Шаг 1. Свойства узла S: поскольку узел является источником, стоимость пути от начального узлак нему самому же для него равна нулю: g (x)=0. Эвристика расстояния до цели g (x) для S равна 7. Тогда f (s) = g (s) + h (s) = 0 + 7 = 7. Sf (S)=g (S)+ h (S)=0+7=7Рисунок 9. Результат после первого шага.

Шаг 2. От вершины S можно двигаться к вершине, А и к вершине В. Для вершины, А стоимость равна сумме стоимости предыдущей родительской вершины, т. е. S и А: g (S -A) = 0 + 1; эвристика для, А h (A) = 6, тогда f (A) = g (S -A) + h (A) = (0 +1) + 6 = 7. Для вершины В аналогично g (S -В) = 0 + 4; эвристика для Вh (В) = 2, тогда f (B) = g (S -В) + h (В) = (0 +4) + 2 = 6. Это значение ниже, чем для вершины А. Следовательно, путь через вершину В к этому шагу более эффективен, чем через А. S — Bf (B)=g (S-B)+ h (B)=(0+4)+2=6S — Af (A)=g (S-A)+ h (A)=(0+1)+6=7Рисунок 10. Результат после второго шага.

Шаг 3. Продолжаем построение через вершину В: от нее к целевой финишной вершине путь идет через вершину С: g (S -В-C) = 0 + 4 + 2; эвристика для Ch© = 1, тогда f© = g (S -В- C) + h© = (0 +4 + 2) + 1 = 7. S -В — Сf (C)=g (S-B-C)+ h (C)=(4+2)+1=7Рисунок 11. Результат после третьего шага.

Шаг 4. К вершине С есть альтернативные пути: S -А- C и S -А -В- C. Оценим эти пути. g (S -А-C) = 0 + 1 + 5; эвристика для Ch© = 1, тогда f© = g (S -А- C) + h© = (0 + 1 + 5) + 1 = 7. g (S -А- В) = 0 + 1 + 2; эвристика для Вh (В) = 2, тогда f (В) = g (S -А-В) + h (В) = (0 + 1 + 2) + 2 = 5. g (S -А- В — С) = 0 + 1 + 2 + 2; эвристика для Сh© = 1, тогда f© = g (S -А-В — С) + h© = (0 + 1 + 2 +2) + 1 = 6. S -A- Сf (C)=g (S-A- C)+ h (C)=(0+1+5)+1=7S -A -B- Cf (C)=g (S-A-B-C)+ h (C)=(0+1+2+2)+1=6S -A — Gf (G)=g (S-A-G)+ h (G)=(0+1+12)+0=13Рисунок 12. Результат после четвертого шага.

Шаг 5. Для финишной целевой вершиныG родительскими являются вершины, А и С. Маршрут S -А- G оценивается функцией f (G) = g (S -А- G) + h (G) = (0 + 1 + 12) + 0 = 13. Через вершину С к целевой вершине проходят три маршрута: S -А-В — С — G, S -В — С — G, S -А- С — G. Оценим их.

Для маршрута (S -А-В — С — G) g (S -А-В — С) = 5. Тогда g (S -А-В — С- G) = 5 +3. При этом f (G) = g (S -А-В- С-G) + h (G) = (5 + 3) + 0 = 8. Для маршрута (S -В — С — G) g (S -В — С) = 4 + 2 = 6. Тогда g (S -В — С- G) = 6 +3. При этом f (G) = g (S -В- С-G) + h (G) = (6 + 3) + 0 = 9. Для маршрута (S -А-С — G) g (S -А-С) = 6. Тогда g (S -А- С- G) = 6 +3. При этом f (G) = g (S -А- С-G) + h (G) = (6 + 3) + 0 = 9. Следовательно, среди трех маршрутов минимальным является S -А-В — С- G и для него f = g + h = 8.

То есть путь S -А-В- С-G является оптимальным. S — B- C — Gf (G)=g (S-B-C-G)+ h (G)=(0+4+2+3)+0=9S — А — B — C — Gf (G)=g (S-А-B-C-G)+ h (G)=(0+1+2+2+3)+0=8S -А- C — Gf (G)=g (S-А-C-G)+ h (G)=(0+1+5+3)+0=9Рисунок 13. Результат после пятого шага: путь S -А-В- С-G является оптимальным5. Программная реализациямодифицированного алгоритма Дейкстры.

Для того чтобы охарактеризовать оптимальное решение при наличии множества целей, необходимо определение недоминируемого или набора Парето. Определение: недоминируемое решение или множество Парето: набор решений / n-кортежей для задачи многоцелевой (n целей, n> 1) оптимизации, обладает следующими свойствами:

1. Ни одно решение не является лучшим для всех целевых функций.

2. Нет единого решения лучшегодля всех целевых функций, чем любое множество существующих решений. Анализ оптимальности включает в себя генерацию набора недоминируемых решений из кортежей [длина пути, затраты] от источника к месту назначения. При генерации множества, недопустимые комбинации отбрасываются (ограничения длины и затрат удовлетворяются).Ниже приведен алгоритм, используемый для генерации множественных недоминируемых решений. Каждый узел хранит несколько путей к исходным узлам. Пути, сохраненные для узла назначения (множество A), выбираются для исследования, начиная со строки 10 и далее. Строка 12 ограничивает популяцию только допустимыми путями (допустимыми являются длина и стоимость). Строка 14 сортирует возможные решения в порядке возрастания длины пути. Перед вставкой нового пути из множества A множество Парето P строка 14 сравнивает каждый возможный путь в A с элементами в P следующим образом:

1. Значения длины и стоимости допустимого пути в A больше, чем значения пути в P: отбросить допустимое решение.

2. Длина / стоимость допустимого пути в A меньше, чем у пути, который уже существует в P, но его значение стоимости / длины больше, чем у пути в P: добавить допустимое решение к множеству Парето.

3. И длины, и значения стоимости допустимого пути в A меньше, чем у пути R, который уже существует в P: добавить допустимое решение к P, отбросить путь R из P. Программа была реализована в пакете MATLAB (Multi_dijksta.m). В рассмотренном примере реализации задан граф, имеющий 8 узлов со следующей матрицей инциденций: h=[5 5 5 1 1 1 1 1;5 5 1 5 5 1 5 1;5 1 1 1 1 1 5 1;1 1 1 5 5 5 1 1;1 5 1 5 5 1 1 1;1 5 1 1 1 1 1 1;1 1 1 1 1 1 1 1;1 1 1 1 1 1 1 1]; Его графическое отображение получено с помощью встроенной функцииbiograph: H= view (biograph (h,[],'ShowWeights','on')).На рис. 14 показаны значения расстояния и стоимости для всех допустимых путей. Рисунок 14. Пример реализации модифицированного алгоритма Дейкстры.

Оптимальный в смысле Парето путь состоит из 8ребер с длиной пути от 11 до 14 единиц и стоимостью от 14 до 19 условных единиц. Множество допустимых решений в пространстве [расстояние стоимость], полученные с помощью упомянутой программы показаны на рисунке 15. Граница Парето на этом рисунке определяется нижнейправой огибающей. Самый короткий путь (11.071 единиц) имеет максимальную стоимость (19 у.е.). В таблице 2 перечислены длины и значения стоимости путей множества Парето. Таблица 2. Значения длины и стоимости оптимальных маршрутов Парето Длина (расстояние)Стоимость (условные единицы).

11.

71 911.

6718.

0312.

2517.

0112.

8215.

913.

4215.

71 414.

1Код для построения матрицы Парето является следующим: function S = buildMatrix (sizeMatrix) S = rand (sizeMatrix); for (y = 1: sizeMatrix) for (x = y: sizeMatrix) if (x==y)S (x, y) = 0; else if S (x, y)<=0.70 S (x, y) = 0; end S (y, x) = S (x, y); end end endРисунок 15. Расстояние и стоимость допустимых путей6. Сравнительная эффективность модифицированного алгоритма Дейкстры и алгоритма поиска А*Блок схема программы алгоритма поиска А* представлена на рис. 16. Рисунок 16. Блок-схема алгоритма А*Для численного эксперимента и сравнительных испытаний алгоритмов поиска кратчайших путей Дейкстры и А* были имитированы прогоны в широком диапазоне исходных данных: от 1 до 700 вершин. Для проведения этого эксперимента было было необходимо создание случайных графов. Для этого была написана функция buildMatrix (). Эта функция выполняется в 𝑂 (𝑛2) времени, где n равно числу узлов. Она необходима для расчета времени. function S = buildMatrix (sizeMatrix)S = rand (sizeMatrix);for (y = 1: sizeMatrix)for (x = y: sizeMatrix)if (x==y) S (x, y) = 0;elseif S (x, y)<=0.70 S (x, y) = 0;end S (y, x) = S (x, y);endendendВначале она создает матрицу размером [n x n] со случайными числами от 0 до 1 в качестве элементов. Элементы на диагонали матрицы были равны нулю.

Кроме того, элементы матрицы для неориентированных графов должны быть симметричны (𝑥, 𝑦) = 𝑤(𝑦, 𝑥). Поэтому команда if, управляющая вложенным циклом, анализирует, находится ли элемент по диагонали. Если да, то функция присваивает это значение равным нулю. Если элемент не находится по диагонали, то присваивается соответствующий элемент на другой стороне диагонали так, чтобы𝑤 (𝑥, 𝑦) = 𝑤 (𝑦, 𝑥).Каждый алгоритм компилируется один раз для каждого числа вершин от 1 до 700 (приведенная ниже программа progon. m). results=[]; for (i=1:3)for (n=2:10:702) randomMatrix = buildMatrix (n); i n tic; dijkstra (randomMatrix, i, n); DijkstraTime = toc; tic; Astar (randomMatrix, i, n); AstarTime = toc; results (n, 3*i-2) = n; results (n, 3*i-1) = DijkstraTime; results (n, 3*i) = AstarTime;endendresultsДо того, как число вершин будет увеличено, будет создана новая случайная квадратная матрица. Это позволяет рассчитывать длительность решения для новой топологии графа каждый раз с помощью предварительно заданная функция MATLAB «tic-toc». Данные о продолжительности хранятся в переменной Results. По окончании расчетов эти значения были импортированы в электронную таблицу Microsoft Excel, чтобы легко создавать графики и легко получать данные. В соответствии с этими экспериментальными результатами преимущества в быстродействии алгоритма А* перед алгоритмом Дейкстры начинают быть ощутимыми только в случае количества вершин графа, превышающем 450 вершин (рисунок 17).Кроме того потребности в памяти у алгоритма А* значительно выше, чем у алгоритма Дейкстры. Рисунок 17. Сравнительное исследование быстродействия алгоритмов Дейкстры (красная кривая) и алгоритма А* (синяя кривая) Следовательно, представленные данные позволяют утверждать, что использования модифицированного алгоритма Дейкстры в сравнении с алгоритмом поиска А* является эффективным для задач, имеющих количество вершин до 420. Если количество вершин графа более 500 алгоритм А* становится более эффективным в сравнении с алгоритмом Дейкстры.

Заключение

.

Выполненная работа обеспечивает инструмент решения оптимизации маршрутов для многокритериальных задач оптимизации маршрутов и описывает различные алгоритмы решения таких задач. Подобные задачи часто решаются путем свертки нескольких критериев к единой целевой функции или переформулировкой многокритериальной задачи как задачи с несколькими ограничениями одной целевой функцией. Подобные подходы являются, как правило, спорными и неоднозначными. Если задача имеет более одной цели, то они формируют множество Парето. Традиционная задача оптимизации планирования единственной целевой функции и единственного пути должна быть расширена до нескольких целей. При наличии нескольких весов ребер обычно нет единого оптимального пути, так как пути имеют разные затраты в разных весах. В классическом подходе вычисляются все оптимальные по Парето пути P, т. е., где для каждого другого пути P0 имеется по меньшей мере один из реберных весов, для которых P лучше, чем P0. При этом путь P доминирует над другим путем P0, если P0 не лучше в любом краевом весе.

Наиболее распространенным алгоритмом для вычисления всех паретооптимальных путей является обобщение алгоритма Дейкстры (Парето-Дейкстра). У него больше нет свойства установления узла, поскольку уже установленные узлы, возможно, придется обновлять снова, а несколько оптимальных по Парето путей к узлу представлены многомерными метками. Вычисление всех оптимальных по Парето путей, вообще говоря, NP-сложно, и на практике существует также множество оптимальных по Парето путей в дорожных сетях. В ходе выполнения работы была достигнута поставленная цель и решены частные задачи. При этом были получены следующие результаты:

проведен анализобзор литературных источников по методам поиска кратчайших путей методами теории графов;

изучены особенности постановки и методы решения многокритериальных оптимизационных задач;

реализован алгоритм Дейкстры оптимального построения маршрута как многокритериальной задачи для получения Парето-оптимального решения; проанализированы возможности альтернативных алгоритмов, в частности алгоритма оптимального построения маршрута A*.Список использованной литературы.

Валуев А. М. Модель многокритериального выбора основных проектных решений для глубоких карьеров // Научное обозрение. 2014. № 12. С. 76−80.Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М., 1978. Deo, N., Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, New Jersey, 1974.

Ху Т. Целочисленное программирование и потоки в сетях, М.: Мир, 1974. — 520 с. JOHNSON, D. E., and JOHNSON, J. E., Graph Theory with Engineering Applications, Ronald Press, New York, New York, 1972.

Филлипс Д., Гарсия-Диас А. Методы анализа сетей: пер. с англ. М. Мир, 1984. — 496 с. Hitchner, L. E., A C omparative Investigation of the Computational Efficiency of Shortest Path Algorithms, University of California, Berkeley, Operations Research Center, Report No.

ORC 68−17, 1968. Dreyyfus, S. E., A n Appraisal of Some Shortest-Path Algorithms, Operations Research, Vol.

17, pp. 395−412,1969.Gilsinn, J., and Witzgall, C., A Performance Comparison of Labelling Algorithms for Calculating Shortest Path Trees, National Bureau of Standards, Washington, DC, NBS Technical Note No.777, 1973. Golden, B., Shortest-Path Algorithms: A Comparison, Operations Research, Vol. 24, pp. 1164−1168,1976.Denardo, E., and Fox, B., Shortest-Route Methods, 1: Reaching, Pruning, and Buckets, Operations Research, Vol. 27, pp. 161−186, 1979. Bloniarz, P., A Shortest-Path Algorithm with Expected Time O (n2log n log* n), SlAM Journal on Computing, Vol. 12, pp. 588−600, 1983. Форд.

Л.Р., Фалкерсон Д. Р. Потоки в сетях.: пер. с англ.- М.: Мир, 1966, 356с. Moore, E. F., T he Shortest Path through a Maze, Proceedings of the International Symposium on the Theory of Switching, Part II, pp.

285−292, 1957; Annals of the Computation Laboratory of Harvard University, Harvard University Press, Cambridge, Massachusetts, Vol. 30, 1959. Bellman, R. E., O n a Routing Problem, Quarterly of Applied Mathematics, Vol.

16, pp. 87−90, 1958. Floyd, R. W., A lgorithm 97, Shortest Path, Communications of the ACM, Vol. 5, p.345, 1962.

Эвристики для поиска кратчайших путей [Электронный ресурс]. — Режим доступа:

http://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D0%BF%D1%83%D1%82%D0%B5%D0%B9. Дата обращения: 01.

03.2017 г. Эвристический поиск [Электронный ресурс]. — Режим доступа:

http://chernykh.net/content/view/293/493/. Дата обращения: 13.

03.2017 г. H art, P. A F ormal Basis for the Heuristic Determination of Minimum Cost Paths / P. H.

art, N. N ilsson, B. R.

aphael // IEEE Trans. S yst. S cience and Cybernetics. — 1968.

— № SSC- 4(2). — C. 100−107. 54 Koenig, S. I ncremental Heuristic Search in Artificial Intelligence / S.

K oenig, M. L ikhachev, Y. L.

iu, D. F urcy // Artificial Intelligence Magazine. — 2004. — № 25(2).

— C. 99−112. C ormen, Thomas H. I ntroduction to Algorithms Third Edition Thomas / Thomas H Cormen, Charles E. L.

eiserson, Ronald L. R ivest, Clifford Stein. — L.

dn.: T he MIT Press, 2009. — 1313 c. D.

eo, N. S hortest-path algorithms: Taxonomy and Annotation / N. D eo, C.

P ang // Networks. — 1984.

— № 14. — С. 275−323. Котов, А. Н. Метод минимизации суммарных затрат по развертыванию распределительных сетей на основе модифицированного метода Дейкстры [Электронный ресурс] / А. Н. Котов. — СПб.

: СПбГУТ им. проф. М.А. Бонч-Бруевича, 2007. — Режим доступа:

http://jurnal.org/articles/2007/radio4.html. Дата обращения: 26.

03.2017 г.

http://elib.spbstu.ru/dl/2/v16−1652.pdf/download/v16−1652.pdf?lang=en Задача о кратчайшем пути. Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути Алгоритм Дейкстры. Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры.

Алгоритм Беллмана-Форда. Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Белмана_Форда.

Алгоритм А*. Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Алгоритм_поиска_А*Алгоритм D*. Электронный ресурс. Режим доступа:

http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_D*Алгоритм Флойда-Уоршелла. Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Алгоритм_Флойда-Уоршелла.

Алгоритм Джонсона. Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Алгоритм_Джонсона.

Алгоритм Ли (Волновой алгоритм). Электронный ресурс. Режим доступа:

https://ru.wikipedia.org/wiki/Алгоритм_ЛиАлгоритм А* для новичков [Электронный ресурс]. — Режим доступа:

http://www.policyalmanac.org/games/aStarTutorial_rus.htm. Дата обращения: 25.

04.2017 г. Алгоритм поиска пути Jump Point Search [Электронный ресурс]. — Режим доступа:

http://habrahabr.ru/post/162 915/. Дата обращения: 26.

04.2017 г.