Toy problemsは役立たずか(Floydの問題・ネタバレ)


U = {√1, √2, …, √50}を2つのグループに分け、グループ毎の和を求める。和の差がなるべく小さくなるようなグループ分けを、制限時間10秒で見つけよ。

1881526917先日紹介したFloyd問題です。

10秒という制限時間で、2の49乗個の候補の中から最良のものを見つけ出すのは、1977年当時のコンピュータでは難しかったはずです。そこでKnuthは、以下のような工夫をしました。

  1. まず小数部分を近づけることを目指し、その後で整数部分を近づける。(この問題では結果オーライ。√40までの場合はうまくいかない。)
  2. I = {√1, √4, √9, √16, √25, √36, √49}は、和の整数部分にしか関与しないから後で考えることにする。
  3. Uを2つのグループAとBに分け、Aの部分集合とBの部分集合の合計の小数部分を、全体の合計の半分の小数部分に近づける。
  4. Aの部分集合の小数部分をすべて記録しておき、Bの部分集合に対して、上の条件に会うようなAの部分集合がすぐに見つかるようにする。
  5. 部分集合の生成にはグレイコードを使う。
  6. X = {√2, √8, √18, √32, √50}の組み合わせでできる和は16通りしかないことを利用する。同様に、Y = {√3, √12, √27, √48}の組み合わせでできる和は11通りしかないことも利用する。
  7. 集合をA = X ∪ Y ∪ {√5, √6, √7, √10, √11, √13, √14, √15}、B = U – I – Aとする。

今日のコンピュータは当時と比べればはるかに強力なので、これらの工夫のうちの1から4を採用するだけで、あとは富豪的なプログラムでも最良解を見つけるのに5秒とかかりません(コード)。本稿執筆時点のideone.comで約2.5秒(double)あるいは約2.8秒(long double)、私のデスクトップ(Core i7 950 3.07Ghz)のVisual C++で約1.3秒でした(いずれもシングルスレッド)。

4774157155Aの部分集合の記録には、C++11で導入されたunordered_multimapを使いました。キーAのサブセット和の小数部分8桁を、値はサブセットを表現する整数とサブセット和のpairです(この実装では、mapよりunordered_mapのほうがかなり速いです)。sizeAを20にしたり、keyを小数点以下8桁にすると速いのは、動かしてみてわかったことです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です