На графике мне нужно найти кратчайший путь между двумя точками и по пути посетить один контрольный пункт. Кроме того, я могу посещать каждую вершину только один раз. Полагаю, что это связано с сетевым потоком, но я не знаю, как это реализовать.Самый короткий путь между тремя точками
Вы можете смоделировать его целиком как проблему с минимальными затратами на пропускную способность с несколькими продуктами. Вы хотите перейти от A к B через C, не используя двойную вершину дважды. Вы можете моделировать его как поток от A до C (товар 1) и поток от B до C (товар 2). Чтобы избежать одновременного использования узла, вам необходимо выполнить следующий трюк на всех ваших узлах (в вашей модели):
Для узла X с входящими и исходящими краями p вы создаете новый узел Y и переустанавливаете ссылки. Все входящие ссылки p все будут поступать в X, q исходящих ребер все отклоняются от Y. Добавьте только 1 ссылку (L) из X в Y. Установив пропускную способность L-link на 1, каждый узел будет использоваться только один раз.
Затем вы можете записать его как (M) ILP и решить его. ILP предоставит вам правильное решение, если оно существует. В зависимости от вашего приложения это может быть излишним. Если вам нужна быстрая эвристика, просто используйте 2 A * поисковые запросы и надейтесь, что они не перекрываются.
Проверьте алгоритм A *. –
Извините, я не могу дать вам больше, только эта ссылка http://en.wikipedia.org/wiki/A*_search_algorithm, здесь вы можете найти пример реализации. –
спасибо, но ничего о контрольной точке нет, если я найду самый короткий путь между стартом и контрольной точкой, это может заблокировать мой путь до конца. – Kamgar