照明 (9)

美術館の照明数について、せっかくプログラムを書いたので、もっと一般の形についても調べてみたい。今回は、ランダムに黒マスを置いて、数値的に評価してみた結果を紹介する。

使用する用語

この記事では、次の用語を用いる。

  • 必要照明数:(美術館のルールを満たす)照明数の最小値
  • 十分照明数:(美術館のルールを満たす)照明数の最大値
  • 照明数限界:必要照明数と十分照明数の総称
  • ギャップ:十分照明数と必要照明数の差(Δ=s-n)
  • SN比:十分照明数と必要照明数の比(r=s/n)

ランダム美術館

今まで、いくつかの基本的な形について、照明数を調べてきた。もっと一般の形に対する照明数を知りたい。しかし「一般の形」というのは範囲が広く、調べるのが難しい。なにか方針が必要である。ここでは、長方形の盤面内にランダムに黒マスを置いた状況(図1)を考えてみる。ランダム配置を考える背景には、random k-SATのように面白い現象が現れないか、という期待がある(今回の記事ではそれほど深い話にはならない)。

図1 ランダム配置の例(黒マス数=14)

まずは、正方形盤面NxNに対して、黒マスをk個配置することを考える。ここで、盤面が分断されるかどうかは気にせず、完全にランダム(全てのマスで等しい確率)に配置することに注意する。

極限での結果を整理しておく。kは、0以上N以下の値である。k=0の時は、黒マスが一つもないので、照明数(n, s)=(N, N)になる。一方で、k=Nの時は、盤面全体が黒マスで塗りつぶされるのだから、もはや美術館として意味をなさないが、あえて定義するなら(n, s)=(0, 0)になる。kが0とNの中間の値の場合は、一般に照明数(n, s)は具体的な配置に依存するだろう。そこで、今回は数値実験を繰り返し実行して統計(最小値、平均値、最大値、など)を見る。

照明数限界

図2 7x7盤面にk個入れた時の照明数限界

図2に、7x7の盤面にk個の黒マスをランダムに置いたときの、必要照明数n(青)と十分照明数s(橙)のばらつきを可視化する。横軸がkで、縦軸が照明数の値(青い方が必要照明数nで、橙の方が十分照明数s)である。擬似乱数(PCG 64bit)を使用して、各kごとに10000回ずつ実行して集計している。薄く色を塗った領域は四分位領域(0%, 25%, 75%, 100%)で、実線は平均値である。

この結果を見ると、平均必要照明数(青の実線)は、kを0から増やしていく過程で一度減少するがその後は増加して緩やかな極大を迎えた後、k=49まで直線的に落ちていく。平均十分照明数(橙の実線)はもう少し素直で、全体を通して上に凸な関数に見える。図1は全体的に「イルカ」のシルエットのようにも見える。

盤面のサイズを一般のMxNに変えたときの実験結果をいくつか見せる。

図3 5x8盤面にk個入れた時の照明数限界

図3は、5x8盤面に対する結果である。傾向は先程の図2(7x7に対する結果)と似ている(イルカ的である)が、イルカの口の部分(k=0付近)が明確に異なっている。7x7の場合には平均必要照明数(青の実線)が一度減少してから増加に転じていたが、5x8の場合には、最初の傾きがゼロで、その後緩やかに増加している。

図4 6x7盤面にk個入れた時の照明数限界

図4は、6x7盤面に対する結果である。今度は、平均必要照明数のイルカの口(k=0)での傾きはゼロだが、その後いったん減少して、その後緩やかに増加している。

図2~4以外にもいくつか調べたところ、どうやら、平均必要照明数のイルカの口での傾きは、正方形の場合だけ負になり、長方形の場合にはゼロor正になるようだ。これは、「照明」で調べたk=1の結果と整合している。他にもいくつか調べた結果、平均必要照明数は、盤面が大きくなるにつれて、また、長方形の二辺の長さの比が1から離れるにつれて、「単純」な曲線になっていく様子が観察された*1

前者(盤面が大きくなるにつれて~~)は、盤面が大きくなることでグラフの解像度が上がるため、滑らかな曲線に見えるようになっていくからだろう、と考えられる。後者(長方形の二辺の長さの比が1から離れるにつれて~~)は、正方形という形が必要照明数を大きくするうえで「都合の良い」形になっているためだろう、と考えられる。黒マスを十分にたくさん配置すれば、元の盤面が正方形であったか長方形であったかはほとんど関係がなくなるが、黒マスの数が少ない場合には、元の盤面の形が照明数にとって「都合の良い」形であるかどうかが効いてくる。正方形はかなり「特殊」な形で、必要照明数を一気に跳ね上げるのだろう。今、我々はランダム配置の影響を見たいので、ここ(元の盤面形状由来の影響)は本質でない部分である、と考える。

ギャップ

個人的に特に興味があるのは、必要照明数と十分照明数の間のひらきである。そこで、必要照明数と十分照明数の差(ギャップ)の分布を調べることにした。いくつのグラフを示す(図5~図7)。

図5 7x7盤面にk個入れた時のギャップ
図6 5x8盤面にk個入れた時のギャップ
図7 6x7盤面にk個入れた時のギャップ

ここで、青の実線は平均ギャップ値、薄い色で示している範囲は四分位領域(0%, 25%, 75%, 100%)である。図2~4と比べて、盤面の元の形に対する依存が少ない結果になった。前半で増加して後半で減少する、という単純な関数になっている。気になるのは、どこで最大値を取るのか、そしてその値はいくつか、の2点である。以降は平均ギャップ値(青い実線)に注目する。

まず、最大になる位置について調べる。図5~7を見ると、最大になる位置は共通しておおよそMN/4付近にあるように見える。そこで、盤面のサイズによらずに常にMN/4付近に来ることが期待されるが、残念ながら、盤面の元の形状が細長くなるにつれて位置が変化する現象が見られた。いくつかの例を図8~図10に示す。

図8 2x11盤面にk個入れた時のギャップ
図9 3x9盤面にk個入れた時のギャップ
図10 4x8盤面にk個入れた時のギャップ

最大になる位置とその値をプログラムで求めた結果(テキストデータ)を下に掲載する。ここで、7x8と8x8は計算量が多いため実行回数を少なく(7x8は1000回、8x8は500回実行)しており、したがって精度が低いと考えられる。2x2は、たくさん実行しても意味がない(各kに対して定数になる)ので、1000回だけ実行している。2x2と7x8と8x8を除くその他の盤面形状に対しては、各kにつき10000回ずつ実行して評価している。各盤面形状ごとに10000回も実行している理由の一つは、最大になる位置をなるべく正確に求めたかったからである。

2,2     pos=1/4=0.250000000000000       height=1.000000000000000
2,3     pos=2/6=0.333333333333333       height=0.668000000000000
2,4     pos=3/8=0.375000000000000       height=0.640400000000000
2,5     pos=4/10=0.400000000000000      height=0.680700000000000
2,6     pos=5/12=0.416666666666667      height=0.753500000000000
2,7     pos=6/14=0.428571428571429      height=0.830900000000000
2,8     pos=6/16=0.375000000000000      height=0.906600000000000
2,9     pos=7/18=0.388888888888889      height=0.994700000000000
2,10    pos=8/20=0.400000000000000      height=1.095300000000000
2,11    pos=9/22=0.409090909090909      height=1.168900000000000
3,3     pos=1/9=0.111111111111111       height=1.114900000000000
3,4     pos=3/12=0.250000000000000      height=1.248000000000000
3,5     pos=4/15=0.266666666666667      height=1.311400000000000
3,6     pos=5/18=0.277777777777778      height=1.446700000000000
3,7     pos=7/21=0.333333333333333      height=1.614100000000000
3,8     pos=8/24=0.333333333333333      height=1.768000000000000
3,9     pos=9/27=0.333333333333333      height=1.938300000000000
4,4     pos=3/16=0.187500000000000      height=1.591200000000000
4,5     pos=5/20=0.250000000000000      height=1.895800000000000
4,6     pos=6/24=0.250000000000000      height=2.133800000000000
4,7     pos=8/28=0.285714285714286      height=2.340600000000000
4,8     pos=9/32=0.281250000000000      height=2.581500000000000
5,5     pos=6/25=0.240000000000000      height=2.312000000000000
5,6     pos=8/30=0.266666666666667      height=2.694900000000000
5,7     pos=8/35=0.228571428571429      height=3.028700000000000
5,8     pos=10/40=0.250000000000000     height=3.360400000000000
6,6     pos=9/36=0.250000000000000      height=3.214700000000000
6,7     pos=10/42=0.238095238095238     height=3.675900000000000
6,8     pos=13/48=0.270833333333333     height=4.097800000000000
7,7     pos=12/49=0.244897959183673     height=4.248100000000000
7,8     pos=14/56=0.250000000000000     height=4.806000000000000
8,8     pos=14/64=0.218750000000000     height=5.430000000000000

こうして求めた、最大になる位置のリストを、下の図11にプロットする。

図11 平均ギャップの最大位置の盤面形状依存性

図11で、横軸は盤面の元の形状の面積(例えば7x7なら49)、縦軸は求めた位置である。グラフにいくつか引いている線は、長方形の片方の辺を固定してもう片方の辺を伸縮した時にたどる線を表している。この図からいくつかのことがわかる。まず、それぞれの線は、それほど単純な曲線になっていないようである。増減の激しいグラフになっている。例えば、2x2から2x7にかけては順調に増加するにもかかわらず、2x8で急に減少している。この原因として、最大になる位置の計算に誤差が生じていることが挙げられるだろう。また、そもそも位置は9/36のような有理数で求まるため、解像度が高くない、というのも理由として考えられる。このように誤差が大きいので、このグラフの詳細を掘り下げてもあまり実りがなさそうだ。

ただ、グラフをじっくりと見ていると、なにやら興味深い性質も見つかる。例えば、正方形の時に、一貫して値が低くなっていることがわかる。この理由は分かっていない。また、グラフは非常に複雑だが、全体的には0.2~0.4あたりにおおむね治まっている傾向も見て取れる。したがって、盤面の20~40%くらいが黒マスで埋まる時が、ギャップが大きくなりやすい、と言えそうだ。これも興味深い点である。ギャップは盤面の分断と関係していそうなので、イジングモデルやパーコレーションの話と関係があるのでは、とにらんでいる。

次に、最大値の値を調べる(図12)。

図12 平均ギャップの最大値の盤面形状依存性

横軸が面積、縦軸が求めた最大値である(1xNに対する結果も追加している)。面積に対して線形に近い形で増加していることがわかる。格子が奇妙に歪んでいないため、誤差の心配は少ないと思われる。

面積に対して平均ギャップの最大値が(おおむね)線形になるのは、自明な結果だろうか。例えば盤面が黒マスによって二つの領域に分断されている時、必要照明数と十分照明数は、分断された各領域の値の和になるため、ギャップもそれぞれのギャップの足し算になる。したがって、黒マスの密度が十分高い場合には面積におおむね比例しそうだ。黒マスが盤面を分断しない程度に疎な場合には、どうなるのか、さほど自明ではない。今は、「平均ギャップが大きくなりやすいような黒マス密度での平均ギャップ値」を考えているのだから、黒マスの密度がある程度高い場合に該当すると考えられ、おおむね線形になるというのは納得できる結果である。次にやることは、面積に比例しない成分を調べることである。

図13 平均ギャップ最大値の面積に対する比の面積依存性

図13では、先程の図12の縦軸を、横軸の面積の値で割ったものである。すなわち、横軸は面積で、縦軸は平均ギャップの最大値の面積に対する割合である。どの折れ線MxNも、Nが増加するにつれて定数に収束しそうな印象を持てる。これが真に収束するか、というのは興味のある部分である。

SN比

前の節では必要照明数nと十分照明数sの差(ギャップ)Δ=s-nに注目したが、比r=s/nに注目する考え方もあるだろう。照明数の考察の中では、この比をSN比と呼ぶことにする。十分照明数sは常に必要照明数n以上なので、SN比は常に1以上になる。また、2以下であることも次のようにしてわかる:正方格子では一つの照明は最大で2つの列を照らすが、各列に最大で一つしか照明を入れることができない。

いくつかの盤面形状MxNに対する結果を図14~16に示す。

図14 7x7盤面にk個入れた時のSN比
図15 5x8盤面にk個入れた時のSN比
図16 6x7盤面にk個入れた時のSN比

ギャップの傾向と似ている。盤面形状依存性を下の図17に示す。

図17 平均SN比の盤面形状依存性

縦軸と横軸の範囲は揃えている。小さい盤面では複雑な関数形になっているが、十分に大きな盤面では、どれも類似した関数形になっているように見える。

ギャップの場合と同じように調べる。関数が最大になる位置と、そこでの値のデータ(プレインテキスト)は、次の通りである。

2x2     pos=1/4=0.250000000000000       height=2.000000000000000
2x3     pos=2/6=0.333333333333333       height=1.533400000000000
2x4     pos=3/8=0.375000000000000       height=1.383533333333333
2x5     pos=4/10=0.400000000000000      height=1.330750000000000
2x6     pos=5/12=0.416666666666667      height=1.305398333333333
2x7     pos=6/14=0.428571428571429      height=1.291795000000000
2x8     pos=7/16=0.437500000000000      height=1.275316428571428
2x9     pos=8/18=0.444444444444444      height=1.270240714285714
2x10    pos=8/20=0.400000000000000      height=1.269213809523810
2x11    pos=9/22=0.409090909090909      height=1.261081468253968
3x3     pos=1/9=0.111111111111111       height=1.557450000000000
3x4     pos=3/12=0.250000000000000      height=1.523916666666667
3x5     pos=4/15=0.266666666666667      height=1.446751666666666
3x6     pos=5/18=0.277777777777778      height=1.426375000000000
3x7     pos=6/21=0.285714285714286      height=1.410031904761905
3x8     pos=8/24=0.333333333333333      height=1.397535119047619
3x9     pos=9/27=0.333333333333333      height=1.392415277777778
4x4     pos=3/16=0.187500000000000      height=1.516350000000000
4x5     pos=4/20=0.200000000000000      height=1.538295000000000
4x6     pos=6/24=0.250000000000000      height=1.516825952380952
4x7     pos=7/28=0.250000000000000      height=1.501270119047619
4x8     pos=8/32=0.250000000000000      height=1.488456507936508
5x5     pos=5/25=0.200000000000000      height=1.547783333333333
5x6     pos=6/30=0.200000000000000      height=1.569225714285714
5x7     pos=8/35=0.228571428571429      height=1.562860753968254
5x8     pos=9/40=0.225000000000000      height=1.552416984126984
6x6     pos=7/36=0.194444444444444      height=1.589464880952381
6x7     pos=8/42=0.190476190476190      height=1.601738293650794
6x8     pos=9/48=0.187500000000000      height=1.600877777777778
7x7     pos=9/49=0.183673469387755      height=1.624828730158730
7x8     pos=11/56=0.196428571428571     height=1.633186904761905
8x8     pos=11/64=0.171875000000000     height=1.659905555555556

図18 平均SN比の最大位置の盤面形状依存性

結果は平均ギャップの評価結果と似ているが、こちらは盤面が大きい時に、より小さい値に収束しそうである。SN比が最大となる黒マス密度は、ギャップが最大となる黒マス密度よりも小さくなる(らしい)、と言い換えられる。

図19 SN比最大位置とギャップ最大位置のずれ

図19は、7x7盤面にk個入れた時の照明数限界(図2と同一のグラフ)である。k=9でSN比が最大になり、k=12でギャップが最大になる。kが9から12に増える過程で、十分照明数は必要照明数よりも大きい傾きで増えているが、比率で見ると、下がっている。ただしこの変化の割合は非常に小さく、数値誤差の影響も含まれているだろう。なお、平均SN比の定義は「(平均の十分照明数)/(平均の必要照明数)」ではなくて、「平均の「(十分照明数)/(必要照明数)」」であるため、この図から推測できる値とは厳密には異なる。こういった繊細な違いによって差が生じているため、解釈は難しい印象である。

次は最大値の値を見てみる。

図19 平均SN比の最大値の盤面形状依存性

ギャップの評価の結果(面積で割った結果)と似ているが、包絡線(NxNの線)はNに対して増加傾向である。ここから考察できることは色々とありそうだ。

総括

今回は長方形盤面にランダムに黒マスを一定密度で置いたときの照明数のギャップとSN比について調べ、特に、黒マス率を変えた時の最大値について可視化を行った。そこで、いくつかの興味深い曲線(折れ線)が現れることを見た。今後は、もう少し対象を具体化して、実際にどのような場合に照明数、ギャップ、SN比が大きくなる/小さくなるのかについても調べていきたい。

*1:ここでの「単純」な曲線とは、滑らかで、山がひとつの曲線を指す。