我有一组顶点,每对顶点之间定义了一些利润,因此利润(i,j)可能不等于利润(j,i)。此外,存在正权重周期,利润可能为负。
这是一个寻找最大利润的NP-hard问题,所以问题是每个城市最多访问一个(不需要访问所有城市)的利润最大化。我尝试了以下算法来找到这个:
- 对完整顶点集的贪心算法。
- Greedy with brute force:首先找到顶点的贪心序列。这给出了几乎形成簇的近似顶点集。现在连续设置 8 个城市并重新排列它们以使用蛮力找到最大利润。
但是当在 100 个顶点上尝试时,这些并没有给出很好的结果。
是否有任何其他概率或近似方法来最大化成本?