|
|
> No.1485[元記事へ]
永野護さんへのお返事です。
> 8パズル（3×3)を解くプログラムをつくっています。
千日手は、過去と同じ盤面になって無限ループになるからです。
履歴をとって、チェックする必要があります。
評価関数はどちらを使ってもうまくいかない場合があります。
局所的な判断ですから、それが大局的に最適かどうかは分かりません。
たとえば、
DATA 6,2,9
DATA 1,7,3
DATA 5,4,8
の場合は、解けません。
マンハッタン距離によるサンプル
LET M=3 !MxNパズル
LET N=3
!DATA 1,6,2 !開始の盤面 ※9は空きを意味する
!DATA 5,7,3
!DATA 9,4,8
DATA 6,9,2
DATA 1,7,3
DATA 5,4,8
DIM B(M*N)
MAT READ B
DATA 1,2,3 !終了の盤面
DATA 4,5,6
DATA 7,8,9
DIM G(M*N)
MAT READ G
DIM H(0 TO 1000,M*N) !盤面の履歴（手順）
CALL hill_climb_search(0,M,N,B,G,H)
END
EXTERNAL SUB hill_climb_search(p,M,N,B(),G(),H(,)) !山登り法
PRINT p;"手" !debug
!!!IF p>=100 THEN EXIT SUB !上限を設定する
FOR j=1 TO M*N !p手目の盤面を記録する
LET H(p,j)=B(j)
NEXT j
LET C=0 !不一致の駒（数字）の枚数
FOR i=1 TO M*N
IF B(i)<>G(i) THEN LET C=C+1
IF B(i)=9 THEN LET sp=i !空きを探す
NEXT i
IF C=0 THEN !終了の盤面なら
FOR i=p TO 0 STEP -1 !履歴（手順）を表示する
PRINT i;": ";
FOR j=1 TO M*N !盤面を表示する
PRINT H(i,j);
NEXT j
PRINT
NEXT i
!STOP !１つのみ!!!
ELSE
DIM S(M*N) !save it
MAT S=B
LET E0=cost(M,N,B,G) !現状の盤面の評価値を得る
!空きの上下左右の位置にある駒（数字）を移動させる
PRINT sp !debug
IF sp>N THEN !１行目以外なら、上の数字を移動させる
LET B(sp)=B(sp-M)
LET B(sp-M)=9
IF cost(M,N,B,G)<=E0 THEN !評価値が良くなれば
MAT PRINT B; !debug
CALL history(p,M,N,B,H, rc) !新規の盤面なら
IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
END IF
MAT B=S !restore it
END IF
IF sp<=M*N-N THEN !M行目以外なら、下の数字を移動させる
LET B(sp)=B(sp+M)
LET B(sp+M)=9
IF cost(M,N,B,G)<=E0 THEN
MAT PRINT B; !debug
CALL history(p,M,N,B,H, rc)
IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
END IF
MAT B=S
END IF
IF MOD(sp-1,M)>0 THEN !１列目以外なら、左の数字を移動させる
LET B(sp)=B(sp-1)
LET B(sp-1)=9
IF cost(M,N,B,G)<=E0 THEN
MAT PRINT B; !debug
CALL history(p,M,N,B,H, rc)
IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
END IF
MAT B=S
END IF
IF MOD(sp-1,M)<M-1 THEN !N列目以外なら、右の数字を移動させる
LET B(sp)=B(sp+1)
LET B(sp+1)=9
IF cost(M,N,B,G)<=E0 THEN
MAT PRINT B; !debug
CALL history(p,M,N,B,H, rc)
IF rc=0 THEN CALL hill_climb_search(p+1,M,N,B,G,H)
END IF
MAT B=S
END IF
END IF
END SUB
EXTERNAL SUB history(p,M,N,B(),H(,), rc) !同じ盤面かどうか確認する
LET rc=1
FOR i=0 TO p
FOR j=1 TO M*N
IF H(i,j)<>B(j) THEN EXIT FOR !並びが異なるなら
NEXT j
IF j>M*N THEN EXIT SUB !既出なら
NEXT i
LET rc=0
END SUB
EXTERNAL FUNCTION cost(M,N,B(),G()) !評価関数
LET c=0
FOR i=1 TO M*N
LET Bx=MOD(B(i)-1,N) !列番号0～N-1
LET By=INT((B(i)-1)/M) !行番号0～M-1
LET Gx=MOD(G(i)-1,N)
LET Gy=INT((G(i)-1)/M)
!!!PRINT Bx;By; Gx;Gy !debug
LET c=c+ABS(Bx-Gx)+ABS(By-Gy) !マンハッタン距離
NEXT i
LET cost=c
END FUNCTION
|
|