Как найти кратчайший путь в графе эвристическим алгоритмом?

Question

[JunPupil]

Здравствуйте,
взвешенный неориентированный граф задается матрицей смежности. нужен эвристический алгоритм для поиска кратчайшего пути между двумя точками. Разбирался в A* и в муравьях, в итоге ничего путного не вышло.

Comments

[tsarevfs]

Что значит не вышло путного? Долго? Если да, то какие ограничения у вас? Граф из точек на плоскости (как карта дорог например) чтобы A* применять?

[JunPupil]

tsarevfs: не вышло ничего путного = не понял, как и почему он вообще работает, и следовательно не смог написать программу.
да, на плоскости(задан квадратной матрицей)

[Станислав Макаров]

JunPupil A* работает потому, что он информированный (https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D..., т.е. у него есть дополнительная информация, которая МОЖЕТ помочь быстрее найти лучший маршрут.
Вообще, "не понял почему он работает" не лучшее обоснование необходимости искать что-то еще.

[JunPupil]

Станислав Макаров: немного не так. я не понимаю, как он работает и даже не против в нем разобраться. но на графе я не могу понять, как выбирать приоритетную очередь

[Станислав Макаров]

JunPupil вы должны понимать это исходя из вашей предметной области. Вот одна из "предметных областей" - это плоскость, на которой можно прикинуть расстояние между узлами за счет того, что они расположены не абы как, а двумерной сеткой. Это и есть эвристика. С другими графами и эвристики будут другие. Если у вас в принципе нет никакой доп. информации о природе графа, то и нет смысла заморачиваться с информированными алгоритмами - очередь с приоритетами выродится в обыкновенную очередь, т.к. функция эвристики h(x,y) выродится в константу (в самом общем случае - в ноль).

[JunPupil]

Станислав Макаров: так-то оно так, но я даже не понял, как для кратчайшего пути между двумя точками написать жадный алгоритм

Answer 1

[uvelichitel]

Простейшая эвристика - найдите какой нибудь путь и оптимизируйте его пока не надоест

Answer 2

[AtomKrieg]

www.redblobgames.com
Здесь примеры поиска пути

Comments

[JunPupil]

на плоскости понятно, как задать эвристическую функцию, но как это сделать на графе?

[AtomKrieg]

JunPupil: положите его на плоскость так чтобы связи не пересекались и используйте евклидову дистанцию

Answer 3

[SeptiM]

Начните с простого, с Дейкстры: e-maxx.ru/algo/dijkstra

Comments

[JunPupil]

Дейстру и флоида-уоршелла написал. С этим проблем не возникло

[SeptiM]

А что вы хотите? Т.е. какая конкретная цель?

[JunPupil]

SeptiM: как и написано выше, решить ту же задачу с помощью эвристики

[tsarevfs]

JunPupil: A star очень похож на дейкстру. Та же очередь, только приоритетная. В том смысле что мы сначала пытаемся посмотреть на те вершины, которые ближе к нашей цели.

[JunPupil]

tsarevfs: но как на графе понять, какая вершина ближе?

[tsarevfs]

JunPupil: У вас должна быть дополнительная информация. Например для сетки -- каждая вершина это ячейка с координатами x, y. Расстояние до цели r = sqrt((x - x_end)^2 + (y - y_end)^2). Корень можно выкинуть из-за его монотонности. В случае с дорожными картами аналогично есть координаты вершин.

Answer 4

[Ai Lab]

ЭВРИ́СТИКА -Совокупность исследовательских методов, способствующих открытию ранее неизвестного.
То есть "эвристический" это такой метод который "чтото умное и полезное делает", то есть ничего конкретного. Как уже сказал uvelichitel начните с любого алгоритма, потом ищите более оптимальные пути, как это уже другой вопрос.