6/20 MIKUセミナー 一番簡単な難問

第八章 一番簡単な難問
 
いくつかある正の整数を2群に分けたい、ということでこちらに分割プログラムを書いた。
 
本中では、与えられたいくつかの正の整数を、和が等しくなるように2群に分割したい。
ここで、和がR的に書くと、floor(sum/2)に一致するような組み合わせを探す。
これを、完璧な分割、と定義する。
このとき、
1:存在するか、しないか
2:存在するなら何通りか
3:存在するなら、n個(nは1以上)見つけるまでやる
4:1つ見つけたら、連鎖的に見つかるか(ちょっと似た話
とある。
本中で登場したアルゴリズムは、
1:欲張り
2:差分(樹形図を書くのはわかりやすかった。引く回数を偶奇でわける。)
3:力任せにゴリゴリ
とあるが、これらのアルゴリズムの善し悪しを決める指標は何か、ということで出てきた話題が、ある数のまとまりを与えられたときに、完璧な分割が存在していて、それを拾いだすことができるか(感度)の高さというものが考えられそうだ。
力任せにゴリゴリやるのは、すべての場合の数を出し尽くすので、すべての完璧な分割の洗い出しができるし、逆に、完璧な分割が存在しないことも証明できる。しかし、本中でも書かれているようにこれはNP問題であり、難しい。
これできたら医学やめてる。
欲張りと差分は、完璧な分割が存在しないときに、完璧な分割が存在しないことを言うのは難しそうだ。
 
2進法で表記したときの、分割される整数の代表値をm、分割される整数の個数をnとしたら、\frac{m}{n}がこの分割問題の難しさを表している(相転移がおきる閾値)。
本中では、幼少時代に草野球チームを均等に2等分できたのは、子供の能力値(が数値化できるとして)がまあ数倍〜数百倍の差にとどまっていて、それの底2の対数を取って2チーム(18人)で割れば\frac{m}{n}が小さくなるから、適当な分割方法を選ぶことができた、といっている。
確かに、あやふやな記憶を辿ると、バスケットボール陸上競技でもっとも個人の実力差がゲームに反映されるスポーツである。異論は認める。
能力の数値化が難しいところだが、1チームを構成する要員が5人というのが、nを小さくすることで\frac{m}{n}が大きくなってしまう。
逆に、サッカーは個人の実力差がゲームに反映されにくいスポーツである。異論は認める。足でボールを扱う、ということで、能力差の開きが小さそうだし、人数も11人なのでまあそうか。
上のスポーツの例は、既に分割し終わっているが、例えば、離散的なものを2分割することから発展して、連続的なものを複数に分割することを考えると、全身の臓器に血液が分布するとすると、脳に20%、肝臓に10%、腎臓に...とか、血管や気管支が2分割を延々とすることを考えると、適当な血液配分というものは今回の分割問題に通じるところがありそう。
 
と思ったり。