誰かがそれを行うためのアルゴリズムまたは何かを知っていますか
したがって、アークに接続されたノードがあり、すべてのノードをカバーするおおよその最短パスを見つけるための解決策を見つける必要があります。（私は一度しか訪問できません）
取得に時間がかかるため、おおよそのパスである必要があります。最短パス
あなたの答えをありがとう:)
（私はJavaでそれをしなければなりません）
4 に答える
5
これは巡回セールスマン問題として知られており、合理的かつ迅速な近似は、常に最も近い未訪問のノードを次に訪問し、他のいくつかの開始場所で同じことを再試行することです。通常、これにより最適解に非常に近づきます。
もう 1 つのアルゴリズムは、最初にグラフの最小スパニング ツリーを構築し、次に繰り返されるノードを削除することです。これにより、準最適性の特定の上限が保証されます (ユークリッドの場合 (ウィキペディア) の 2 倍以下)
さらに別のアルゴリズムは、最初の 3 つのノードから開始し、既存のエッジを分割する (または最後に新しいエッジを追加する) ことによって、次のノードをある順序 (初期、x 座標でソート、中心からの距離でソート) で追加することです。 、最短パスの場合) パスをできるだけ短く保ちます。
解決策 (悪いものであっても) があれば、K-opt によって改善できます。K 個のランダムなエッジを繰り返し選択し、それらを完全に削除して、新しいエンドポイントを再接続する最善の方法を見つけます。K-opt の変形は、3 つのエッジのうち 2 つが常に隣接する 2-opt ステップと 3-opt ステップを (ある順序で) 交互にするLin-Kerninghamヒューリスティックです。
ほとんどのエッジが欠落しているか、非常に長い (2 つのノード間の距離がメトリックを形成しない) 場合は、問題があります。エッジが欠落している場合、そのようなパスが存在するかどうかを判断するのは NP 完全であるとだけ言っておきましょう。
于 2012-11-24T12:28:24.817 に答える
1
非常に高速な近似は、空間充填曲線に沿って頂点を並べることです。空間充填曲線は次元を削減し、一部の空間情報も保持します。旅行のセールスマンの問題でムーア曲線を試してみてください。これは、始点と終点が互いに隣接する 4 つのヒルベルト曲線のコピーであるためです。しかし、描くのは少し高価です。
于 2012-11-24T14:17:04.313 に答える
0
はいあります。この方法は「遺伝的最適化」と呼ばれ、次のように進みます。2. k 個の隣接するノードをランダムに選択します: N1,N2..Nk : X->N1->..Nk->Y 3. ノード N1..Nk を使用して、X から Y へのより短いパスがあるかどうかを確認します。パス X -*> Y をより短いソリューション 5 に置き換えます。 goto 2
より短い組み合わせを簡単に見つけることができるように、k は小さくする必要があります (5 以下)。
これの良いところは、いつでも停止して既存のソリューションを使用できることです。より大きな k を 1 回ランダムに選択することで改善されます。
于 2012-11-24T12:23:58.583 に答える