Untitled Course巡回セールスマン問題

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

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

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

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

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

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