Взвешенный ход графика с проскальзываниями

Question

В то время как я был в душе сегодня, я подумал: «Как трудно было бы написать алгоритм для перемещения взвешенного ди-графа и найти кратчайший путь, если ему разрешено пропустить фиксированное число ребра s. Я начал думать об одном пропуске, а для метода грубой силы, похоже, умножает проблему на количество ребер на вашем графике, так как вам нужно найти кратчайший путь для каждого случая, когда ребро установлено на 0, а затем сравните все графики. Я не знаю, есть ли какие-либо алгоритмы, которые делают это, но беглый поиск google не показывал.

Мой первый вопрос заключается в том, чтобы пропустить наиболее затратные края, но это также интересная проблема, связанная с поиском пути, предполагающего, что вы пропускаете наименее затраченные края.

Это просто для удовлетворения моего любопытства, поэтому не спешите.

Спасибо!

Answer 1

Далее следует логика решения этой проблемы. Способ решения этой проблемы состоит в том, чтобы рассмотреть граф, состоящий из двух копий исходного графа, который вы хотите пройти, и я опишу, как его создать. Для вас нарисуйте небольшой график, а затем нарисуйте его топологически отсортированным (что помогает при визуализации, но в программе не обязательно). Затем нарисуйте копию этого графика на несколько дюймов выше оригинала. Вы находитесь в нижней части этого графика, когда вы еще не использовали свой пропуст, и вы находитесь в верхней части, когда вы использовали свой пропуск. Давайте назовем узлы в нижнем графике A1, A2, A3 ... и узлы в верхнем графе B1, B2, B3 ... Если в вашем исходном графе узел 1 подключен к узлам 2, то ваш новый граф имеет ребра A1-> A2, B1-> B2 и свободную связность A1-> B2 (с краевой стоимостью 0).

Рассмотрите следующий оригинальный график, в котором вы начинаете с черного узла, и хотите попасть в синий узел.

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

В каждом месте в нижней части графика, вы не использовали свой пропуск, и, таким образом, может либо пропустить (перемещение в верхней части графика) или может нормально двигаться, переходя к другому узел в нижнем графике.

Затем вы можете использовать любой из стандартных алгоритмов обхода графика.