Кратчайший путь между тремя точками
На графике мне нужно найти кратчайший путь между двумя точками и по пути посетить одну контрольную точку. Также я могу посетить каждую вершину только один раз. Я предполагаю, что это как-то связано с сетевым потоком, но я понятия не имею, как это реализовать.
1 ответ
Вы можете смоделировать его целиком как проблему потока с минимальными затратами. Вы хотите перейти от A к B через C без использования вершины дважды. Вы можете смоделировать его как поток от A до C (товар 1) и поток от B до C (товар 2). Чтобы избежать двойного использования узла, вы должны выполнить следующий трюк на всех ваших узлах (в вашей модели):
Учитывая узел X с p входящими и t исходящими ребрами, вы создаете новый узел Y и перепишите связи. Все входящие ссылки p будут приходить в X, исходящие ребра q будут отходить от Y. Добавьте только 1 ссылку (L) из X в Y. Если установить емкость L-link равной 1, будет использоваться только каждый узел. один раз.
Затем вы можете записать его как (M)ILP и решить его. ILP даст вам правильное решение, если оно существует. В зависимости от вашего приложения, это может быть излишним. Если вам нужна быстрая эвристика, просто используйте 2 A* поиска и надейтесь, что они не пересекаются.