Использование Bellman Ford для обнаружения циклов с порогом превышения продукта
Беллман Форд используется для обнаружения отрицательных взвешенных циклов на графике. Я хотел бы знать, как я могу использовать его для обнаружения циклов, которые превышает определенный порог вместо.
Пример:
--------->
^ |1
0.5 | <------v
1 -----------> 2
^ |
|4 |1
| 2 v
4<------------3
Этот график имеет 2 цикла. Один с продуктом = 1, а другой с продуктом = 4. Если порог = 1, алгоритм должен вывести true, поскольку существует 1 цикл с продуктом> 1.
Решение
Я полагаю, вы хотите обнаружить просто цикл с весом, превышающим некоторый порог (в противном случае вы можете повторить любой положительный вес> 1 цикла достаточно раз, чтобы превысить любой положительный порог).
К сожалению, эта проблема NP-Hard.
Простое сокращение от Задача о гамильтоновом цикле:
Учитывая экземпляр G=(V,E) задачи о гамильтоновом цикле, сохранить тот же график G, с w(e) = 2 для любого края, и отправьте его на проблему с порогом 2^|V|-1,
Если есть какой-либо цикл с весом больше 2^|V|-1, then it has more than| V | -1` ребер, так что этот цикл гамильтонов, и если есть гамильтонов цикл, алгоритм найдет, что существует цикл веса 2 * 2 * … * 2> 2 ^ | V | -1 ,
Поскольку гамильтонов цикл является Np-полным, и мы нашли полиномиальную редукцию от него к этой задаче, эта задача является NP-сложной, и для нее нет известного решения для полинома.
tl; dr: использование Bellman Ford для решения этой проблемы далеко не тривиально и, если возможно, потребует изменения графа, чтобы он был экспоненциальным по размеру исходного графа (при условии P! = NP)
Другие решения
Частичное решение проблемы
Это решение работает, когда порог равен 1.
ТЛ; др Измените вес ребер, применив логарифм и используйте Флойд-Варшал, чтобы обнаружить отрицательные циклы, которые произойдут, если произведение исходных весов цикла больше 1.
длинный ответ.
Флойд-Варшал может быть использован для APSP, а также обнаружения отрицательные циклы в графе. Чтобы сделать эту проблему проблемой, где решение включает поиск нег. циклы, выполните следующие действия:
- Построить граф на основе матрицы смежности
- инициировать значения матрицы с
log(weight of edge) * (-1)
это значение станет положительным, если исходное значение меньше 1, или другими словами: оно отрицательно для всех значений больше 1.
поскольку log(m * n) = log(m) * log(n)Нам больше не нужно умножать, чтобы получить результат, а просто добавляем логи.
Следовательно, если алгоритм нашел отрицательный цикл, мы можем знать, что произведений его ребер из исходного цикла больше 1.