詰め込み選手権 ―― ポリオミノを長方形に敷き詰める、四つのアルゴリズムの勝負

テトリスのように、いろいろな形のピースを長方形の枠にすき間なく詰める。あのパズルは、工場では板金や生地の板取り（材料の板から部品の形をむだなく切り出す配置決め、ネスティングとも呼ばれます）として毎日解かれています。すき間はそのまま端材、つまり材料のむだですから、詰め方を少し良くして歩留まり（一枚の材料からどれだけ部品が取れるかの割合）が上がると、その分がコストに効いてきます。

おもちゃ売り場でも、さまざまな木片やプラスチック片を、ぴったり枠にはめ込むパズルとしてよく見かけます。

前回はジョブショップ・スケジューリングという工程の順番決めを、貪欲・焼きなまし・遺伝的アルゴリズム・厳密解の四つに解かせて競わせました。今回はその続きで、同じ四つに、テトリス的なピースの詰め込みを競わせます。問題も解き方もすべて Python で自作し、外部のデータは使わず、固定シードの乱数で問題を作っているので、同じコードなら同じ問題を再現できます。

先に言っておくと、今回は少し意外な結果になりました。前回は強かった焼きなましと遺伝的アルゴリズムが、今回はある場面でそろって足踏みします。代わりにどの手法が詰め切るのかは、盤面を小さいものから大きいものへ広げながら見ていきます。

問題と、少しずるい作り方

盤面は縦横のマスに区切った長方形です。ピースはマスがいくつか連結した塊（ポリオミノ）で、回転と反転をして置けます。目的は、置いたピースが覆えたマスの割合、つまり占有率をできるだけ高くすることです。すき間が少ないほど良い、という素直な指標です。実装では、盤面を縦横のマス数ぶんのビットを並べた一つの整数として持ち、埋まっているマスを 1、空きを 0 としました。ピースの置き方も、覆うマスを 1 にしたビット列で表します。この二つの論理積を取ると、重なるマスがあればそこで 1 と 1 が揃って結果が 0 になりません。逆に 0 なら、埋まったマスと一つも重ならない、すなわち置けるということです。この判定が一度の演算で済むので、何千回とくり返す占有率の測定を軽くできます。Python の整数は桁数に上限がないので、196 マスの盤面でも 196 ビットの整数一つにそのまま入ります。

問題の作り方に一つ工夫を入れました。ランダムなピースを適当に持ってくるのではなく、盤面そのものをランダムに連結した破片へ切り分けて、それをピースの集まりにしています。こうすると、切り分けた破片を元どおりに戻せば盤面をぴったり覆えるので、占有率 100% の敷き詰めが必ず存在します。解く側はその元の並びを知らないまま、破片を組み直します。最適が 100% だと分かっているので、どの手法がどこまで近づけたかを、そのまま比べられます。

出場するのは前回と同じ四つです。

貪欲法は、ピースの並べ順をいくつか決めて（大きいものから、など）、上・左から順に、置ける最初の場所へ詰めていきます。速いですが、後になって残った半端なすき間には融通が利きません。上・左から詰めるこのやり方は、長方形の枠にピースを詰めるときによく使われる bottom-left fill（決めた隅から順に詰めていく素朴な方法）と考え方が同じです。呼び名のとおり隅を左下に取ることが多いのですが、今回は盤面の上・左を隅にして、マス目の上で使っています。

焼きなましは、ピースの並びを二か所入れ替えて少しずつ変え、占有率が上がれば受け入れ、下がっても最初のうちはある確率で受け入れて、行き止まりを避けます。占有率がいったん下がる手をあえて選ぶのは、目先の改善だけを追うと、それ以上良くならない小さな山（局所最適）で止まってしまうからです。少し悪くなる回り道を許して、その山から抜ける余地を残しています。

遺伝的アルゴリズムは、ピースを並べる順番を生物の染色体に見立てます。交叉とは、成績の良い並びを二つ選んでその順番を混ぜ、新しい並びを作る操作、突然変異とは、それを少しだけ入れ替えてみる操作です。ピースの順序そのものが答えなので、混ぜたときに同じピースがだぶったり抜けたりしないよう、元の順序を保つ形の交叉（順序交叉）を使いました。

厳密解（バックトラック探索）は、少し毛色が違います。いちばん上・左の空きマスに注目して、そのマスを覆えるピースを順に当てはめ、埋まったらまた次の空きマスへ、と進みます。行き詰まったら一手戻してやり直す、いわゆるバックトラックで、盤面を完全に覆う並べ方を探します。このあと各手法の手間を「枝」の数で示しますが、枝とは、こうして一手置いてみる試みの一つ一つのことです。枝の数が少ないほど、あまり迷わずに答えへたどり着けた、と読めます。

焼きなましと遺伝的アルゴリズムは、公平のために、占有率を測る回数（並び順を盤面に置き直して数える回数のことで、あとの収束の図では評価回数と呼びます）の予算を同じ値に揃えました。焼きなましは貪欲法の並びから始め、遺伝的アルゴリズムは初期集団の一つに貪欲法の並びを入れました。

10 マス四方の盤面で、貪欲の詰め方と、完全な敷き詰めを並べてみます。

左が貪欲、右が完全な敷き詰めです。斜線のマスがすき間、つまりむだになった場所です。貪欲は大きいピースを先に置けるだけ置きますが、最後に半端なすき間が残ります。右のように隅々まで埋めるには、ピースどうしの噛み合わせを最後まで整える必要があります。

小さいうちは順当、そして中盤で番狂わせ

まず 6 マス四方（36 マス、7 ピース）の小さな盤面です。貪欲は 88.9%、焼きなましと遺伝的アルゴリズムはどちらも 100%、厳密解も 100% を、わずか 35 個の枝で出しました。ここまでは順当で、凝った手法ほどきれいに詰め切ります。

盤面が少し大きくなっても、凝った三つはそろって 100% に届くだろう、と私は思っていました。番狂わせは次の 10 マス四方（100 マス、21 ピース）で起きました。厳密解が、千三百ほどの枝をたどって 0.01 秒ほどで完全な敷き詰め（100%）を出したのに対し、焼きなましと遺伝的アルゴリズムは 96% で止まり、100% に届きませんでした。前回のジョブショップでは、この二つが真の最適に届いて、厳密解はその答え合わせ役でした。今回は立場が逆です。

なぜ詰め込みでは厳密解がこんなに強いのか。手がかりは、いちばん上・左の空きマスを、そこを覆えるピースで埋める、という進め方です。空きマスを一つ決めてしまえば、そこを埋められるピースと置き方はごく限られます。たとえば盤面の左上の角にできた空きマスなら、そこにぴったり収まるピースと向きは数えるほどしかありません。埋めれば次の空きマスがまた候補を絞る、という具合に制約が次々に伝わって、枝分かれがあまり広がらないまま、次々に埋まっていきます。

この進め方は、ピースで盤面のマスを重なりも取りこぼしもなく覆う「完全被覆（exact cover）」を解いているのに近いものです。覆うべきマスをまず一つ選び、そこを覆える候補だけに枝を伸ばす筋道は、パズルの世界では Knuth の Algorithm X として知られています。私のコードも同じ発想で、空きマスのうち、いちばん上・左の一つに狙いを絞っています。

21 ピースをただ並べる順番だけでも 5000 京通りを超えますし、置き方まで含めればもっと膨れます。それでも厳密解が実際に伸ばした枝は千三百ほどでした。空きマスを起点に候補を絞ると、闇雲に試すのとは桁違いに少ない手数で答えにたどり着けます。

一方、並びを入れ替えるだけの焼きなましや遺伝的アルゴリズムには、この絞り込みがありません。並び順から配置への変換は、ピースを順に、置ける最初の場所へ入れていくだけなので、早い段階でできた半端なすき間は、あとのピースがちょうど収まらなければそのまま残ります。最後の数マスを合わせるには、かなり前の順番まで変える必要があって、詰めの細工が利きにくいのだと思います。二つが中くらいの盤面でも、次の大きい盤面でも、ほとんど同じ値で止まったのは、手法の調整というより、並び順で表せる範囲の頭打ちに見えました。

盤面を大きくすると、こんどは厳密解が失速する

ところが、この厳密解も万能ではありません。14 マス四方（196 マス、42 ピース）まで大きくすると、10 秒の予算で百万の枝規模を探しても、完全な敷き詰めを見つけられずに時間切れになりました。組み合わせが増えて、さすがに数え上げが追いつきません。ピースで領域をきっちり覆えるかどうかを一般に判定する問題は、規模とともに手間が急に膨らむ種類の難しさ（いわゆる NP 困難）を持つと知られています。今回は最適が 100% だと分かっていてなお解き切れなかったので、形があらかじめ読めない実務では、数え上げだけで押し切るのはなおのこと難しいのだろうと思います。

ここで初めて、96% あたりで止まっていた焼きなましと遺伝的アルゴリズムの出番になります。厳密解が答えを出せない以上、今回得られた中では、その 95.9%（図では 96% に丸めています）が、いちばん詰まった配置でした。

図の下の点線が貪欲の出発点（90%）、上の破線が完全な敷き詰め（100%）です。二つの曲線はどちらも下の線から急に立ち上がり、上の破線に届かないところで平らになります。厳密解は制限時間内に完全な配置を返せませんでしたが、この二つは時間内にここまで詰められました。

成績を並べてみる

三つの盤面での占有率を並べると、優位に立つ手法が移っていくのが分かります。

小さい盤面では、厳密解と焼きなまし・遺伝的アルゴリズムがどれも 100% に届きました。中くらいの盤面になると、100% を出せたのは厳密解だけです。大きい盤面では、厳密解の棒はなく、完全な敷き詰めを見つけられずに時間切れになったことだけを示しています。四つを通して見ると、貪欲法だけはどの盤面でも一歩後ろにいて、速さと引き換えの詰めの甘さが最後まで残りました。

この勝負から見えたこと

前回のジョブショップでは焼きなましと遺伝的アルゴリズムが強く、今回の詰め込みでは、大きい盤面を除いて素朴な厳密解が強い。同じ四つの解き方で、問題を変えただけで上位が入れ替わりました。どの手法が効くかは、名前の派手さよりも、問題の構造と規模のほうで決まっているようでした。

詰め込みは、空きマスから制約が伝わりやすい問題で、そこに厳密探索がうまくはまりました。けれど盤面が大きくなれば、その厳密解も組み合わせの多さに追いつけず失速し、そこはヒューリスティクスに任せることになります。ここでいうヒューリスティクスとは、厳密に最適をつきとめるのではなく、そこそこ良い答えを手早く見つけにいくやり方のことで、焼きなましや遺伝的アルゴリズムがこれにあたります。実務の板取りでも、小さい単位なら厳密に詰め切り、大きくなったら焼きなましなどで折り合いをつける、という使い分けが自然だと思います。

ただ、今回のモデルと実際の板取りの間には、まだ距離があります。板金や生地の部品はマス目に乗った形ではなく連続した輪郭を持つので、置けるかどうかの判定には、ある部品の周りに別の部品がどこまで寄れるかを表す no-fit polygon のような道具が要ります。回転も自由とは限らず、生地の織り目や板の圧延方向（板を延ばした加工の向きで、木目のように向きで強さが変わる）のせいで向きが限られることが多いです。切断には刃の幅（切り代）があるので部品どうしを少し離す必要があり、現場では一枚にどれだけ詰めるかだけでなく、板を何枚使うかを少なくすることも目的になります。今回はこれらを省いて、マス目と占有率だけに絞った小さな模型として組みました。

次は巡回路（配送や配線で、どの順に回ると短いか、というテトリスとはまた違う形の問題）で、同じ四つを競わせてみるつもりです。問題が変われば、また上位の顔ぶれも変わるはずです。使ったコード（問題の生成、四つの解法、図の描画）はすべて自作で、GitHub に置きました（logicia32/packing-lab）。