在具有正權重週期的圖中最大化利潤

Question

我有一組頂點，在每對頂點之間定義了一些利潤，這樣利潤（i，j）可能不等於利潤（j，i）。此外存在正面權重週期和利潤可能是負面。

這是一個難以找到最大利潤的NP難題，所以問題是最大化每個城市訪問的最大利潤（所有城市都不需要訪問）。 我試過下面的算法找到這個：

• 貪心算法的頂點集。
• 貪婪與暴力：首先找到貪婪的頂點序列。這給出幾乎形成簇的近似頂點集合。現在連續說8個城市，並重新排列他們，以蠻力尋找最大利潤。

但是，當在100個頂點上試用時，這些並不能給出非常好的結果。

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

Answer 1

林不知道我明白這個問題，但你不能排序的邊緣，並找到最小生成樹。克魯斯卡爾算法如何工作？

編輯 如果存在負的重量邊緣，您可以停止重量變爲負值的時刻。