Как найти кратчайший путь в графе эвристическим алгоритмом?
Здравствуйте,
взвешенный неориентированный граф задается матрицей смежности. нужен эвристический алгоритм для поиска кратчайшего пути между двумя точками. Разбирался в A* и в муравьях, в итоге ничего путного не вышло.
tsarevfs: не вышло ничего путного = не понял, как и почему он вообще работает, и следовательно не смог написать программу.
да, на плоскости(задан квадратной матрицей)
JunPupil A* работает потому, что он информированный (https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D..., т.е. у него есть дополнительная информация, которая МОЖЕТ помочь быстрее найти лучший маршрут.
Вообще, "не понял почему он работает" не лучшее обоснование необходимости искать что-то еще.
Станислав Макаров: немного не так. я не понимаю, как он работает и даже не против в нем разобраться. но на графе я не могу понять, как выбирать приоритетную очередь
JunPupil вы должны понимать это исходя из вашей предметной области. Вот одна из "предметных областей" - это плоскость, на которой можно прикинуть расстояние между узлами за счет того, что они расположены не абы как, а двумерной сеткой. Это и есть эвристика. С другими графами и эвристики будут другие. Если у вас в принципе нет никакой доп. информации о природе графа, то и нет смысла заморачиваться с информированными алгоритмами - очередь с приоритетами выродится в обыкновенную очередь, т.к. функция эвристики h(x,y) выродится в константу (в самом общем случае - в ноль).
JunPupil: A star очень похож на дейкстру. Та же очередь, только приоритетная. В том смысле что мы сначала пытаемся посмотреть на те вершины, которые ближе к нашей цели.
JunPupil: У вас должна быть дополнительная информация. Например для сетки -- каждая вершина это ячейка с координатами x, y. Расстояние до цели r = sqrt((x - x_end)^2 + (y - y_end)^2). Корень можно выкинуть из-за его монотонности. В случае с дорожными картами аналогично есть координаты вершин.
ЭВРИ́СТИКА -Совокупность исследовательских методов, способствующих открытию ранее неизвестного.
То есть "эвристический" это такой метод который "чтото умное и полезное делает", то есть ничего конкретного. Как уже сказал uvelichitel начните с любого алгоритма, потом ищите более оптимальные пути, как это уже другой вопрос.
