0

我有一组顶点,每对顶点之间定义了一些利润,因此利润(i,j)可能不等于利润(j,i)。此外,存在正权重周期,利润可能为

这是一个寻找最大利润的NP-hard问题,所以问题是每个城市最多访问一个(不需要访问所有城市)的利润最大化。我尝试了以下算法来找到这个:

  • 对完整顶点集的贪心算法。
  • Greedy with brute force:首先找到顶点的贪心序列。这给出了几乎形成簇的近似顶点集。现在连续设置 8 个城市并重新排列它们以使用蛮力找到最大利润。

但是当在 100 个顶点上尝试时,这些并没有给出很好的结果。

是否有任何其他概率或近似方法来最大化成本?

4

1 回答 1

0

我不确定我是否理解这个问题,但你不能对边缘进行排序,然后找到最小生成树。kruskals 算法是如何工作的?

编辑如果存在负权重边缘,您可以在权重变为负数时停止。

于 2013-02-03T06:47:29.023 回答