Использование Bellman Ford для обнаружения циклов с порогом превышения продукта

Question

Bellman Ford используется для обнаружения отрицательных взвешенных циклов на графике.Я хотел бы знать, как я могу использовать его для обнаружения циклов, которые вместо превышают определенный порог.

Пример:

               --------->
               ^        |1
       0.5     | <------v
1 -----------> 2 
^             |
|4            |1
|     2       v
4<------------3 

Этот график имеет 2 цикла.Один с продуктом = 1, а другой с продуктом = 4. Если порог = 1, алгоритм должен вывести true, поскольку существует 1 цикл с продуктом> 1.

Answer 1

Частичное решение проблемы

Это решение работает, когда порог равен 1.

tl; др Изменение весовребер, применяя логарифм и используя Флойд-Варшал, чтобы обнаружить отрицательные циклы, которые произойдут, если произведение исходных весов цикла больше 1.

длинный ответ .Флойд-Варшал может быть использован для APSP, а также для обнаружения отрицательных циклов на графике .Чтобы сделать эту проблему проблемой, где решение включает в себя поиск нег.циклы, выполните следующие действия:

• Постройте график на основе матрицы смежности
• Инициируйте значения матрицы с помощью log(weight of edge) * (-1)

Это значение станет положительным, если исходное значение меньше 1, или другими словами: оно отрицательно для всех значений, превышающих 1.

Поскольку log(m * n) = log(m) * log(n), мы ненужно больше умножать, чтобы получить результат, а просто добавить журналы.

Следовательно, если алгоритм нашел отрицательный цикл, мы можем знать, что произведения его ребер из исходного цикла больше 1.

Answer 2

Я предполагаю, что вы хотите обнаружить простой цикл с весом, превышающим некоторый порог (в противном случае вы можете повторить любой положительный вес> 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)