今回は、「農夫と山羊と狼とキャベツの問題」 [*1] という、古典的なパズルを解いてみましょう。農夫が狼と山羊とキャベツを持って川の左岸にいます。農夫はこれらを川の右岸へ運ばなければいけませんが、ボートにはそのうちのひとつしか乗せることができません。狼は山羊を好んで食べるため、この 2 つを同じ岸に残すことはできません。また、山羊はキャベツを好んで食べるため、この 2 つも同じ岸に残すことはできません。この条件で、荷物をすべて右岸へ運ぶ手順を求めるのが問題です。
このパズルを深さ優先探索と幅優先探索で解いてみましょう。使用するプログラミング言語は Perl です。コンピュータに解かせる前に、自分で考えてみるのも面白いでしょう。
このパズルを深さ優先探索で解く場合、同じ移動手順を何度も繰り返すことがないように注意しなければいけません。極端な例ですが、何も工夫しないと、同じ物を持って左右の岸を往復する、といったことも起こります。この場合、過去の状態を記憶しておけば、簡単にチェックすることができます。つまり、過去のある状態と同じになった場合は、そこで探索を打ち切ればいいわけです。
次はデータ構造を考えましょう。今回は Perl を使うので、データを文字列 farmer, wolf, goat, cabbage で表しても、簡単にプログラムを作ることができます。この場合、左右の岸は配列で表し、そこに文字列を格納することになります。
これでもいいのですが、もっと簡単な方法がデータをビットで表すことです。過去に同じ状態があるかチェックするとき、整数値の比較をするだけで済みますし、状態の変更もビットのオン・オフだけなので簡単です。そこで、次のようなグローバル変数を定義します。
リスト：グローバル変数の定義 $farmaer = 0x01; # 農夫 $goat = 0x02; # 山羊 $wolf = 0x04; # 狼 $cabbage = 0x08; # キャベツ $all = 0x0f; # 全部揃った状態 # 移動リスト @move_list = ( $farmer, $goat, $wolf, $cabbage ); # 状態を保存 @left_side = (); @right_side = ();
移動リスト @move_list の先頭は、農夫だけ移動することを表します。これを忘れると解くことができません。ご注意くださいませ。
ところで、ボートを表すデータがありませんが、ボートには必ず農夫が乗り込むので、ボートのデータは農夫で代用することができます。
左右の岸は配列 @left_side, @right_side で表します。ここに過去の状態を記憶します。バックトラックで探索するときに、左右の岸を区別するのは面倒なので、探索関数には農夫がいる岸を引数 $src_side に, 農夫がいない岸を引数 $dest_side に渡します。これらの変数には @left_side, @rigth_side へのリファレンスをセットします。
探索関数を search_move とすると、次のように呼び出します。
$left_side[0] = $all; $right_side[0] = 0; search_move( 0, \@left_side, \@right_side );
第 2 引数に農夫のいる岸を、第 3 引数に農夫のいない岸を渡します。
プログラムは次のようになります。
リスト：深さ優先探索
sub search_move {
my ($num, $src_side, $dest_side) = @_;
my $src_state = $src_side->[$num];
my $dest_state = $dest_side->[$num];
foreach $move (@move_list) {
if( $move & $src_state ){
my $new_dest_state = $dest_state | $move | $farmer;
my $new_src_state = $new_dest_state ^ $all;
if( &check_state( $num, $new_src_state, $src_side ) ){
# OK
$dest_side->[$num + 1] = $new_dest_state;
$src_side->[$num + 1] = $new_src_state;
if( $right_side[$num + 1] == $all ){
&print_answer( $num + 1 );
}
# 再帰
&search_move( $num + 1, $dest_side, $src_side );
}
}
}
}
@move_list から移動する物を求め、それが移動できるかチェックします。これは AND 演算で簡単にチェックすることができます。実際に移動する場合は、対岸の状態 $dest_state に $move と $farmer のビットを立てればいいわけです。この新しい状態を $new_dest_state に格納します。この変数のビットを反転させると、$src_state から $move と $farmer を取り除いた状態になります。ビットの反転は $all と排他的論理和 (xor) を取れば求めることができます。
次に、関数 check_state で条件を満たしているかチェックします。農夫のいない状態を渡して、キャベツや山羊が無事か確認し、過去に同じ状態がないかチェックします。OK ならば状態を配列に格納して、ゴールに到達したかチェックします。ゴールは右岸と決まっているので、グローバル変数 @right_side にアクセスして確認します。
関数 print_answer はゴールまでの手順を表示します。ゴールでなければ、search_move を再帰呼び出しします。このとき、$src_side と $dest_side を逆にして渡すことに注意してくださいね。
最後に、状態をチェックする関数 check_state を示します。
リスト： 状態のチェック
sub check_state {
my ($num, $state, $side ) = @_;
my $i;
# 山羊と狼、または、山羊とキャベツを残してはいけない
if( (($state & $wolf) && ($state & $goat)) ||
(($state & $goat) && ($state & $cabbage)) ){
return 0;
}
# 同じ状態が無いかチェック
for( $i = 0; $i <= $num; $i++ ){
return 0 if $side->[$i] == $state;
}
return 1;
}
山羊と狼が残っている、または、山羊とキャベツが残っていたら、山羊もしくはキャベツが食べられてしまいます。return で 0 を返します。この条件式の場合、3 つとも残っている場合でも、移動は失敗となります。過去の状態のチェックは、配列を検索するだけなので簡単です。
実行手順の表示は簡単なので、プログラムの説明は省略します。それでは実行してみましょう。
0: [ farmer goat wolf cabbage ] [] 1: [ wolf cabbage ] [ farmer goat ] 2: [ farmer wolf cabbage ] [ goat ] 3: [ cabbage ] [ farmer goat wolf ] 4: [ farmer goat cabbage ] [ wolf ] 5: [ goat ] [ farmer wolf cabbage ] 6: [ farmer goat ] [ wolf cabbage ] 7: [] [ farmer goat wolf cabbage ]
7 手で解くことができました。このプログラムでは、解をひとつ見つけたら終了します。具体的には print_answer の最後で exit します。深さ優先探索では、最初に求まる解が最短手順とはかぎりません。最短手順を求める場合、幅優先探索 の方が適しています。
#
# farmer1.pl : 農夫と山羊と狼とキャベツの問題
#
# 単純なバックトラック版だよ
#
# bit で表す
$farmer = 0x01; # 農夫
$goat = 0x02; # 羊
$wolf = 0x04; # 狼
$cabbage = 0x08; # キャベツ
$all = 0x0f; # 全員が揃った状態
# 移動リスト
@move_list = ( $farmer, $goat, $wolf, $cabbage );
# 状態を保存
@left_side = ();
@right_side = ();
sub print_state {
my $state = shift;
my $str ="[";
if( $state & $farmer ){
$str .= " farmer ";
}
if( $state & $goat ){
$str .= " goat ";
}
if( $state & $wolf ){
$str .= " wolf ";
}
if( $state & $cabbage ){
$str .= " cabbage ";
}
$str .= "]";
printf("%-32s", $str );
}
# 表示
sub print_answer {
my $num = shift;
my $i;
for( $i = 0; $i <= $num; $i++ ){
print "$i: ";
print_state( $left_side[$i] );
print_state( $right_side[$i] );
print "\n";
}
exit( 0 );
}
# 状態のチェック
sub check_state {
my ($num, $state, $side ) = @_;
my $i;
# 羊と狼、または、羊とキャベツを残してはいけない
if( (($state & $wolf) && ($state & $goat)) ||
(($state & $goat) && ($state & $cabbage)) ){
return 0;
}
# 同じ状態が無いかチェック
for( $i = 0; $i <= $num; $i++ ){
return 0 if $side->[$i] == $state;
}
return 1;
}
# 移動手順の検索
sub search_move {
my ($num, $src_side, $dest_side) = @_;
my $src_state = $src_side->[$num];
my $dest_state = $dest_side->[$num];
foreach $move (@move_list) {
if( $move & $src_state ){
my $new_dest_state = $dest_state | $move | $farmer;
my $new_src_state = $new_dest_state ^ $all; # ビットを反転
if( &check_state( $num, $new_src_state, $src_side ) ){
# OK
$dest_side->[$num + 1] = $new_dest_state;
$src_side->[$num + 1] = $new_src_state;
if( $right_side[$num + 1] == $all ){
# 正解です
&print_answer( $num + 1 );
}
# 再帰
&search_move( $num + 1, $dest_side, $src_side );
}
}
}
}
$left_side[0] = $all;
$right_side[0] = 0;
search_move( 0, \@left_side, \@right_side );
今度は幅優先探索で解いてみましょう。ところで、深さ優先探索では右岸と左岸の状態を保存しましたが、一方の岸の状態だけ保存しておけば他方の状態を求めることができます。そこで、農夫がいる岸の状態だけを保存することにします。
リスト：グローバル変数の定義 $farmer = 0x01; # 農夫 $goat = 0x02; # 羊 $wolf = 0x04; # 狼 $cabbage = 0x08; # キャベツ $right = 0x10; # 農夫は右側 $all = 0x0f; # 全員が揃った状態 $goal = 0x1f; # ゴール @state = (); # 農夫のいる側の状態 @prev_state = (); # 手順表示用配列
状態を表す数値の第 4 ビットで、農夫が右岸にいるか左岸にいるかを表します。幅優先探索は、すべての手順について平行に探索を進めていきます。配列 @state には、最初の状態、1 手目の状態、2 手目の状態、と順番に格納されます。このままでは手順の再現が出来ないので、@prev_state にひとつ前の状態を表す番号を格納することにします。
最初の状態が $state[0] だとすると、1 手目の状態は $state[1] 以降に格納されます。このとき、$prev_state[1] には 0 を格納します。これで、$state[1] のひとつ前は $state[0] であることがわかります。答えが見つかったときは、@prev_state をたどることで、手順を再現することができます。
探索プログラムは、@state からデータを取り出して、新しい状態が生成できたら、それを @state に登録します。これを解が見つかるまで繰り返します。@state の管理は キュー (queue) を使えば簡単です。プログラムは次のようになります。
リスト：幅優先探索
sub search_move {
my $r = 0;
my $w = 1;
$state[0] = $all;
$prev_state[0] = -1;
for( ; $r < $w; $r++ ){
my $now_state = $state[$r];
foreach $move (@move_list) {
if( $now_state & $move ){
my $new_state = ($now_state ^ $goal) | $move | $farmer;
$state[$w] = $new_state;
$prev_state[$w] = $r;
if( &check_state( $w ) ){
if( $state[$w] == $goal ){
# 発見
print_answer( $w );
return;
}
$w++; # キューに登録
}
}
}
}
}
ちょっとリストが長いですが、やっていることは簡単です。最初、@state と @prev_state に初期値をセットします。$r と $w はキューを管理する変数です。$r の位置にあるデータを取り出して、新しい状態を生成できたら、$w の位置に書き込みます。$r と $w が等しい値になると、キューは空の状態になるので探索を終了します。この場合は、解を見つけることができなかったということになります。
物の移動処理は深さ優先探索の場合とほぼ同じです。$now_state と $goal の排他的論理和を取ることで、農夫の位置が対岸に移動します。状態のチェックは、$state[$w] に書き込んでから行っていますが、$w の値を +1 していないので、まだキューには登録されていません。ご注意ください。
次は手順を表示する関数 print_answer です。
リスト：手順の表示
sub print_answer {
my $num = shift;
my $r;
my $l;
if( $prev_state[$num] != -1 ){
&print_answer( $prev_state[$num] );
}
if( $state[$num] & $right ){
$r = $state[$num];
$l = $r ^ $all;
} else {
$l = $state[$num];
$r = $l ^ $all;
}
print_state( $l );
print_state( $r );
print "\n";
}
単純に @prev_state をたどると、移動手順は逆順に表示されてしまいます。そこで、再帰呼び出しで先頭まで戻り、最初から手順を表示しています。あとは難しいところはないでしょう。
それでは実行結果を示します。
[ farmer goat wolf cabbage ] [] [ wolf cabbage ] [ farmer goat ] [ farmer wolf cabbage ] [ goat ] [ cabbage ] [ farmer goat wolf ] [ farmer goat cabbage ] [ wolf ] [ goat ] [ farmer wolf cabbage ] [ farmer goat ] [ wolf cabbage ] [] [ farmer goat wolf cabbage ]
7 手で解くことができました。深さ優先探索と同じ結果でしたね。実はこのパズル、全部で 10 通りの状態しかありません。そして、右側へ全部移動することが、いちばん手数のかかる問題だったなのです。コンピュータで解くには、ちょっと簡単なパズルでしたね。
#
# farmer2.pl : 農夫と山羊と狼とキャベツの問題
#
# 幅優先探索
#
# 状態を表すビット
$farmer = 0x01; # 農夫
$goat = 0x02; # 羊
$wolf = 0x04; # 狼
$cabbage = 0x08; # キャベツ
$right = 0x10; # 農夫は右側
$all = 0x0f; # 全員が揃った状態
$goal = 0x1f; # ゴール
# 移動リスト
@move_list = ( $farmer, $goat, $wolf, $cabbage );
@state = (); # 農夫のいる側の状態
@prev_state = (); # 手順表示用配列
# 状態を表示
sub print_state {
my $s = shift;
my $str ="[";
if( $s & $farmer ){
$str .= " farmer ";
}
if( $s & $goat ){
$str .= " goat ";
}
if( $s & $wolf ){
$str .= " wolf ";
}
if( $s & $cabbage ){
$str .= " cabbage ";
}
$str .= "]";
printf("%-32s", $str );
}
# 表示
sub print_answer {
my $num = shift;
my $r;
my $l;
if( $prev_state[$num] != -1 ){
&print_answer( $prev_state[$num] );
}
if( $state[$num] & $right ){
$r = $state[$num];
$l = $r ^ $all;
} else {
$l = $state[$num];
$r = $l ^ $all;
}
print_state( $l );
print_state( $r );
print "\n";
}
# 状態のチェック
sub check_state {
my $num = shift;
my $now_state = $state[$num];
my $s = $now_state ^ $all; # 農夫がいない方のチェック
my $i;
# 羊と狼、または、羊とキャベツを残してはいけない
if( (($s & $wolf) && ($s & $goat)) ||
(($s & $goat) && ($s & $cabbage)) ){
return 0;
}
# 同じ状態が無いかチェック
for( $i = 0; $i < $num; $i++ ){
return 0 if $state[$i] == $state[$num];
}
return 1;
}
# 幅優先探索
sub search_move {
my $r = 0;
my $w = 1;
$state[0] = $all;
$prev_state[0] = -1;
# キューにデータがある間は繰り返す
for( ; $r < $w; $r++ ){
my $now_state = $state[$r];
foreach $move (@move_list) {
if( $now_state & $move ){
my $new_state = ($now_state ^ $goal) | $move | $farmer;
# キューに登録
$state[$w] = $new_state;
$prev_state[$w] = $r;
if( &check_state( $w ) ){
if( $state[$w] == $goal ){
# 発見
print_answer( $w );
print "状態数 $w\n";
return;
}
$w++;
}
}
}
}
}
# 実行
&search_move();