Несколько дней назад кто-то спросил меня: если у нас есть какие-то агенты в нашей среде, и они хотят перейти от своих источников к месту назначения, как мы можем найти общий кратчайший путь для всех них так, чтобы у них не былоконфликт во время их обхода.
Проблема заключается в том, что все агенты одновременно ходят в среде (которая может моделироваться неориентированным взвешенным графиком), и у нас не должно быть никаких столкновений.Я думал об этом, но я не мог найти оптимальный путь для всех них.Но, конечно, есть слишком много эвристических идей для этой проблемы.
Предположим, входные данные представляют собой граф G (V, E), m агентов, которые находятся в: S 1 , S 2 , ..., S m узлов графа при запуске, и они должны перейти в узлы D 1 , ... D m в конце.Также может быть конфликт в узлах S i или D i , ... но эти конфликты не важны, они не должныу них не может быть конфликта, когда они находятся во внутренних узлах своего пути.
Если их путь не должен иметь одинаковый внутренний узел, он будет иметь вид k-disjoint paths
проблема в том, что NPC, но в этом случае пути могут иметь одинаковые узлы, но агент не должен находиться в одном узле в одно и то же время.Я не знаю, могу ли я сказать точное постановка проблемы или нет.Если сбивает с толку, скажите мне в комментариях, чтобы отредактировать его.
Существует ли какой-либо оптимальный и быстрый алгоритм (под оптимальным я подразумеваю сумму длин всех путей как можно меньше, а под быстрым я имею в виду хороший алгоритм за полиномиальное время).