0

私は、利益(i、j)が利益(j、i)と等しくない可能性があるように、頂点の各ペア間で定義された利益を持つ一連の頂点を持っています。さらに、プラスのウェイト サイクルが存在し、利益がマイナスになる場合もあります。

これは、最大の利益を見つけるための NP 困難な問題であるため、問題は、各都市を訪問する利益を最大化することです (すべての都市を訪問する必要はありません)。これを見つけるために、次のアルゴリズムを試しました。

  • 頂点の完全なセットに対する貪欲なアルゴリズム。
  • 力ずくで貪欲: まず頂点の貪欲なシーケンスを見つけます。これにより、ほぼクラスターを形成する頂点の近似セットが得られます。次に、たとえば 8 つの都市の連続したセットを取り、それらを並べ替えて、力ずくで最大の利益を見つけます。

しかし、これらを 100 個の頂点で試した場合、あまり良い結果は得られません。

コストを最大化するための他の確率的または近似的な方法はありますか?

4

1 に答える 1

0

質問を理解しているかどうかわかりませんが、エッジを並べ替えて最小スパニング ツリーを見つけることはできませんか。kruskalsアルゴリズムがどのように機能するか?

編集 負の重みエッジが存在する場合、重みが負になった瞬間に停止できます。

于 2013-02-03T06:47:29.023 に答える