使用贝尔曼福特来检测产品超过阈值的循环

问题描述

用于检测图中的负加权循环。我想知道如何使用它来检测超过某个阈值的周期。

示例：

    c $ c>哈密尔顿周期问题，保持同样的图 G ，其中 w（e）= 2 边缘，然后将它发送到阈值 2 ^ | V | -1 的问题。 
 
如果任何周期的权重大于 2 ^ | V | -1，那么它的边数多于 | V | -1`所以这个循环是哈密尔顿算子，如果有一个哈密尔顿循环，算法会发现有一个重量为2 * 2 * ... * 2> 2 ^ | V | -1的循环。
 
 
 
由于哈密尔顿周期是Np-完全的，并且我们找到了这个问题的多项式约化，所以这个问题是NP-Hard，并且没有已知的多项式解。
 
 
 
 
 
  tl; dr：使用Bellman Ford来解决这个问题远不是微不足道的，如果可能的话，需要修改图形为指数（假设P！= NP）
Bellman Ford is used to detect negative weighted cycles in a graph. I would like to know how I can use it to detect cycles which exceeds a certain threshold instead. 

Example: 
               --------->
               ^        |1
       0.5     | <------v
1 -----------> 2
^             |
|4            |1
|     2       v
4<------------3
This graph has 2 cycles. One with the product = 1 and the other with the product = 4. If the threshold = 1, the algorithm should output true, since there is 1 cycle with a product > 1. 
 解决方案 
I assume you want to detect a simple cycle with weight that exceeds some threshold (otherwise, you can repeat any positive weight>1 cycle enough times to exceed any positive threshold).
Unfortunately, that problem is NP-Hard.
A simple reduction from the Hamiltonian cycle problem:
Given an instance G=(V,E) of Hamiltonian cycle problem, keep the same graph G, with w(e) = 2 for any edge, and send it to the problem with threshold 2^|V|-1.
If there is any cycle with weight bigger than 2^|V|-1, then it has more than|V|-1` edges, so this cycle is hamiltonian, and if there is a hamiltonian cycle, the algorithm will find that there is a cycle of weight 2*2*...*2> 2^|V|-1.
Since Hamiltonian Cycle is Np-Complete, and we found polynomial reduction from it to this problem, this problem is NP-Hard, and there is no known polynomial solution to it.
tl;dr: to use Bellman Ford to solve this problem, is far from trivial, and if possible, will require modifying the graph to be exponential in size of the original graph (Assuming P!=NP)
                        
这篇关于使用贝尔曼福特来检测产品超过阈值的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！