よくプレゼン資料とかで、xxxを最適化する必要がある、とかよく使っていて、聞こえはよく何となく説得力のある言葉だが、何をどう最適化するの？というところまで踏み込んで議論してないときが多い。実際、最適化というのは難しいし、計算量も必要になるし、課題解決の中でも難しい問題だと思う。AIでも今後最適化は重要なキーワードになるし、今量子コンピュータについて調べだしているので、自分の中でも一度整理をしてみる。
組み合わせ最適化とはなにか？
最適化とは、様々な制約下で多くの選択肢の中から、最も価値を高くする変数の値（組合せ）を求めること。組み合わせ最適化は、最適化の中でも順序や割当など組み合わせ的なものを最適化すること。例えば宅配トラックの配送計画、カーナビの経路探索、シフトのスケジューリング、荷物の詰め方など、組み合わせ最適が必要なところが世の中にはたくさんある。最適化によって、単に時間や効率性が改善されることだけでなくて、最近は配送回数を減らすことでCO2を削減できるとか、人員シフトの最適化で働き方を改革するとか、生産計画を最適化して製品の作りすぎや在庫を削減するなど、最適化の目的も広がっている。
問題を解くことの難しさ具合
組み合わせ最適の際に、必要な条件や要素の組み合わせが増加していって、計算量が爆発することを組み合わせ爆発という。では、どのような時に爆発するかというと、計算量（時間）が問題の規模の指数関数または階乗に比例するようなケース。逆に多項式時間で解ける問題、Nk（kは定数）などは計算時間が現実的な時間で見積もることができる。下のグラフを見ても、多項式時間（多項式で計算時間を見積もれる）と指数時間の違いのイメージがつかめると思う。
そして問題の複雑さの尺度を下記の計算量の複雑性の集合で表している。このあたりは数学の世界なので、中々理解は難しいので、具体的にどのような問題があるのかを理解した方がよいかもしれない。
代表的な問題
以下は代表的な組み合わせ最適。
- 最短経路問題 – P：与えられたネットワーク上でコスト（距離、費用、時間）が最小となる経路探索。鉄道の経路案内やカーナビゲーションなど。
- 運搬経路問題 – NP困難：複数の顧客に対して複数の車両での荷物配送で、総コストが最小となる経路の探索。店舗への配送、宅配・郵便・新聞配達、ごみ収集など。
- 巡回セールスマン問題 – NP困難 ：一筆書きで最小コストを探索する。
- 勤務スケジューリング問題 – NP困難：看護師や添乗員などのスケジューリング問題。
- ナップサック問題 – NP困難：容量が一定のナップサックに重さと価値が決まっている複数の荷物を詰め込む時に価値を最大にする詰め方の探索。
最後に
今後量子コンピュータの知識を深めていくにあたって、最低限の組み合わせ最適化の知識について整理をしてみた。整理しながら考えてみると、結局ほとんどの業務上の問題って、限られた制約やリソースの中で最大な利得を得るための最適化問題にいきつくような気がする。なので、プレゼンで最適化ということで結論付けるのも当たり前な気がする。一方で多くの問題はNP困難に分類され、最適化が難しいという現実もある。なので、プレゼンでの結論は、最適化をどうやって実現するかがないと意味がない結論を述べているのかもしれない。つまり、これからは最適化できたものが勝つということかもしれない。