在加权无向图中，如何找到从特定节点v开始的最小平均成本周期？ [英] In weighted undirected graph, how to find the minimum average cost cycle starting from a specific node v?

问题描述

假设我们有一个加权无向图，并且边| E |的数量约为节点数| V |的k倍，即| E | 〜= k * | V |。

现在，选择一个节点，比如v，我们希望找到包含v且具有最小平均成本的循环。 （即平均成本意味着沿一个周期的平均边缘权重）。

是否有任何有效的算法？

对不起，我错过了一个点 - 循环不需要包含此图中的所有节点。这使得它与汉密尔顿循环问题有所不同。 这相当于哈密尔顿周期问题，它是NP完全的。除非 P = NP ，否则没有最坏情况多项式算法能够解决此问题。

我们可以将哈密尔顿循环问题简化为这个问题：
$ b $ ul

选择一个任意顶点作为起点

为入射到该顶点的每条边指定2的费用

将成本1赋值给所有其他边

n循环的平均成本为（n + 2）/ n - a减少正数 n 的顺序。对于v-顶点图，如果图是哈密尔顿图，则存在（v + 2）/ v 的平均成本周期。因为确定哈密尔顿图是NP完全的，所以这个问题是NP难的。

与这个问题相关的决策问题（是否存在一个简单的循环（如果平均长度的路径存在，那么验证一个周期是一个有足够低的平均成本的有效周期），则需要 O（v） time（使用相邻矩阵表示法）。

---

因此，你不能希望最坏-case-polynomial-time算法。但是，根据边缘成本的分布，使用动态规划的分支定界算法或分支定界可以非常有效：

• （可选）删除不是V所连接的2顶点连接组件的一部分的所有顶点（V可能位于多个2顶点连接的组件中）。
  
• 从V中枚举所有路径。让相关的优先级队列为 q ：
  
  
  
  • 从空路径开始。 >
    
  • 选择成本估算值最低的路径（下限）。
    
  • 将此paht添加到完成集。
  
  
  • 如果成本估算值是不低于 c_best ，终止循环。否则，
    
  • 尝试每个传出边：
    
    
    
    • 如果新顶点已经在路径中并且（它不是V或新路径将是一个双周期的 ⁺ ），拒绝这条边。否则，
    
    
    • 用这条边扩展路径并计算这条新路径的成本估计值。
      
    • 如果估计值不低于 c_best ，拒绝此路径。否则，
      
    • 如果最后一个顶点是V，请将 c_best_path 设置为此路径，并且 c_path 。

    • 新路径 q 。
    
    
    • 如果添加的路径与队列中的其他路径具有相同的签名，请删除更昂贵的路径。
    
    
  



• 返回 c_best_path
  $ b $ p

  ⁺ ：如果图是一个多图，则需要采取两个最便宜的平行边缘而不是相同边缘两次。这可能是最好的一个单独的步骤。

  
  
  

  动态编程检查可能非常便宜（只需对一个顶点集合进行散列），但是如果没有预期的保存（该算法很可能会提前结束），可以省略它 - 删除完成集并忽略队列中的任何重复项（具有相同签名的不同路径）。

  
  
  

  只要可以计算下限，此算法对任何路径成本度量都可以正常工作。对于平均边缘成本问题，我可以想到几种启发式：
  
  

  在任何情况下，如果路径是一个循环，计算并返回它的确切成本。 / b>
  
  

  一个简单的启发式就是假设您可以访问所有剩余的顶点，其边不会比整个图或2连接组件中最便宜的路径便宜。那么相应的预期成本是（cost +（v-edge_length）* c_min）/ edge_length 。好处是这是快速计算。不利的一面是，如果图形很大，而且边缘很少，几乎和最便宜的一样便宜，那么这种算法可以扩展很多路径，以达到它认为的绿洲。

  
  
  

  如果边数不多的价格低于最便宜的价格，您可以在图的所有边中准备 v 的最低价格清单。然后为了估计一个图的成本，考虑：只有最便宜的边完成的路径，用最便宜的两个边完成的路径，用最便宜的三个边完成的路径... while（exp_cost_decreases& amp ;& length< v）exp_cost =（exp_total_cost + = best_edges.next）/ ++长度。好处是它可以做出更好的猜测。缺点是需要较长的时间来计算是否有很多边缘会降低估计值。

  
  
  

  您始终必须使用公共边以及起点（如果存在的话）的末端顶点或与每个顶点相邻的一个边（ min_cost_adjanced（V）+ min_cost_adjanced（end））。如果找到了共同的边缘，那么循环的处理应该在这里完成。

  
  
  

  在哈密尔顿循环缩减的情况下，前两个启发法的性能同样很差。启发式（1 + 3）和（2 + 3）的性能相同。最好的情况是时间线性的。最坏的情况是带动态编程的 O（v * k * 2 ^ v）或 O（v * k * log（k）* （假设优先级队列中的 O（log n） push，pop-min和decrease-key）

  
  
  

  请注意，测试一般图中是否存在哈密尔顿循环的最着名算法是 O（1.657 ^ v） a href =http://en.wikipedia.org/wiki/Hamiltonian_cycle_problem#Algorithms =nofollow>根据维基百科，截至2013年8月）

  
  

  Suppose we have a weighted undirected graph, and the number of edge |E| is about k times of node number |V|, i.e, |E| ~= k * |V|.

  Now, one node, say v, is choosen, and we want to find the cycle containing v with the minimum average cost. (i.e., average cost means average edge weight along a cycle.)

  Is there any efficient algorithms?

  Sorry, I missed one point-the cycle do not need to contain all nodes in this Graph. This makes it different from Hamilton cycle problem.

  解决方案

  This is equivalent to the Hamiltonian cycle problem, which is NP-complete. There is no worst-case-polynomial algorithm able to solve this unless P = NP.

  We can reduce the hamiltonian cycle problem to this problem:

  • choose an arbitrary vertex as the starting point
  • assign the cost of 2 to every edge incident to this vertex
  • assign the cost of 1 to all other edges

  the average cost of an n-cycle is (n+2)/n - a decreasing sequence for positive n. For a v-vertex graph, there is a cycle of the average cost of (v+2)/v iff the graph is a hamiltonian graph. Since the determination if a hamiltonian graph is NP-complete, this problem is NP-hard.

  The decision problem associated with this problem ("Is there a simple cycle of an average edge cost of x passing through a vertex V") is in NP: if a path of that average length exists, then verifying that a cycle is a valid cycle with low enough average cost takes O(v) time (using an adjancency matrix representation).

  ---

  Thus, you cannot hope for a worst-case-polynomial-time algorithm. But, depending on the distribution of edge costs, the branch-and-bound algorithm or branch-and-bound with dynamic programming can be very efficient:

  • (optional) Remove all vertices that are not a part of a 2-vertex-connected component that V is (V can lie in multiple 2-vertex-connnected components).
  • Enumerate all paths from V. Let the associated priority queue be q:
    • Start with the empty path.
    • Pick the path with the lowest cost estimate (lower bound). In case of a tie, pick the path added the latest.
    • Add this paht to the "done" set.
    • If the cost estimate is not lower than c_best, terminate the loop. Else,
    • Try every outgoing edge:
      • If the new vertex is already in the path and (it is not V or the new path would be a two-cycle⁺), reject this edge. Else,
      • Extend the path with this edge and compute the cost estimate of this new path.
      • If the estimate is not lower than c_best, reject this path. Else,
      • If the last vertex is V, set c_best_path to this path and c_path to its cost.
      • Else if a path with the same set of visited vertices and the same last vertex (= signature) is not already present in the "done" set, add the new path to q.
      • If the path being added has the same signature as another path in the queue remove the more expensive path from the queue.
  • Return c_best_path

  ⁺: if the graph is a multigraph, you need to to take two cheapest parallel edges rather than the same edge twice. This is probably best handled in a separate step.

  Dynamic programming checks can be very cheap (just hash a vertex set with a vertex) but if there are very few expected saves (the algorithm is likely to end early), it can be left out - drop the "done" set and ignore any duplicates (different paths with the same signature) in the queue.

  This algorithm works just as fine for any path cost metric as long as you can compute a lower bound. For the average-edge-cost problem, I can think of several heuristics:

  In any case, if the path is a cycle, compute and return its exact cost.

  One simple heuristic is to assume that you may be able to visit all remaining vertices with edges no cheaper than the cheapest path in the entire graph or 2-connected component. Then the respective expected cost is (cost + (v - edge_length) * c_min) / edge_length. The upside is this is fast to compute. The downside is that if the graph is big and there are few edges nearly as cheap as the cheapest one, then this algorithm could expand a lot of paths to reach the "oasis" it thinks there is.

  If there are few edges as cheap as the cheapest one, you can prepare a list of v lowest costs among all edges in the graph. Then to estimate the cost of a graph, consider: The path completed with only the cheapest edge, the path completed with the cheapest two edges, the path completed with the cheapest three edges... while(exp_cost_decreases && length < v) exp_cost = (exp_total_cost += best_edges.next) / ++length. The upside is it makes better guesses. The downside is that it takes longer to compute if there are lot of edges that lower the estimate.

  You always have to use either a common edge to the start vertex and the end vertex of the path (if one exists) or one of the edges adjanced to each vertex (min_cost_adjanced(V) + min_cost_adjanced(end)). If a common edge is found, the handling of cycles should possibly be done here.

  In case of the hamiltonian cycle reduction, both of the first two heuristics will perform equally poorly. The heuristics (1+3) and (2+3) will perform equally. The best-case scenario is linear in time. The worst-case scenario is O(v*k*2^v) with dynamic programming or O(v*k*log(k)*k^v) without (assuming a priority queue with O(log n) push, pop-min and decrease-key)

  Note that the best known algorithm to test whether a hamiltonian cycle exists in a general graph is O(1.657^v) (according to wikipedia, as of Aug 2013)

  这篇关于在加权无向图中，如何找到从特定节点v开始的最小平均成本周期？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！