Матрица расстояния Генетический алгоритм на Android
Я делаю приложение для маршрутизации на Android, когда пользователь может ввести количество часов для поездки, а мое приложение выдаст вывод о возможных маршрутах, по которым могут путешествовать пользователи.
Я использую генетический алгоритм (GA), чтобы указать маршрут для пользователя, и использую PHP для выполнения моей GA.
Здесь возникает проблема, для того, чтобы маршрутизация была эффективной, мне нужно знать расстояние между каждым городом, чтобы проверить, возможен ли маршрут, а расстояние минимизировано. Как сохранить расстояние между каждым городом, чтобы ускорить выполнение? Я пытался получить расстояние непосредственно
из Google Maps API, но это занимает больше времени выполнения.
Я думал сохранить расстояние до файла JSON, но возможно ли это? Или есть другие эффективные способы?
Обратите внимание, что пункт назначения будет динамическим. Пользователи могут добавить новый пункт назначения, поэтому при появлении нового пункта назначения матричное расстояние необходимо обновлять.
Пожалуйста, помогите мне 🙂 Спасибо.
Решение
Вы знаете начальную позицию пользователя и хотите знать различные расстояния до пункта назначения. Я предлагаю вам использовать один источник детерминированного алгоритма кратчайшего пути, как Дейкстра вместо эволюционного алгоритма. Реализация, основанная на очереди с минимальным приоритетом, реализованной в куче Фибоначчи, работающей в O (E.logV), где E — это число ребер, а V — количество вершин. Он работает намного быстрее, чем генетический алгоритм, а также находит лучший ответ вместо приблизительного. У этого также есть свойство, которое находит первые ближайшие пункты назначения сначала, которое подходит для Вас.
Другие решения
Других решений пока нет …