4

少し奇妙な質問があります。誰かが情報を見つける場所を教えてもらえますか、または山登り法を使用する最短経路アルゴリズムの使用について少し紹介してもらえますか？私は両方の基本を理解していますが、2つを組み合わせることができません。ウィキペディアには、山登り法で巡回セールスマンを解決することについて興味深い部分がありますが、それを正確に行う方法についてのより詳細な説明は提供されていません。

たとえば、山登り法は巡回セールスマン問題に適用できます。すべての都市を訪問する解決策を見つけるのは簡単ですが、最適な解決策と比較すると非常に貧弱です。アルゴリズムはそのようなソリューションから始まり、2つの都市が訪問される順序を切り替えるなど、小さな改善を行います。最終的には、はるかに優れたルートが得られます。

私が理解している限りでは、任意のパスを選択し、それを繰り返して、途中で最適化を行う必要があります。たとえば、戻って開始ノードから別のリンクを選択し、それによってパスが短くなるかどうかを確認します。

申し訳ありませんが、私は自分自身をあまり明確にしませんでした。このアイデアを巡回セールスマンに適用する方法を理解しています。最短距離アルゴリズムで使用したいと思います。

4

4 に答える 4

4

ランダムに 2 つの都市を交換できます。

最初のパスは次のとおりです: 長さ 200 の ABCDEFA

ここで、C と D を入れ替えて変更します。長さ 350 の ABDCEFA - さらに悪いことに!

次のステップ: ABCDFEA: 長さ 150 - ソリューションを改善しました。;-)

ヒル クライミング アルゴリズムは実装が非常に簡単ですが、極大値に関していくつかの問題があります。[同じ考えに基づくより良いアプローチはシミュレーテッド アニーリングです。]

山登りは非常に単純な種類の進化的最適化であり、より高度なアルゴリズム クラスは遺伝的アルゴリズムです。

TSP を解決するためのもう 1 つの優れたメタヒューリスティックは、アリのコロニーの最適化です。

于 2009-05-17T15:56:02.310 に答える
2

例としては、データ クラスタリングにおける遺伝的アルゴリズムや期待値の最大化があります。単一のステップの反復により、すべてのステップでより良いソリューションに到達しようとします。問題は、ローカルの最大値/最小値のみを検出することであり、グローバルな最大値/最小値を検出することは保証されません。

必要な遺伝的アルゴリズムとしての巡回セールスマン問題の解決策:

  • 訪問した都市の順序としてのソリューションの表現、たとえば [ニューヨーク、シカゴ、デンバー、ソルトレイクシティ、サンフランシスコ]
  • 移動距離としてのフィットネス関数
  • 最良の結果の選択は、適応度に応じてアイテムをランダムに選択することによって行われます。適応度が高いほど、解が生き残るために選択される確率が高くなります。
  • [A、B、C、D]が[A、C、B、D]になるように、突然変異はリスト内の都市に切り替わります
  • 2 つの可能な解 [B,A,C,D] と [A,B,D,C] を交差させると、[B,A,D,C] になります。つまり、両方のリストを途中で切り取り、1 つの親の先頭を使用します。子を形成するもう一方の親の終わり

アルゴリズムは次のようになります。

  • ソリューションの開始セットの初期化
  • すべての解の適合度の計算
  • 望ましい最大フィットネスまで、または変化が起こらなくなるまで
    • 最善の解決策の選択
    • 交差と突然変異
    • すべての解の適合度計算

アルゴリズムを実行するたびに結果が異なる可能性があるため、複数回実行する必要があります。

于 2009-05-17T16:08:51.953 に答える
1

ダイクストラのアルゴリズムはフィボナッチキューを使用した多項式の複雑さO（| E | + | V | log | V |）であるため、山登りアルゴリズムを使用する理由がわかりません：http: //en.wikipedia.org / wiki / Dijkstra's_algorithm

シングルパス問題へのヒューリスティックなアプローチを探している場合は、A *を使用できます：http： //en.wikipedia.org/wiki/A * _search_algorithm

ただし、効率の向上は、目標までの距離をヒューリスティックに推定できるかどうかにかかっています。 http://en.wikipedia.org/wiki/A * _search_algorithm

于 2009-06-15T19:38:15.603 に答える
0

TSP をヒルクライムするには、開始ルートが必要です。もちろん、「賢い」ルートを選んでも問題ありません。

その開始ルートから 1 つの変更を行い、結果を比較します。高い場合は新しいものを維持し、低い場合は古いものを維持します。これを、もう登れなくなるまで繰り返します。これが最高の結果になります。

明らかに、TSP を使用すると、極大値に達する可能性が高くなります。しかし、十分な結果を得ることができます。

于 2009-05-17T16:23:42.403 に答える