1.問題の声明
500頂点の完全な重み付きグラフは、隣接行列によって与えられます。
このグラフでハミルトニアンサイクルを可能な限り低い合計コストで見つける必要があります。
2.決定
1.貪欲なアルゴリズム
ここではすべてが簡単です。任意の頂点から開始し、移動可能なエッジの最小コストを選択し、頂点xに移動し、頂点を消し、頂点xで同じことを行います。
シンプルで高速。
しかし、答えは真実とはかけ離れているかもしれません。
Zhadinaはランダムグラフではうまく機能しますが、ここではグラフについて何も知りません。
したがって、次に進みます。
2.公正な検索
巡回セールスマンのタスクは、最小総コストのハミルトニアンサイクルの検索でもあり、NPが重いため、このようなグラフの徹底的な検索は永遠に続く可能性があるため、このアイデアは機能しません。
3.枝とボーダーの方法
頭に浮かんだ2番目のアイデアは、アルゴリズムのすべてのステップで明らかに最適でないソリューションを破棄し、改善された列挙を使用することです。
この種の最も効果的なアルゴリズムの1つは、1963年にCarelのLittle、Merty、Sweeneyが開発した分岐限定法（「バックトラッキング」）です。
S（0）を、n個の都市とコストマトリックスcを持つ巡回セールスマン問題のすべての許容される閉ルートのセットとします。
Littleの方法は、セットを2つの互いに素なサブセットに分割し、それぞれの推定値を計算することに基づいています。 次に、最小推定（コスト）のサブセットが2つのサブセットに分割され、それらの推定が計算されます。 各ステップで、このステップで取得されたすべての推定値の中で最も小さいサブセットが選択され、2つのサブセットに分割されます。 最終的に、1つのサイクル（課せられた制限を満たす閉じたルート）を含むサブセットを取得します。そのコストは最小限です。
アルゴリズムは2つの段階で構成されます。
第一段階
コストマトリックスを取得し、ルートrのコストのより低い推定値を計算します。
1.各行の最小要素を計算します（行のキャスト定数）
2.各行からその縮小定数を減算することにより、新しいコストマトリックスに渡します。
3.各列の最小要素を計算します（列のキャスト定数）
4.各列からその縮小定数を減算することにより、新しいコストマトリックスに進みます。
その結果、各行と列に少なくとも1つのゼロ要素が含まれるコストマトリックスが作成されます。
5.列と行のキャスト定数の合計としてrを計算します。
第2（メイン）ステージ
1.削減コストマトリックスの各ゼロ要素の不使用に対するペナルティの計算。
不使用のペナルティとは、マトリックス内のインデックス（h、k）を持つ要素を意味し、このエッジがルートに含まれないことを意味します。したがって、このエッジを「使用しない」最小コストは行hと列kの最小要素の合計です。
a）与えられた行列内のすべてのゼロ要素を探しています
b）それらのそれぞれについて、不使用に対するペナルティを考慮します。
c）最大ペナルティに対応する要素を選択します
なぜ最大ですか？ これは、このエッジのルートから除外すると、最適なルートのコストが最大に増加することになります。
2.次に、セットS（0）をSw（エッジh、kを含む）とSw / o（エッジh、kを含まない）の2つに分割します。
3.これらの各セットに含まれるルートのコスト見積もりの計算。
a）セットSw / oの場合、すべてが単純です：エッジ（h、k）を使用しないため、コスト推定値はセットSのコスト推定値（0）+エッジを使用しない場合のペナルティ（h、k）に等しくなります
b）セットSwのコストを計算するとき、エッジ（h、k）がルートに入るため、エッジ（k、h）がルートに入ることができないため、コストマトリックスにc（k、h）=と書く無限大、ポイントhを「既に去り」、ポイントkに「すでに来ている」ので、hから出ているエッジもkに入っているエッジも使用できないため、行hと列kの行列をコストします。 その後、マトリックスを提示すると、Swのコスト推定値はS（0）とr（h、k）のコスト推定値の合計に等しくなります。ここで、r（h、k）は修正されたコストマトリックスの還元定数の合計です。
4. SwおよびSw / oのセットから、最高の評価を持つものが選択されます。
そのため、経費のマトリックスに、クロスアウトされていない行とクロスアウトされていない列がなくなるまで続けます。
今の結果。
各ステップで2つのセット（SwとSwo）からのみ選択する場合、アルゴリズムはかなり正常に機能しますが、精度はひどいです（項目1から欲張りの多くを失います）
すべてのステップで、このステップで取得され、以前に使用されなかったすべての最適なセットを選択した場合、
その後、小さなグラフ（約40〜50）の頂点については、良好な精度が得られますが、500の頂点を待つことはできませんでした。
したがって、次の考え方が思い浮かびます。
4.ヒューリスティックを使用したブランチおよびボーダーの方法
はい、本当です、なぜヒューリスティックを導入しませんか？ 実際、ブランチとボーダーのアルゴリズムでは、ノードをエッジ（x、y）にするかどうかを決定するツリーを実際に構築し、Sw（x、y）とSw / o（x、y）の2つの子をハングさせます。 ただし、次の反復に最適なオプションは、評価によってのみ選択されます。 それでは、評価だけでなく、ツリーの深さによっても最良のものを選択しましょう。 選択したアイテムが深いほど、カウントの終わりに近くなります。 したがって、最終的に回答を待つことができます。
ヒューリスティックコスト=マークの最初で最も単純なバリアントは、k *深さです。 k rib骨の平均重量に応じて選択するが、それでも深さが決定的な役割を果たさないようにする。 また、たとえば、その深さが少なくともb、つまり 頂点がルートから距離qにあり、q <bの場合、depth = b、そうでない場合はdepth = q。 bとして、分岐および境界の正直なアルゴリズム（ヒューリスティックなし）が適切な時間でそのような深さに達するような数を選択します。 私の場合、b = 30でした。
開始し、待機します。
仕事の夜には、欲張りアルゴリズムよりも2％優れた答えが得られます。
貪欲なアルゴリズムが数秒間機能し、5分で書かれていることを考えると、ごくわずかです。
そして今勝者：
ローカルボーダーとブランチメソッドを備えた貪欲なアルゴリズム
アルゴリズムは次のとおりです。
1.貪欲なアルゴリズムを実行して、ルートを取得します。
2.ルートをいくつかの部分に分割します。
3.各部分で、ルートの最後の頂点から最初の頂点まで、架空のエッジを作成します。
4.これらの各部分で、ヒューリスティックなしで分岐およびバインドメソッドを実行します。
5.分枝限定法によって最適化されたパーツを結合し、ダミーエッジを開き、n-1パーツの最後の頂点を最初のnパーツに接続します。
このアルゴリズムにはいくつかの利点があることを理解するのは簡単です。
-ヒューリスティックを使用しない、ブランチとボーダーの正直な方法。
-並列化するのは簡単で、仕事の時に勝ちます。
-欲張りアルゴリズムはパーティションの一部のみを示し、結合後はNUMBER_OF_PARTS-1エッジのみを使用し、欲張りアルゴリズムによって与えられ、分枝限定法によって最適化されません。
結果。
25個の部品の稼働時間-3分、貪欲に勝ちます〜7％
10パーツ-4時間、ゲイン〜15％
継続