Алгоритм обхода нескольких локаций с нахождением кратчайшего маршрута
Я создаю программу для туристов. Они покинут отель и пойдут, скажем, в 3 разных места (B, C, D). Мне нужно найти кратчайший путь к точкам пересечения B, C и D. Конечная точка не важна, это может быть любой из них.
Можно Алгоритм Дейкстры сделай это?
Мне нужно реализовать алгоритм с использованием PHP.
Решение
Алгоритм Дейкстры может решить эту проблему. Я не уверен, что это оптимально. Но, по крайней мере, это решает вашу проблему. В худшем случае вы можете перечислить все ордера, с которыми вы достигнете каждого узла (т.е. BCD, BDC, CDB, CBD, DBC, DCB). Затем запустите алгоритм Дейкстры, чтобы получить кратчайший путь. Принять заказ BCD например, запустить Dijkstra’s, чтобы получить самый короткий из отеля в B, от B в Cнаконец из C в D, суммируйте их, чтобы получить кратчайший путь для этого заказа. Самый короткий из всех заказов — оптимальное решение вашей проблемы.
Другие решения
Других решений пока нет …