17

Допустим, мы едем с 1 по 5. Самый короткий маршрут будет 1-4-3-5 (всего: 60 км).

график

Мы можем использовать алгоритм Дейкстры для этого.

Теперь проблема в том, что самый короткий маршрут не всегда самый быстрый из-за пробок или других факторов.

Например:

Известно, что 1-2 часто бывают пробки, поэтому его следует избегать.
Внезапно происходит автомобильная авария на 4-3, поэтому ее тоже следует избегать.
И т.д...

Так что, вероятно, мы можем ускоряться на маршруте 1-4-5 из-за отсутствия пробок / аварий, поэтому мы прибудем на 5 быстрее.

Ну, это общая идея, и я пока не думаю о более подробной информации.

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

graph dijkstra anta40
источник

3

Это домашнее задание? Разве это не просто en.wikipedia.org/wiki/Travelling_salesman_problem для обхода взвешенного графика?

StuperUser

9

@StuperUser: Нет, TSP - это схема всех узлов без дубликатов. Например, нет необходимости попадать в узел 2, например.

Дэвид Торнли

2

@ ДэвидТорнли, я вижу. То есть Дейкстра для кратчайшего маршрута на взвешенном графике? И TSP посещает каждый узел?

StuperUser

1

@Stuper: кратчайший путь, да

BlueRaja - Дэнни Пфлюгофт

2

@StuperUser, только к вашему сведению, TSP - сильно NP-полная проблема, решение которой не может быть выполнено за полиномиальное время. ... Итак, теперь вы знаете.

riwalk

5

Так как вы привели к застою в картине, будьте осторожны, вы не попадетесь под парадокс Брасса . Если каждый выберет оптимальный путь, это приведет к худшему времени в пути для всех.

Майкл Браун
источник

49

Да, Дейкстра

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

Мартин Йорк
источник

9

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

Мартин Беккет

6

Хотя Dijsktra подойдет, я обычно выбираю A * для любой серьезной работы по поиску пути; Эвристика очень поможет.

Мирча Chirea

6

Ссылка: * алгоритм поиска . Это расширение метода Дейкстры.

mgkrebbs

Пока существует применимая эвристика, A * будет превосходить Дейкстру (с точки зрения производительности).

Bummzack

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

pwny

16

Да. Алгоритм Дейкстры решит эту проблему.

Проблема в вашем случае заключается в том, что вы автоматически предполагаете, что кратчайший путь равен пройденному расстоянию, тогда как на самом деле он более уместно соответствует СТОИМОСТИ прохождения маршрута.

Если у одного пути есть контрольно-пропускной пункт, тогда его COST должен быть выше, и алгоритм все еще применяется.

maple_shaft
источник

Да, извините, если я не использовал правильную формулировку. Я имею в виду «самый удобный маршрут» (с минимальными затратами)

anta40

11

Вы должны просто иметь возможность заменить свое расстояние временем между узлами и решить его таким же образом.

DKnight
источник

10

Дейкстра

Как уже было сказано, он используется не только для кратчайшего расстояния. Я считаю, что эта анимация дает хорошее представление о «силе» (из-за отсутствия лучшего слова) Дейкстры:

Дейкстра

динамический
источник

Алгоритм определения самого быстрого маршрута?

Ответы:

Дейкстра