直曲ループ

鉛筆パズルの整数計画法による解法定式化集９０．
直曲ループ
解答
例題（2015.6.30毎日新聞より）
直
曲
直
直
曲
直
曲
曲
直
直
曲
曲
曲
直
直
曲
曲
直
曲
直
曲
曲
ルール
黒い点と「直」「曲」が書かれた白い丸をタテかヨコに結び、枝別れのない大きな一つのループを作る。
①「直」の丸では線は直進し、「曲」の丸では線は90度曲がる。
②白い丸はすべて通る。黒い点は通らずに余るものがあってもよい。
③同じところを２度以上通ることはできない。
「ましゅ」を簡略化したようなパズルである。
Excel用に黒い点は廃止し、マスに矢印を付けて並べ、マスの中心を通る線を描かせることにする。
解答
Ｓ
Ｃ
Ｃ＝曲
Ｓ＝直
Ｓ
Ｃ
Ｓ
Ｓ
Ｃ
Ｃ
Ｃ
Ｃ
Ｓ
変数
曲直
マスの行番号をＩ、列番号をＪとして、符号にも番号を付けておく。
U(I,J) ＝1
＝0
D(I,J) ＝1
＝0
L(I,J) ＝1
＝0
R(I,J) ＝1
＝0
N(I,J) ＝K
(I,J)の矢印が上に向いているとき
〃いないとき
J →
1 2
(I,J)の矢印が下に向いているとき
〃いないとき
(I,J)の矢印が左に向いているとき
〃いないとき
(I,J)の矢印が右に向いているとき
〃いないとき
(I,J)の矢印Ｋ番目とき
I 1
↓ 2
C
3
.
.
.
S
Nr
K=2
K=1
3
K=3
4
S S
. . .
Nc
目的関数
minimize
x
（ダミー）
制約式
subject to
１．マスには矢印が付く
L(I,J)+R(I,J)+U(I,J)+D(I,J) ≦ 1
記号マスのとき
L(I,J)+R(I,J)+U(I,J)+D(I,J) ＝ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
２．マスに入る矢印は１個以下である
L(I,J+1)+R(I,J-1)+U(I+1,J)+D(I-1,J) ≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
３．矢印の先に矢印の根元が付く
L(I,J) ≦ L(I,J-1)+U(I,J-1)+D(I,J-1)
R(I,J) ≦ R(I,J+1)+U(I,J+1)+D(I,J+1)
U(I,J) ≦ U(I-1,J)+L(I-1,J)+R(I-1,J)
D(I,J) ≦ D(I+1,J)+U(I+1,J)+D(I+1,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
４．外枠から外に向かう矢印はない
L(I,1) ＝ 0
R(I,Nc) ＝ 0
U(1,J) ＝ 0
D(Nr,J) ＝ 0
(I=1,2,....Nr)
(J=1,2,....Nc)
５．曲でまがる
記号マスＫの座標を(I,J)として
L(I,J+1)
R(I,J-1)
U(I+1,J)
D(I-1,J)
≦
≦
≦
≦
U(I,J)+D(I,J)
U(I,J)+D(I,J)
L(I,J)+R(I,J)
L(I,J)+R(I,J)
(K=1,2,....Nm)
Nmは記号の総数
≦
≦
≦
≦
L(I,J)
R(I,J)
U(I,J)
D(I,J)
(K=1,2,....Nm)
６．直で直進
L(I,J+1)
R(I,J-1)
U(I+1,J)
D(I-1,J)
７．矢印に番号を振る
１番目の記号マスを集水マス(I0,J0)とし、１番を振る。
N(I0,J0) ＝ 1
その他 R(I,J-1) = 1 のとき N(I,J)+1 ≦ N(I,J-1)
すなわち矢印は根本側に繋がる矢印が大きくなるように付番する。
ビッグＭを使って
N(I,J)+1 ≦ N(I,J-1)+bigM*{1-bR(I,J-1)} (I=1,2,....Nr)
(J=1,2,....Nc)
同様に
bigM＝Nr*Nc とする
N(I,J)+1 ≦ N(I,J+1)+bigM*{1-bL(I,J+1)}
N(I,J)+1 ≦ N(I-1,J)+bigM*{1-bD(I-1,J)}
N(I,J)+1 ≦ N(I+1,J)+bigM*{1-bU(I+1,J)}
上下界
bounds
N(I,J)≦ bigM
変数型
binary
L(I,J) R(I,J)
U(I,J) D(I,J)
general
N(I,J)
終端
end
(I=1,2….…Nr)
(J=1,2….…Nc)
(I=1,2….…Nr)
(J=1,2….…Nc)

Download Report