0

重複の可能性:
Java でのスター (A*) アルゴリズムの実装

巡回セールスマンの問題を解決するために、いくつかの検索アルゴリズムを実装する必要がある割り当てについて、私は問題を理解しており、アルゴリズムがどのように機能するかを理解しています。単に実装方法がわかりません (私の Java は優れていません)。これは本当に簡単な部分ですが、残念ながら、Java に関する私の知識は、アルゴリズムについて知っていることを適用するには十分ではありません。

したがって、誰かがこれを始める方法についてのヒントやヒント、または読むための良いリンクを提供できるかどうか疑問に思っていました.IDで始めるのが簡単なアルゴリズムがある場合は、他のアルゴリズムも実装する必要があります.それと一緒に行く！私はすでにここを見てきましたが、関連するものを見つけることができないようです:/

どんな助けでも大歓迎です！ありがとうございました

4

1 に答える 1

0

私は専門家ではありませんが、巡回セールスマン問題の解決に A* を使用できるとは思いません。TSP が NP 困難であることはご存じだと思います。そのため、正確な解は非常に複雑で、すべてのケースに対応できるわけではありません。解を近似するために私が知っている (そして使用した) 最も簡単な方法は、「シミュレーテッド アニーリング」と呼ばれるもので、これは確率論的方法です (つまり、ランダムです!)。

アイデアはとてもシンプルです。ポイントをリストにまとめます。これは、すべてのノード間のパスを表します (これを「ツアー」と呼びます)。ツアーの長さを計算し、長さを保存します。次に、ランダムなサブリストを選択して、単純に逆にします。新しい長さを計算します。新しいリストが短い場合は保持し、そうでない場合は破棄します。これらの手順を 100/1,000/10,000,000 回 (ポイントの数に応じて) 繰り返すだけで、適切な概算値が得られます。

例として、5 つのポイント (疑似コード) があるとします...

List tour = [e, b, a, d, c]
int len = tourLength(tour)
List newTour = [e, b] + [d, a] + [c] // a and d have been reversed
int newLen = tourLength(newTour)
if(newLen < len) {
    tour = newTour
}

10 ポイントの場合、100 回の反復で良好な結果が得られます。

于 2012-12-07T17:13:33.040 に答える