もう一つの代表的な応用分野として、組み合わせ最適化問題があります。ここで は、典型的な組み合わせ最... もう一つの代表的な応用分野として、組み合わせ最適化問題があります。ここで は、典型的な組み合わせ最適化問題として、巡回セールスマン問題への応用につ いて紹介します。 巡回セールスマン問題とは、図に示すように多数の「都市」があるときに、一人 の「セールスマン」が全ての都市を一回ずつ訪問して、最後に出発点に戻って来 るための最短経路を探す問題です。 都市数をとすると、可能な経路の総数は通り存在します。 が小さいとき には、全ての組み合わせを調べて最短経路を探すこともできますが、 が大きく なるにつれて、この組み合わせ総数は爆発的に増加し、全てを調べることは事実 上不可能になります。例えば、のときには、組み合わせ総数は181440通りで すが、 のときには、のオーダーになってしまいます。このような 全てを調べることができないような問題には GAは非常に有効であると言われて います。 巡回セールス
記事へのコメント0件
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています