足す、掛ける、括弧と1だけで(その2)
「足す、掛ける、括弧と30個の1があれば任意の4桁の数を作ることができる」の続編。 後輩と話していて「枝かりには上限と下限が必要なんだ」と口走って、改めてその意味に気づいた。つまり、たとえば木を探索してコストが最小の解を探すような問題で、掘り進むにしたがってコストが上がるような状況を仮定しよう。そうすると、探索の途中でコストが他の解の「暫定的な最小のコスト」を上回ってしまったら枝かりができる。 これはどういうことか噛み砕いてみる。掘り進むにしたがってコストが増加するので、現在いる場所より先にある(かもしれない)解のコストxは現在のコストa以上である。一方、他のところでコストbの解が出ているので「最小コストの解」のコストはb以下である。 もしb < aであれば、今いるところよりも先に求める解があると仮定するとa以上b以下の値は存在しないので矛盾が起きる。だから今いるところよりも先には求める解がないと判断して先に進まずに探索を打ち切ることができる。
さて、頭によぎった不定形なモチベーションをあえて言語化すると上のようになるんだけども、ようは何らかの形で「nを表現するのには最低m個の1が必要だ」ということが言えないと枝かりはできないと考えたということです。で、とりあえず10000までで「最後にm個の1を使って作られた数」を調べてみました。これだけ自然言語で長々説明していてもコードで言うと
suf[answer.cost] = answer
の1行を追加しただけ。さて、結果は
5 6 3 * 2 6 9 3 * 3 7 12 4 * 3 8 18 3 * 3 * 2 9 27 3 * 3 * 3 10 36 4 * 3 * 3 11 54 3 * 3 * 3 * 2 12 81 3 * 3 * 3 * 3 13 108 4 * 3 * 3 * 3 14 162 3 * 3 * 3 * 3 * 2 15 243 3 * 3 * 3 * 3 * 3 16 324 4 * 3 * 3 * 3 * 3 17 486 3 * 3 * 3 * 3 * 3 * 2 18 729 3 * 3 * 3 * 3 * 3 * 3 19 972 4 * 3 * 3 * 3 * 3 * 3 20 1458 3 * 3 * 3 * 3 * 3 * 3 * 2 21 2187 3 * 3 * 3 * 3 * 3 * 3 * 3 22 2916 4 * 3 * 3 * 3 * 3 * 3 * 3 23 4374 3 * 3 * 3 * 3 * 3 * 3 * 3 * 2 24 6561 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 25 8748 4 * 3 * 3 * 3 * 3 * 3 * 3 * 3 26 9720 5 * 4 * 3 * 3 * 3 * 3 * 3 * 2 27 9990 (4 * 3 * 3 + 1) * 5 * 3 * 3 * 3 * 2 28 9999 ((4 * 3 * 3 + 1) * 5 * 3 * 2 + 1) * 3 * 3 29 9998 (4 * 4 * 4 * 4 * 3 + 1) * (4 * 3 + 1) + 1 30 9979 ((4 * 4 * 4 + 1) * 3 * 3 + 1 + 1) * (4 * 4 + 1)もちろん10000の近くでスピードダウンしているのは10000で打ち切られたせいなので除外するとm個の1で作ることのできる最大の数f(m)は
m mod 3 = 0のとき 3 ** (m / 3)となりそうです。証明略。で、これは逆関数が求めにくいのでf(m) <= f'(m) が成り立つように x = f'(m) = 3 ** (m / 3)とおいて、これの逆関数を求めます。m = log(x) / log(3) * 3。これをg(x)と置くことにします。そうすると、xを表現するのには必ずg(x)個以上の1が必要になることになります。というわけでこれで枝かりを実装。gは上に凸だからg(i)+g(i-j)はj=i/2の時に最大っぽいので、上限を超えたらbreakできるな。さて実装完了。どうなるかな？
m mod 3 = 1のとき 4 * 3 ** (int(m / 3) - 1)
m mod 3 = 2のとき 2 * 3 ** int(m / 3)
おおっ、前回のソースでは198107を求めるだけで現実的ではない時間がかかったのに、枝かりを入れたら19810723を求めるのに1.19秒で済んだ。でも本当に最小の解が求まってるかどうかはいろいろ証明せずに進んできているから怪しいなぁ。 とりあえず答えは コスト66で (((5 * 4 + 1 + 1) * (5 * 4 + 1) + 1) * (6 * 6 + 1 + 1 + 1) + 1 + 1) * (((4 * 4 + 1) * 8 + 1) * 8 + 1) なんだけど、今までの正しい例には6とか8とか出てこないしな。
ああ、特に値の小さい領域でg(x)の値で枝かりするとかりすぎてしまうようだ。
>>> suf(8) 5.6783677821431162 >>> suf(2) + suf(4) 5.6783677821431171 >>> suf(6) 4.8927892607143715 >>> suf(3) + suf(2) 4.89278926071437241000までは網羅的に計算して記録しておき、それから探索するタイプならコスト56の ((((4 * 4 + 1) * 3 * 3 + 1) * 3 + 1) * (4 * 3 + 1) * 3 + 1 + 1) * ((5 * 3 * 3 * 3 + 2) * 4 * 2 + 1) が解だと出るのでこっちのほうが正しいんだろうな。ただ、これがファイナルアンサーかどうかはわからないね。
まぁ、19810723 = (((((1 + 1 + 1 + 1) * (1 + 1 + 1 + 1) + 1) * (1 + 1 + 1) * (1 + 1 + 1) + 1) * (1 + 1 + 1) + 1) * ((1 + 1 + 1 + 1) * (1 + 1 + 1) + 1) * (1 + 1 + 1) + 1 + 1) * (((1 + 1 + 1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) + 1 + 1) * (1 + 1 + 1 + 1) * (1 + 1) + 1)なのは嘘ではないので今日のところはこれでよしとしよう。
314159265の計算でMemory Error。これはrangeがリストを作ろうとしてメモリが足りなくなっているせい。イテレータのxrangeに変えれば3141592653も計算できた。しかし31415926535の計算ではOverflowError: long int too large to convert to intときた。xrangeが受け取ることのできる引数の範囲を超えたらしい。xrangeの実装がまずいんだな、intに変換しないでPyLongのまま保持すればいいのに。バージョン2.4ではもう直っているかもしれないけど、とりあえずforを使わずにwhileにすればいいね。
今日たどり着いたゴール。 314159265358979 = (((((1 + 1 + 1 + 1) * (1 + 1 + 1) + 1) * (1 + 1 + 1) * (1 + 1 + 1 + 1) * (1 + 1 + 1 + 1) * (1 + 1) + 1) * ((1 + 1 + 1 + 1) * (1 + 1 + 1 + 1) + 1) * (1 + 1 + 1) * (1 + 1 + 1) + 1 + 1) * (((1 + 1 + 1 + 1) * (1 + 1 + 1) + 1) * (1 + 1 + 1) * (1 + 1 + 1) + 1) * (1 + 1 + 1) + 1) * (((((1 + 1 + 1 + 1) * (1 + 1 + 1 + 1) + 1) * (1 + 1 + 1 + 1) * (1 + 1 + 1) * (1 + 1) + 1) * (1 + 1 + 1 + 1) * (1 + 1 + 1) + 1) * ((1 + 1 + 1 + 1 + 1) * (1 + 1) + 1) * (1 + 1) + 1) * (((1 + 1 + 1) * (1 + 1) + 1) * (1 + 1 + 1) * (1 + 1) + 1) を計算するのに23.3秒。