Найти непересекающийся граф с наименьшей общей стоимостью

Question

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

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

Большое спасибо!

Answer 1

Мне кажется, что вы описываете проблему маршрутизации транспортного средства, где каждый маршрут ограничен, например, по вместимости автомобиля или максимальному времени в пути. Посмотрите на https://en.wikipedia.org/wiki/Vehicle_routing_problem.