Experience the CMOS Annealing Machine

第3章 アニーリングマシンと2次式と離散値の関係

第4節 離散値と連続値の違い

組合せ最適化問題が難しい理由に「離散値である」ということがあります。組合せという概念は、1つ1つの要素の関係のことを指しています。要素が1つ1つ分かれているという特徴があります。このような特徴を、数学の学問であつかう概念としては「離散値」といいます。離散値の対義語は、「連続値」といいます。例えば、3人家族で1枚のピザを分ける時を考えてみましょう。その場合、ピザを3等分すればみんなで公平に食べることが出来ます。また、もしそこにお友達が2人来た時には、ピザを5等分すればみんなで公平に食べることが出来ます。ピザは連続的に繋がっているおかげで、人数が変わってもうまく分けることができます。では、ショートケーキが3個あるときを考えてみましょう。3人家族であれば、1人1つずつに分ければ公平に食べることが出来ます。一方、そこに2人のお友達が遊びに来ると3個のショートケーキを5人で分ける必要があり、なかなか公平に分けて食べるということは難しくなります。つまり、これはショートケーキを公平に分割することが出来ないことに起因しています。これが、離散の問題です。

また、別の例では、クラスのメンバを2つのチームに分けようとしたとき、メンバ数が偶数であれば公平に2つのチームに分けることが出来ますが、メンバ数が奇数だと公平に2つのチームに分けるのは難しくなります。これも離散の問題です。

現実社会では離散で考えないといけない問題と連続で考えないといけない問題が絡み合って存在しています。身近な物理現象においては連続値の変化がよく見られます。ここで第1章の最適化問題の5. 親子丼問題を考えてみましょう。親子丼を作るのにあんを熱しすぎると卵黄が固まり、次に卵白が固まってくるのですが、固まり方がちょうどよい具合で仕上げたいという場合、最適な温度および加熱時間は連続値ということができます。温度の課題は上昇していくのをどこで止めるかを決めるのが目的なので、組合せではありません。逆説的に結論付けると、親子丼問題と違い、組合せ最適化問題は、物理現象ではなく人工的な操作ゆえの問題であることが多いともいえます。親子丼問題は非常に身近な簡単な例ですが、もう1つの側面としては、連続値の問題は目視で確認し得ないような微粒子やミクロ世界などの高度なシミュレーション計算や、機械学習などに多く潜在しています。

シェアする/フィードバックする