用語集

左側のキーワードの1つを選択…

巡回セールスマン問題

読書の時間: ~5 min
このページは自動翻訳されているため、エラーが含まれている可能性があります。翻訳のレビューをご希望の場合はご連絡ください。

もう一度、ネットワークとマップについて考えてみましょう。配達サービスが訪問しなければならないことを想像してください${tsn}小包を配布するさまざまな都市。これらの都市は、グラフの頂点と考えることができます。すべての都市が道路で接続されている場合、これはので、 ${tsn} ×( ${tsn} – 1)2 = ${tsn*(tsn-1)/2}合計でエッジ。

配送トラックは、すべての都市を任意の順序で訪問する必要があります。ケーニヒスベルク橋の問題では、 すべてのエッジ_に沿っ正確に1本のパスを検索する必要がありました。ここで、 _すべての頂点を 1回だけ訪問するパスを見つけたいと思います。これらのパスは、 ハミルトニアンサイクルと呼ばれます。

完全なグラフのハミルトニアンサイクルには、無数の異なる可能性があります。実際、任意の頂点を開始頂点として選択し、残りの都市を任意の順序で選択できます。

Diagram coming soon…

Diagram Coming Soon…

グラフで${tsn1}都市、すべてのハミルトニアンサイクルには、 ${tsn1}都市。さて、

    これは、合計で、 ${tsnPaths(tsn1)}可能なパス。この製品の略記は${tsn1} !または${tsn1} 階乗

    別の都市を経由せずに、2つの都市間を直接移動することは不可能だと想像できます。その場合、完全なグラフはもはや存在せず、ハミルトニアンサイクルが存在するとしても、その数を見つけることははるかに困難になります。

    これまでのところ、一部の都市が他の都市よりも離れている可能性があるという事実を無視してきました。実生活では、しかし、これは非常に重要な考慮事項です:私たちは_すべての_パスを見つけるにしたくないが、我々は最短1を見つけたいです。これは巡回セールスマン問題と呼ばれます。輸送と物流だけでなく、トランジスタをマイクロチップに配置するとき、より高速なコンピュータを作るとき、またはDNAの構造を分析するときにも解決する必要があります。

    簡単な方法の1つは、考えられるすべてのパスを試し、それぞれの長さを見つけて、最短のパスを選択することです。しかし、私たちはそれを示しただけです。 ${tsn2}ある都市${tsn2} ! = ${factorial(tsn2)}可能なパス。数百または数千の頂点があると、強力なコンピュータを使用しても、考えられるすべてのパスを試すことは不可能になります。

    残念ながら、巡回セールスマン問題を解決するためのより効率的なアルゴリズムはありません。代わりに、数学者やコンピューター科学者は、たとえ最善策ではない場合でも、 _適切な_解決策を見つけるさまざまなアルゴリズムを開発しました。近似解のみを与えるこれらのアルゴリズムは、 ヒューリスティックスと呼ばれます。

    このマップで都市を並べ替えて、都市間の最短経路がどのように変化するかを確認してください。都市をタップして削除したり、地図上の任意の場所をクリックして都市を追加したりできます(最大8つ)。

    貪欲アルゴリズム (または最近傍アルゴリズム)は非常に単純です。ランダムな都市から始めて、これまでに訪れたことのない最も近い都市に連続して移動します。すべての都市を訪れたら、立ち止まります。

    アニメーションはもうすぐ…

    平均して、貪欲なアルゴリズムを使用して検出されたパスは、可能な最短パスより25%長いことを示すことができます。

    2-Optアルゴリズムは、ランダムな可能なパスから始まります。次に、2つのエッジを繰り返し選択し、パスの長さが短くなる場合はそれらを入れ替えます。エッジのペアを交換して、長さをそれ以上短くできない場合は停止します。

    アニメーションはもうすぐ…

    コンピュータが存在するずっと前から、Natureはアリのコロニーなど、さまざまな場所の間の最適な経路を見つけるための賢い方法を見つけていました。

    アリは、巣と可能な食料源との間の可能な限り最短のルートを見つけたいと考えています。彼らは彼らが彼らの道に沿って残し、他のアリが従うことができる化学物質を介して互いに通信することができます。

    *アリのコロニーは、最初はランダムな方向に移動する多くのスカウトを送り出します。食べ物を見つけると、フェロモンの痕跡を残して戻ってきます。 *他のアリは、トレイルを見つけたときにトレイルをたどる傾向があります。彼らは帰りの旅でより多くのフェロモンを堆積させ、道を強化します。 *時間の経過とともに、フェロモンは蒸発します。経路が長いほど、アリがそれに沿って移動する時間が長くなるため、フェロモンが蒸発する時間が長くなります。一方、短いパスはより速く強化されるため、強度はより速く増加します。

    図はすぐに来る…

    Ant Colony System(ACS)アルゴリズムは、多くの「仮想」アリを使用して、コンピューターでこの動作を再現しようとします。彼らは巡回セールスマン問題の非常に良い解決策をすぐに見つけることができます。

    ACSアルゴリズムの特に便利な特性の1つは、継続的に実行でき、グラフの変更にリアルタイムで適応できることです。これらの変更は、自動車事故や道路網の通行止め、またはコンピュータネットワーク上のWebサーバーへのトラフィックの急増によって引き起こされる可能性があります。

    巡回セールスマン問題はNP困難です。つまり、コンピューターで解決することは非常に困難です(少なくとも多数の都市では)。

    高速で正確なアルゴリズムを見つけることは、コンピュータサイエンスの分野で深刻な意味を持ちます。つまり、 すべての NP困難な問題に対して高速なアルゴリズムがあるということです。また、特定の問題がコンピュータにとって非常に困難であると考えられているという事実に依存しているため、インターネットセキュリティのほとんどが役に立たなくなります。

    巡回セールスマン問題を解決する高速アルゴリズムを見つけると、数学とコンピューターサイエンスで最も有名な未解決問題の1つであるP対NP問題も解決されます。これは、7つのミレニアム賞問題の 1つであり、それぞれが100万ドルの賞金を獲得しています。