在加权无向图中，如何从一个特定的节点v开始寻找最小平均成本周期？

Question

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

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

有没有高效的算法？

很抱歉，我错过了一点，循环不需要包含此图中的所有节点。这使得它不同于哈密顿循环问题。

Answer 1

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

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

Answer 2

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

不幸的是，Jan给出的降低是不正确的，因为成本周期（v 2）/v通常不是最小平均成本周期。特别是，任何不包含起点的周期都将具有平均成本1

Answer 3

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

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

• 选择任意顶点作为起点

一个n周期的平均成本是（n2）/n——正n的递减顺序。对于v-顶点图，如果图是哈密顿图，则存在（v2）/v的平均代价的循环。由于哈密顿图是否是NP完全的判定，这个问题是NP难的。

与这个问题相关的决策问题（“是否有一个简单的x通过顶点V的平均边成本循环”）是在NP中：如果存在一个平均长度的路径，那么验证一个循环是一个有效的循环，并且足够低平均花费O（v）时间（使用邻接矩阵表示）。

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

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

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

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

    该算法适用于任何路径成本度量，只要可以计算下限。对于平均边缘成本问题，我可以想到几种启发式方法：

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

    一个简单的启发式方法是假设您可以访问所有剩余的顶点，其边不比整个图或2连通组件中最便宜的路径便宜。然后，相应的预期成本为（成本（v-边缘长度）*c\u min）/edge\u长度。有利的一面是计算速度很快。缺点是，如果图很大，而且几乎没有边像最便宜的边那么便宜，那么该算法可以扩展很多路径，以到达它认为存在的“绿洲”。

    如果没有几条边像最便宜的边那样便宜，那么您可以准备一份图表中所有边中成本最低的v列表。然后，要估计一个图的代价，请考虑：仅使用最便宜边完成的路径，使用最便宜的两条边完成的路径，使用最便宜的三条边完成的路径<代码>同时（经验成本降低）

    始终必须使用路径起点顶点和终点顶点的公共边（如果存在）或与每个顶点邻接的一条边（min\u cost\u adjanced（V）min\u cost\u adjanced（end））。如果发现一条公共边，则可能在此处处理循环。

    在哈密顿循环缩减的情况下，前两种启发式算法的性能都同样差。启发式算法（13）和（23）的性能相同。最佳情况是时间上的线性。最坏的情况是使用动态编程的O（v*k*2^v），或者不使用动态编程的O（v*k*log（k）*k^v）（假设优先级队列使用O（log n）推送、弹出最小值和减少键）

    请注意，测试一般图中是否存在哈密顿圈的最著名算法是O（1.657^v）（根据维基百科，截至2013年8月）