AIで「最短ルート」は見つかるか？　いまこそ注目すべきヒューリスティクス

　あなたが営業担当者で、名古屋市内の10ヶ所の取引先を1日で訪問しなければならないとしましょう。会社を出て、10ヶ所すべてを一度ずつ訪問し、再び会社に戻る。このとき、どの順番で訪問すれば移動距離が最も短くなるでしょうか。

　これは、「巡回セールスマン問題」と呼ばれる、最も有名な組合せ最適化問題の一つです。

　すべての順番を試せば、最短ルートを見つけることはできます。しかし、この方法は現実的ではありません。たとえば、10ヶ所の訪問先がある場合、その順番の組合せは約36万通り。20ヶ所になるとなんと2・4京通りを超えます。コンピュータにすべてを試させるには、途方もない時間がかかってしまうのです。

　そのため、最短である保証はないものの、できるだけ最短に近いルートをできるだけ早く見つけるための工夫が必要になります。

　こうした組合せ最適化問題を現実的に解くためには、「ヒューリスティクス（発見的解法）」と呼ばれる手法が用いられます。これは、最適である保証はないものの、実用上十分に満足のいく解を限られた時間で求める方法のことです。

　再び巡回セールスマン問題を例にすると、「現在地から最も近い未訪問の取引先を選ぶ」という操作をすべての取引先を回るまで繰り返せば、最短ではないものの、比較的良好なルートを短時間で得ることができます。

　実際の現場では、「数分で最短に近いルートを出せる」ことのほうが、「何時間もかけて最短ルートを出す」ことよりも重要とされる場面が少なくありません。

　いま誰もが特別な知識なしでAIを使える時代になりました。では、組合せ最適化問題を解くこともAIに任せればよいのでしょうか。

　一見、答えは「はい」のように思えます。しかし、実際には、現在でも多くの場面で、AIよりもヒューリスティクスのほうが、速く、確実に、安定して良い結果を出しています。なぜでしょうか。

　AIは、大量のデータを学習して「それらしい答え」を出すことを得意とします。一方、組合せ最適化問題では、1つ1つの解に対して厳密な制約や評価が求められ、「それっぽい」答えでは済まされないのです。たとえば、ある取引先を訪問し忘れてしまうようなルートは、当然ながら使い物になりません。

　このような理由から、現在でも多くの現場では、人間が考案した「探索の工夫」や「問題構造を上手く利用した近似解法」、つまりヒューリスティクスが、現実的かつ信頼できる手段として広く用いられているのです。

　ヒューリスティクスは、数十年前から存在する技術ですが、その価値はいまも揺らいでいません。むしろ、AIでなんでもできそうに見える時代だからこそ、人間の論理と思考によって組み立てられたアルゴリズムの力が改めて見直されています。

　すべてをAIに任せるのではなく、課題の性質に応じて道具を使い分ける、組合せ最適化のような問題においては、今後も人間の知恵が生きるヒューリスティクスが、有効な選択肢であり続けると考えられます。

【略歴】

名前：藤田　実沙

中京大学工学部電気電子工学科講師

専門分野：組合せ最適化

最終学歴：東京理科大学大学院博士後期課程修了　博士（工学）。1992年生まれ。