Блог

Главная - Вопросы по программированию - Алгоритм обнаружения ключевых точек на дороге

Алгоритм обнаружения ключевых точек на дороге

#algorithm

#алгоритм

Вопрос:

У меня проблема с алгоритмом обнаружения точек, которые находятся на дороге между точками источника и назначения.

Пример участка дороги с отмеченными ключевыми точками

Для этого есть несколько предположений:

  1. Начиная с p0 (начальной точки) Я хочу переместиться в pk (пункт назначения)
  2. У меня есть ограничения по времени и расстоянию
  3. Все ключевые точки (p1, p2, p3, …, pn) имеют соответствующий им вес (прибыль) (w1, w2, w3, …, wn)

Вопрос в том, как определить, какие точки являются наиболее прибыльными? Когда я выбираю некоторые точки, я хотел бы спросить Google navigation API, выполняются ли ограничения, но запросы стоят дорого, поэтому для меня было бы лучше не выполнять многие из них.
Знаете ли вы какой-либо алгоритм, предназначенный для решения такой проблемы?

— ПРАВКА 1—

Если я хорошо вас понял, я должен преобразовать свою проблему в график.

Преобразование реальной дорожной задачи в график

Тем не менее, я не знаю алгоритма, который позволяет мне решить эту проблему.
Это двусторонний график (исключая подключение к точкам p0 и pk). Я хотел бы максимизировать прибыль и сохранить ограничения по расстоянию. Знаете ли вы какой-либо формальный алгоритм, который мог бы мне в этом помочь?

Примерами путей могут быть:
p0->3->2->1-> pk
p0->1->pk

Комментарии:

1. Есть ли какая-либо причина, по которой Дейкстра здесь не сработал бы?

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

3. Дейкстра работает для graph. Вот ситуация, когда у меня есть реальная дорога. Я знаю только расстояния по прямой между точками, но не реальные. Чтобы узнать реальное расстояние, я должен отправить запрос в Google, но я бы хотел избежать этого, запрашивая все дороги.

4. @NicoSchertler Есть ли у вас какие-либо предложения, как приблизить реальное расстояние между двумя координатами? Важно то, что расстояние между точками может быть очень маленьким (0,5 км)

5. Просто прямое расстояние, измеренное по воздуху.