Найти кратчайший маршрут с путевыми точками, используя матрицу расстояний

Question

Я хочу получить кратчайший маршрут между точками A и B с промежуточными точками X между ними, используя Google Maps v3.

В этом примере, скажем, я хочу рассчитать кратчайший маршрут между A и B с помощью C, D, E путевые точки между ними.

Для этого я использую службу матрицы расстояний, чтобы найти расстояние между [AB, AC, AD], [BC, BD, BE], [CD, CE], [DE] с результатами ниже:

A) Адрес A [B: 4, C: 1.4, D: 1.4] Всегда начало маршрута

B) Адрес B [C: 3,8, D: 1,3, E: 3,1]

C) Адрес C [D: 1,2, E: 3,1]

D) Адрес D [E: 2,7]

E) Адрес E - Всегда конец маршрута

Маршрут 1: A + B + C + D + E = 4 + 3,8 + 1,2 + 2,7 = 11,7 км / сек

Маршрут 2: A+ C + B + D + E = 1,4 + 3,8 + 1,3 + 2,7 = 9,2 км

Маршрут 3: A + D + B + C + E = 1,4 + 1,3 + 3,8 + 3,1 = 9,6 км

Маршрут: A + B + D + C + E = 4 + 1,3 + 1,2 + 3,1 = 9,6 км

Маршрут 5: A + C + D + B + E = 1,4 + 1,2 + 1,3+ 3.1 =7 км

маршрут 6: A + D + C + B + E = 1,4 + 1,2 + 3,8 + 3,1 = 9,5 км

В этом случае победителем становится маршрут 5, но у меня естьтри вопроса:

1. Является ли это самоубийством с точки зрения выставления счетов Google Maps с большими объемами?Принимая во внимание, что маршруты будут иметь максимум 12 адресов, включая как начальный, так и конечный адреса.

2. это самоубийство с точки зрения производительности JavaScript?

3. Есть ли лучший способ решить эту проблему?

Заранее спасибо

Answer 1

Как насчет этого:

Хранить списки всех расстояний (скажем, A -> F, со средними точками B, C, D и E):

A: AB, AC, AD, AE
B: BC, BD, BE, BF
C: CB, CD, CE, CF
D: DB, DC, DE, DF
E: EB, EC, ED, EF

Допустим, мы сортируем их в соответствии с расстояниями.

Из A выберите кратчайшее расстояние (допустим, это AC).

Из C выберите кратчайшее расстояние до другогосредняя точка (CE?)

Повторите это и получите что-то вроде ACEBDF.Сохраните это расстояние как d_min.

Вернитесь назад и попробуйте другой путь.Первое, что мы можем изменить, это EB, который мы можем изменить на ED.ACEDB длиннее, чем ACEBDF?Если это так, вернитесь назад и попробуйте ACB.Если нет, протестируйте ACEDBF с d_min.

И так далее - это потенциально спасет вас от более длинных маршрутов, и найдет самый короткий, хотя он может проверить все перестановки.Однако я не думаю, что существуют более быстрые способы сделать это.