@dimentimor

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

Другими словами, если есть 100 магазинов и 10 курьеров, как распределить магазины между курьерами, что бы каждый из них прошел примерно одинаковое расстояние?
  • Вопрос задан
  • 39 просмотров
Решения вопроса 1
@crazywu
Задача коммивояжёра, дополненная несколькими курьерами. Не ожидайте найти быстрых, красивых решений NP-полной задачи.
Но, в какой-то мере вам могли бы помочь:
-поиск подходов к выбору курьера для точки на основе динамического программирования.
-предварительное разбиение графа на сообщества по расстоянию.
-любые допустимые упрощения исходных данных (уж не знаю вашей специфики).
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы