スライド

バイオプログラミング第２
慶應義塾大学理工学部
生命情報学科
榊原康文、佐藤健吾
パズルを解く
• 人間の場合
– 定石や勘で解くことができる
• コンピュータの場合
– すべての場合をしらみ潰しで数え上げる
バックトラック法
• 深さ優先探索を使って、すべてのパターンを
系統的に探索する
これ以上先に
進めない状態
次の状態
初期状態
終了状態
取りうるすべての操作
課題１：Nクイーン問題
• N×Nのチェス盤上にN個のクイーンを配置す
る。この時、どの駒も他の駒に取られるような
位置にあってはいけない。
◯
◯
◯
◯
◯
◯
◯
◯
状態をどのように表すか？
• N×Nの２次元配列 int board[N][N]
– board[i][j]=0の時： (i,j)に駒はない
– bodar[i][j]≠0の時： (i,j)に駒がある
新しい駒を置けるか判定する
• 駒の利き筋に他の駒がないかを調べる
x=i
◯
y=x+j-i
◯
◯
y=j
◯
y=-x+i+j
(i,j)
バックトラック法
• 深さ優先探索を使って、すべてのパターンを
駒を置けない状態
系統的に探索する
2列目
１列目
何も置いて
いない状態
(1,1)
(1,2)
(2,1)
(2,2)
(2,3)
(2,4)
(1,3)
(2,N)
(1,N)
N列目
バックトラック法
• 再帰関数を使って深さ優先探索を実現
function NQueen(x)
if すべての列が終わった
解をカウントする
return
for each ys.t. (x,y)に駒を置ける
(x,y)に駒を置く
NQueen(x+1)
(x,y)の駒を退かす
endfor
endfunction
x=Nかどうかを調べる
(x,y)の利き筋に他の駒
があるかを調べる
状態変数boardの値を
変える
課題１（必須）
• Nクイーン問題を解いて、解の個数を計算す
るプログラムを作成せよ。
– レポートにはN=1~8までの計算結果を載せること。
• （余裕がある人）
状態変数を工夫すると高速化することができ
る。それにより可能な限り大きなNに挑戦せよ。
課題２：宣教師と土人
• N人の宣教師とN人の土人が川を渡ろうとして
いる。ボートはM人乗りである。ただし、川の
両岸、ボートにおいて宣教師よりも土人の人
数が多くなった場合には宣教師が襲われてし
まう。安全に川を渡るための最短の手順を求
めよ。
宣教師と土人
• N=3, M=2の場合
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
MMMCCC|<_>
MMMC |
MMMCC |<_>
MMM
|
MMMC |<_>
M C |
MM CC |<_>
CC |
CCC|<_>
C |
CC |<_>
|
|
<_>|
CC
|
C
<_>|
CCC
|
CC
<_>|MM CC
|M C
<_>|MMMC
|MMM
<_>|MMMCC
|MMMC
<_>|MMMCCC
解の求め方
• 対象の状態を表した探索木を探索する
これ以上先に
進めない状態
次の状態
初期状態
終了状態
取りうるすべての操作
状態をどのように表すか？
• 両岸に何人ずついるか？
• ボートがどちら岸にあるか？
堂々巡りを許さない
• 過去の状態と同じ状態へは遷移しない
初期状態
取りうるすべての操作
最短の手順を求める
• 幅優先探索
• 反復深化深さ優先探索
深さ優先探索
• すべてのパターンを系統的に探索する
初期状態
幅優先探索
• 最も浅い（＝最短）解が最初に見つかる
初期状態
反復深化深さ優先探索
• 深さNまでに制限して深さ優先探索を行い、N
を1ずつ増やしていく。最初に解に辿り着いた
Nが最短となる。
初期状態
深さ1まで
深さ2まで
深さ3まで
課題２（発展）
• 宣教師と土人問題を解くプログラムを作成し、
(N=3,M=2),(N=4,M=3),(N=5,M=2),(N=5,
M=3)などの場合の最短解を解け。

Download Report