Минимальная сумма множественного пути источника-получателя

Question

Учитывая неориентированный и невзвешенный график, я хочу узнать минимальную сумму k пары пути источника-источника при ограничении, что каждая вершина используется не более одного раза.

Например, следующий график с двумя парами назначения-источника (A, E) и (B, F) имеет минимальную сумму в 7 шагов. То есть (A> G> H> I> E) = 4 шага и (B> C> D> F) = 3 шага.

http://i.imgur.com/W4uNiac.png

Очевидно, что жадный метод нахождения все эти к траектории последовательно приведет к неоптимальному раствору. Например, существует решение из 8 шагов с (A> C> D> E) = 3 шага и (B> J> K> L> M> F) = 5 шагов.

Я рассмотрел вопрос о моделировании этой проблемы в проблеме минимальной стоимости максимального расхода. Однако не всегда можно различать такую ​​пару с несколькими источниками. Например, если k = 2 и две пары (A, B) и (C, D), решение, использующее MCMF, может привести к (A> ...> D) и (B> ...> C) в какой-то ситуации, которая, по-видимому, не является решением, которое я хочу.

Есть ли какие-либо идеи по этой проблеме?

Заранее благодарен! :)

Answer 1

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

Я буду называть ваши к пути агентов помочь описать решение.

Основная идея заключается в том, что вы используете двоичное дерево поиска для поиска решения. Начните с поиска самого короткого пути для каждого из агентов k. Затем вы проверяете, есть ли у вас какие-либо столкновения между агентами в разрешенных путях. Когда вы найдете узел, разделенный двумя путями, вы введете дерево в дерево. В правой части дерева первому агенту запрещено использовать этот узел. В левой части дерева второму агенту запрещено использовать узел. Затем агент, которому было предоставлено новое ограничение, требуется для повторного поиска без использования данного узла.

Узлы в дереве расширены в лучшем порядке в соответствии с общей стоимостью пути всех агентов. Когда вы найдете решение, оно гарантировано будет оптимальным.

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

Если я должен был догадаться, проблема в NP-Hard или NP-Complete - легко проверять решения, но данный алгоритм работает в экспоненциальном времени.