Какие бывают алгоритмы по нахождению оптимального пути?

Question

[Alexey]

Подскажите пожалуйста существуют ли алгоритмы по нахождению оптимального маршрута, если вес имеют и дуги(пути) и вершины(точки). Например, есть 10 точек на карте, за посещении каждой точки будет начислены балы, количество балов зависит от конкретной точки. Про алгоритмы Дейкстры, Уоршелла слышал, про транспортную задачу слышал, но не могу понять а что делать если вес имеют не только дуги но и вершины?!

Answer 1

[Владимир Олохтонов]

Кажется, что это на самом деле не очень важно, если говорить об алгоритме Дейкстры. Достаточно при проходе очередного ребра помимо добавления его веса, так же добавлять вес его парной вершины (ведь ребро всегда соединяет 2 вершины).

А что за задача, где требуется учитывать и веса рёбер и веса вершин? Какая-то учебная или порожденная реальным миром? :)

Comments

[Alexey]

Учебная, оптимизация маршрутов для мусороуборочной техники основываясь на заполненности контейнеров.

[Владимир Олохтонов]

Alexey: А не лучше ли будет использовать рюкзак + дейкстра? У вас веса в вершинах и ребрах имеют разный смысл, их нельзя напрямую складывать друг с другом.

[Alexey]

Владимир Олохтонов: кажется, это имеет смысл, спасибо.

[Владимир Олохтонов]

Alexey: Пометьте правильным ответом ;)

[pi314]

Владимир Олохтонов: Зато, наверное, можно бы было отнимать ;) Если мусоровозки "резиновые", то сводится к: найти путь из А в Б, на котором соберется максимум мусора за минимум расстояния. Если тупо (ну, или, умно - с каким-нибудь коэффициентом) отнимать вес узлов от веса ребер, то решается одним поиском, без рюкзака. Если не "резиновые", то, конечно, рюкзак... А еще интереснее станет, если "чем больше загружена мусоровозка, тем больше она тратит бензина" )))

Answer 2

[Александр Скуснов]

Муравьиный алгоритм