Shortest path on a graph where distances change dynamically? (maximum energy path)

Идея

Я предлагаю алгоритм, который строит вспомогательное дерево (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).

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

Для 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.

Возможно следующее сработает:

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

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

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

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

Значит, вам совершенно наплевать на общую длину пути, верно? Просто минимальное значение, которое вы встретите на пути?

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

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

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

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

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

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

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

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

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

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

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

Два варианта.

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

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

14 if alt < dist[v]: // Relax (u,v,a)

15 dist[v] := alt

16 previous[v] := u

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

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