前回に引き続き必要照明数について。
これまでの記事:
wが十分に大きい時(w≧h+1の時)は、前回の議論が使える形で、必要照明数は⌈(w+h)/2⌉。
w=2
ジグザグの形を「nL」型と「nS」型と命名する。前につける「n」は、図2の点線がいくつ目の点線であるかを表す。例えばnLに対して、先端のマスに注目する。先端のマスを照らす照明の配置は図2に示している2通りしかない。それぞれの場合について、残った図形は(n-1)Lと(n-2)Sになる。これがすべての可能性であるため、nLの必要照明数は、(n-1)Lの必要照明数+1、または、(n-2)Sの必要照明数+1の内の、小さい方になる(等しい場合はどちらと考えても良い)。
nS型の図形も同じように小さい図形の必要照明数に帰着できる。
問題はnが小さい時である。ここでは、n=0とn=1の必要照明数を直接計算してしまう(図3)。
ここまでわかると、ダイクストラ法の要領で必要照明数を次々と計算していくことができる。
nL型は(そしてnS型も)周期3の形になった(純算術周期)。nLとnSの必要照明数の計算にはn-1とn-2の結果しか使用しないことと、nLとnSの両方が周期3になっていることから、確認ができる。
w=3
w=3も同じ要領で調べることができる(図5、図6、図7)。AとAバー、BとBバーはおおむね対称に機能するが、右下のコーナーの終端条件で違いが現れる。計算の初期条件だけ気を付ける必要がある(図7)。小さいnのエッジを記載する際、便宜上、1マスの図形をθ、0マスの図形をΦと記述している。
少し計算が面倒なのでプログラムを書いた(図8)。周期6になっている(内部変数も周期6になっているため、真に周期6である)。
総括
wとhに対する必要照明数のマップを図9にまとめる。
白い三角形領域は不明である(太字の部分は個別に調べた結果を記載している)。単調増加かどうかもわかっていない。赤い線で示したように、斜めにまっすぐ等高線が並ぶと予想する場合、傾きが一定になりそうである(w=2, w=3の列も、対角線部分も、線形に増加するため)。
次の記事:照明 (5) - pzdcの雑記