Кратчайший путь на графике, где расстояния изменяются динамически? (максимальный путь энергии)

Question

Я пытаюсь найти кратчайший путь между двумя максимумами в дискретном энергетическом ландшафте, где кратчайший путь - это тот, который уменьшает наименьшую высоту в течение всего пути.Вероятно, путь максимальной энергии является более правильной терминологией, но, другими словами, даже если путь проходит большое расстояние вокруг ландшафта, но не спускается в долины, это будет считаться хорошим.

Моя первоначальная идея состояла в том, чтобы создать график ландшафта, в котором вес был бы разницей в высоте ландшафта между соседями, либо положительным, либо отрицательным для подъема и спуска соответственно.Я только что понял, что это не даст нужный мне результат, и фактически все пути между локальными максимумами будут иметь одинаковую стоимость.

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

Итак, существуют ли алгоритмы поиска в графе, в которых расстояние может динамически изменяться при исследовании путей?

Или есть другие предложения для решения этой проблемы?

Answer 1

Эта проблема известна как проблема кратчайшего пути в узком месте.Это на самом деле проще, чем проблема кратчайшего пути, и может быть решено за линейное время на неориентированных графах.См. Например здесь .

Answer 2

Идея

Я предлагаю алгоритм, который строит вспомогательное дерево (T), в котором каждый узел содержит список вершин. Каждое поддерево будет содержать набор вершин, отделенных от остальной части графа долиной. Чтобы найти расстояние между любыми двумя узлами, нужно просто найти их самого низкого общего предка в дереве.

Алгоритм

Инициализация:

1. Сортировка вершин по возрастанию (пробел: O(V), время: O(V log V))
2. Пусть T состоит только из корневого узла r

MakeTree(G, r)

1. Возьмите самую низкую вершину в графе G, удалите ее из графа и добавьте в список в корне r (стоимость времени на вершину: O(1 + E/V))
2. Повторите вышеуказанный шаг, пока график подключен
3. Для каждого подключенного компонента G' графика G:
   1. создайте новый узел n в T, присоедините узел как дочерний элемент корня
   2. рекурсивный запуск MakeTree(G', n)

Теперь у вас есть дерево с таким свойством, что, если вы хотите перейти от вершины A к B, ваш путь максимальной энергии будет проходить через самую высокую из вершин, хранящихся в самом низком общем предке A и B. Чтобы найти расстояние, просто найдите наименьшего общего предка и возьмите наивысшую сохраненную там вершину C и вычислите max(abs(h(A) - h(C)), abs(h(B) - h(C))).

* * Пример тысяча сорок-девять

Ниже приведен пример графика и соответствующего дерева (для краткости метки вершин являются их высотами). Например, если вы хотите перейти с 22 на 14, вам нужно пройти через 10 (самая высокая вершина у самого низкого общего предка в дереве, расстояние = 22 - 10). Если вы хотите перейти с 22 на 20, вам нужно пройти через 13 (расстояние = 22 - 13).

Answer 3

То есть вас не волнует общая длина пути, верно? Какое минимальное значение, которое вы встретите на пути?

Если это так, то вам не следует использовать «расстояние» в традиционном смысле как стоимость Дейкстры. Ваша очередь приоритетов должна возвращать узел с самым высоким значением энергии - таким образом, вы гарантированно никогда не пройдете путь через более низкое значение, если существует лучший путь.

Я полагаю, что это отличается от того, что предлагает Пол Ханкин в своем ответе. Это, вероятно, откроет много узлов в графе; Я думаю, что вы можете оптимизировать следующим образом:

1. Используйте расстояние [Евклидов или Манхэттен] до цели в качестве тай-брейка в функции сравнения. Таким образом, если два узла имеют одинаковую энергию, вы попробуете тот, который быстрее достигает цели.

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

3. Начало поиска с нижних локальных максимумов (я не уверен, но думаю, что это будет быстрее).

Использование расстояния в качестве разрыва связи в # 1 не повлияет на минимальную энергию, но должно заставить вещи работать быстрее (это похоже на поиск A *).

---

Редактировать: вот совершенно другой (но, вероятно, более медленный) способ думать.

Сначала выберите пороговую энергию. Выполните стандартный поиск Dijkstra / A *, но отклоните все узлы, энергия которых ниже порога. Если у вас нет пути, выберите больший порог и попробуйте снова. «Безопасным» начальным предположением будет минимум E на простом пути (например, идти налево, затем идти вверх) от начала до цели.

Теперь увеличьте порог и повторите Dijkstra / A *. Продолжайте, пока не найдете путь. Последний путь, перед которым вы больше не можете найти путь, - это кратчайший путь с наибольшей минимальной энергией на пути.

Вы также можете повторно использовать стоимость пути из одного поиска в качестве улучшенной эвристики A * для следующего поиска. Поскольку увеличение порога только увеличит длину путей, это допустимая эвристика .

---

Надеюсь, это поможет. Дайте мне знать, если что-то неясно.

Answer 4

Учитывая, что конечные точки в максимумах, ваша проблема эквивалентна этой:

Для x на графике пусть h (x) будет расстоянием ниже начальной точки. (По постановке задачи все точки находятся ниже начальной точки).

Найдите путь, который минимизирует: max (h (x) для x в пути).

Вы можете использовать вариант кратчайшего пути Дейкстры для решения этой проблемы. Я скопировал и изменил описание алгоритма из Википедии (изменяется только вычисление расстояния на шаге 3).

1. Назначьте каждому узлу значение расстояния. Установите его в ноль для нашего начального узла и в бесконечность для всех остальных узлов.

2. Пометить все узлы как не посещенные. Установить начальный узел как текущий.

3. Для текущего узла рассмотрите все его не посещенные соседи и вычислите их предварительное расстояние (от начального узла). Например, если текущий узел (A) имеет расстояние 6 и подключен к другому узлу (B) с h (B) = 7, расстояние от B до A будет max (6, 7) = 7. Если это расстояние меньше ранее записанного расстояния (бесконечность в начале, ноль для начального узла), перезаписать расстояние.

4. Когда мы закончим с учетом всех соседей текущего узла, отметьте его как посещенный. Посещенный узел больше не будет проверяться; записанное в настоящее время расстояние является окончательным и минимальным. Если все узлы были посещены, закончите. В противном случае установите не посещаемый узел с наименьшим расстоянием (от начального узла) в качестве следующего «текущего узла» и продолжайте с шага 3.

Answer 5

Может быть, следующие работы:

Создание графика ландшафта с весами dist + abs (height_a - height_b).

Функция abs делает подъем или падение дорогостоящим, и, как вы уже заметили, одной разницы в высоте недостаточно, поскольку она постоянна для любых двух точек на карте независимо от того, по какому маршруту вы идете .

dist - это обычное расстояние (или даже постоянная 1 во всех случаях), которое может быть опущено, но если вы хотите получить short путей, это должно быть предпочтительным для short по длинному с другими такими же затратами. 1011 *

Конечно, это не проверено. : -)

Answer 6

Две возможности.

а) Например, в версии http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm есть линия, которая определяет возможно улучшенное расстояние до точки v, используя маршрут через точку u:

alt: = dist [u] + dist_between (u, v)

14, если alt

15 dist [v]: = alt

16 предыдущий [v]: = u

Вы, кажется, хотите версию, которая идет alt: = K - min (высота [u], высота [v]). Это работает по той же причине, что и версия с дополнением: в любое время для набора вершин, удаленных из Q, все минимальные затраты корректно рассчитываются для любого маршрута из источника. Каждый раз, когда вы удаляете вершину из Q, так как вы удаляете вершину с минимальным расстоянием, нет шансов на ее сокращение, используя другие вершины, все еще в Q.

б) Возьмите любой метод для разработки, если есть маршрут от источника. Используйте график, который содержит только точку с высотой> = H и посмотрите, есть ли решение. Попробуйте различные H, пока не найдете тот, который просто работает. Вы можете отсортировать все высоты заранее, а затем использовать двоичный метод chop для этого массива.