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

Question

[Ди Ма]

Другими словами, если есть 100 магазинов и 10 курьеров, как распределить магазины между курьерами, что бы каждый из них прошел примерно одинаковое расстояние?

Answer 1

[crazywu]

Задача коммивояжёра, дополненная несколькими курьерами. Не ожидайте найти быстрых, красивых решений NP-полной задачи.
Но, в какой-то мере вам могли бы помочь:
-поиск подходов к выбору курьера для точки на основе динамического программирования.
-предварительное разбиение графа на сообщества по расстоянию.
-любые допустимые упрощения исходных данных (уж не знаю вашей специфики).

Comments

[Ди Ма]

А что вы имеете в веду "поиск подходов к выбору курьера для точки на основе динамического программирования"?

[crazywu]

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

Ну и на всякий случай что такое динамическое программиррование