Нахождение общего кратчайшего пути на плотном графе

Question

Скажем, вы компания по доставке посылок с фиксированным начальным местоположением на карте.Вы должны доставить 40 пакетов, но у вас есть неограниченное количество водителей, неограниченный бензин, и единственное ограничение заключается в том, что вы хотите набрать наименьшее количество миль от общего количества транспортных средств, и каждое транспортное средство может вмещать 16 пакетов.Грузовики могут разгоняться до 18 миль в час и начинать в 8:00

1002 *. В какой-то момент в графике доставки одному пакету будет назначен адрес.

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

Я, наверное,задумавшись над этим, но может ли кто-нибудь указать мне правильное направление?

Answer 1

Эта проблема, к сожалению, является NP-сложной, а это означает, что на данный момент у нас нет никаких алгоритмов для нее, которые, как известно, являются эффективными в худшем случае, детерминистическими и всегда правильными.То есть у нас нет чего-то вроде алгоритма Дейкстры или A *, который мы могли бы просто снять с полки и гарантировать быстрый быстрый оптимальный результат.

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