1

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

现在，选择一个节点，比如说 v，我们想要找到包含 v 且平均成本最小的循环。（即，平均成本是指一个周期内的平均边权重。）

有没有有效的算法？

对不起，我漏掉了一点——循环不需要包含这个 Graph 中的所有节点。这使得它不同于汉密尔顿循环问题。

4

3 回答 3

2

这相当于哈密顿循环问题，它是 NP 完全的。除非P = NP，否则没有最坏情况多项式算法能够解决这个问题。

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

  • 选择任意顶点作为起点
  • 将成本 2 分配给与该顶点相关的每条边
  • 将成本 1 分配给所有其他边

n 循环的平均成本是(n+2)/n- 正数的递减序列n。(v+2)/v对于一个 v-vertex 图，如果该图是一个哈密顿图，则存在一个平均成本的循环。由于确定哈密顿图是否是 NP 完全的，所以这个问题是 NP 难的。

与此问题相关的决策问题（“是否存在 x 通过顶点 V 的平均边成本的简单循环”）在 NP 中：如果存在该平均长度的路径，则验证循环是有效循环平均成本足够低需要O(v)时间（使用邻接矩阵表示）。

因此，您不能指望最坏情况的多项式时间算法。但是，根据边缘成本的分布，分支定界算法或动态规划的分支定界算法可能非常有效：

  • （可选）删除不属于 V 的 2 顶点连接组件的所有顶点（V 可以位于多个 2 顶点连接组件中）。
  • 枚举 V 中的所有路径。让关联的优先级队列为q：
    • 从空路径开始。
    • 选择成本估计最低的路径（下限）。如果出现平局，请选择添加最新的路径。
    • 将此路径添加到“完成”集中。
    • 如果成本估计不低于c_best，则终止循环。别的，
    • 尝试每个传出边缘：
      • 如果新顶点已经在路径中并且（它不是 V 或者新路径将是两个循环+），则拒绝这条边。别的，
      • 用这条边扩展路径并计算这条新路径的成本估计。
      • 如果估计值不低于c_best，则拒绝该路径。别的，
      • 如果最后一个顶点是 V，则设置c_best_path为此路径c_path及其成本。
      • 否则，如果具有相同访问顶点集和相同最后一个顶点（= 签名）的路径尚未出现在“完成”集中，则将新路径添加到q.
      • 如果要添加的路径与队列中的另一个路径具有相同的签名，则从队列中删除更昂贵的路径。
  • 返回c_best_path

+：如果图是多重图，则需要取两条最便宜的平行边，而不是同一条边两次。这可能最好在单独的步骤中处理。

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

只要您可以计算下限，该算法对于任何路径成本度量都一样有效。对于平均边缘成本问题，我可以想到几个启发式方法：

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

一种简单的启发式方法是假设您可以访问所有剩余的顶点，其边不低于整个图中最便宜的路径或 2 连通组件。那么相应的预期成本为(cost + (v - edge_length) * c_min) / edge_length。好处是计算速度很快。不利的一面是，如果图很大并且几乎没有与最便宜的边一样便宜的边，那么该算法可以扩展许多路径以到达它认为存在的“绿洲”。

如果很少有边与最便宜的边一样便宜，您可以准备一个v图表中所有边中成本最低的列表。然后估计一个图的成本，考虑：只用最便宜的边完成的路径，用最便宜的两条边完成的路径，用最便宜的三条边完成的路径while(exp_cost_decreases && length < v) exp_cost = (exp_total_cost += best_edges.next) / ++length......。好处是它可以做出更好的猜测。不利的一面是，如果有很多边会降低估计值，则计算时间会更长。

您始终必须使用路径的起始顶点和结束顶点（如果存在）的公共边或与每个顶点相邻的边之一（min_cost_adjanced(V) + min_cost_adjanced(end)）。如果找到共同边，则可能应在此处完成循环处理。

在汉密尔顿循环减少的情况下，前两个启发式算法的表现都一样差。启发式 (1+3) 和 (2+3) 的性能相同。最好的情况是时间线性的。最坏的情况是O(v*k*2^v)使用或不使用动态编程O(v*k*log(k)*k^v)（假设优先级队列带有O(log n)push、pop-min 和 reduce-key）

请注意，测试通用图中是否存在汉密尔顿循环的最著名算法是O(1.657^v)（根据维基百科，截至 2013 年 8 月）

于 2013-08-29T07:04:25.323 回答
1

实际上存在一种基于动态规划的 O(|V||E|) 算法，由 Karp 在 1978 年首次描述（http://www.sciencedirect.com/science/article/pii/0012365X78900110，或第 5.7 节）网络流”，Ahuja、Magnanti 和 Orlin）。

不幸的是，Jan 给出的减少是不正确的，因为成本周期 (v+2)/v 通常不是最小平均成本周期。特别是，任何不包含起点的循环对于任何 n 都将具有平均成本 1 < (n+2)/n。

于 2014-10-12T21:04:50.233 回答
0

德沃夏克的回答是正确的。原始问题要求循环通过指定的顶点 v。平均成本 (v+2)/v 的循环将是“找到必须通过顶点 v 的平均成本最小的简单循环”问题的最佳答案.

在 Karp 的论文中，“在图中找到最小平均成本周期”的问题在 O(|V||E|) 中得到解决。循环不需要经过任何特定的顶点。

于 2015-06-05T18:20:59.260 回答