はじめに
配列の中から要素をひとつ選ぶ処理を考えます。たとえば、a[n] は配列 a の n 番目の要素を取り出しますが、選ぶ要素を添字 n で指定する必要があります。これに対して、特別な指定をしないで無作為に要素を選ぶことを考えます。このような選択を「非決定的選択」といいます。
ここで、非決定的選択は問題を解くのに都合のいい選択が行われると仮定します。つまり、複数の選択肢の中で解に導くものがいくつか存在するならば、そのうちの一つを選択するのです。たとえば、迷路で分かれ道にきた場合、その中から出口につながる道を一つ選ぶわけです。このような非決定的選択を含む処理 (計算) を「非決定性計算」とか「非決定性」といいます。
このような都合のいい処理を現在のコンピュータで実現することは不可能ですが、バックトラックを使って近似的に実現することは可能です。つまり、ある要素を選んで条件を満たさない場合は、バックトラックして異なる要素を選択すればいいわけです。今回は継続を使って非決定性計算を行う関数 amb() を作ってみましょう。
●amb() の動作
amb() は 0 個以上の引数を受け取り、その中から一つを選んで返します。次の例を見てください。
amb(1, 2, 3) => 1, 2, 3 のどれか 1 つを返す amb => バックトラックして残りの 2 つのうちの 1 つを返す amb => バックトラックして最後の 1 つを返す amb => これ以上バックトラックできないのでエラー
amb() は 1 個以上の引数が与えられた場合、その中の 1 つを選んで返します。引数がない場合、バックトラックして次の要素を選びます。今回は先頭から順番に引数を選んでいくことにしましょう。
amb() は要素を選ぶだけの単純な動作ですが、複数の amb を組み合わせると複雑な動作が可能になります。1, 2, 3 と 4, 5, 6 から要素をひとつずつ取り出して、その組を求める処理は次のようになります。
[amb(1, 2, 3), amb(4, 5, 6)] => [1, 4] amb => [1, 5] amb => [1, 6] amb => [2, 4] amb => [2, 5] amb => [2, 6] amb => [3, 4] amb => [3, 5] amb => [3, 6] amb => エラー
最初の amb() で 1 を選び、次の amb() で 4 が選ばれるので、最初の値は [1, 4] になります。次に amb() を評価すると、2 番目の amb() がバックトラックして、次の要素 5 を選びます。したがって、返り値は [1, 5] になります。そして、その次の返り値は [1, 6] になります。
2 番目の amb() で要素がなくなると、最初の amb() にバックトラックします。すると、次の要素 2 を選び、2 番目の amb() を評価します。ここで 2 番目の amb() は新しく評価されることに注意してください。引数 4, 5, 6 を順番に選んでいくので、返り値は [2, 4] になります。あとはバックトラックするたびに組が生成され、全ての組み合わせを求めることができます。
●amb() の作成
それでは関数 amb() を作りましょう。プログラムは次のようになります。
リスト : 非決定性
require 'continuation'
# エラー定義
class AmbError < StandardError
end
# バックトラックするときの継続を格納
$amb_fail = false
# 初期化
def initialize_amb
$amb_fail = proc { raise AmbError, "AMB tree exhausted" }
end
# 非決定性オペレータ
def amb(*args)
if args == []
$amb_fail.call
else
prev_fail = $amb_fail
callcc {|ret|
args.each do |x|
callcc {|cont|
$amb_fail = proc {
$amb_fail = prev_fail
cont.call
}
ret.call(x)
}
end
$amb_fail.call
}
end
end
$amb_fail はバックトラックするときの継続を格納します。関数 initialize_amb() は $amb_fail を初期化します。これは raise でエラー AmbError "amb tree exhausted" を送出するだけです。関数 amb() は引数のリスト args の要素を先頭から順番に取り出していきます。この処理は前回作成したジェネレータやファイバーとよく似ています。
最初に args が空リストかチェックします。そうであれば、$amb_fail に格納されている継続を実行します。引数がある場合は、先頭から順番に取り出していきます。まず、$amb_fail に格納されている継続を局所変数 prev_fail に保存します。次に、callcc で要素を返すための継続を取り出して引数 ret に渡します。そして、メソッド each() で args の要素を順番にアクセスします。
ブロックの中でバックトラックするときの継続を callcc で取り出して引数 cont に渡します。そして、$amb_fail に cont を呼び出す処理をセットします。この処理の中で、prev_fail に保存しておいた継続を $amb_fail に戻してから、cont を呼び出してバックトラックするようにします。最後に ret.call(x) で要素 x を返します。
これで、amb() でバックトラックすると each() の処理に戻るので、要素をひとつずつ取り出すことができます。each() が終了したら $amb_fail を呼び出すことに注意してください。これで、以前に実行した amb() にバックトラックすることができます。
それでは簡単な実行例を示しましょう。
irb> initialize_amb => #<Proc: ... > irb> amb(1,2,3) => 1 irb> amb => 2 irb> amb => 3 irb> amb ...: AMB tree exhausted (AmbError) irb> [amb(1,2), amb(3,4)] => [1, 3] irb> amb => [1, 4] irb> amb => [2, 3] irb> amb => [2, 4] irb> amb ...: AMB tree exhausted (AmbError)
●順列の生成
もう一つ簡単な例として、順列を生成するプログラムを作ってみましょう。次のリストを見てください。
リスト : 順列の生成
# 条件を満たさない場合はバックトラックする
def assert(pred)
amb unless pred
end
# 順列の生成
def permutations(n, m, a = [])
if m == 0
a
else
x = amb(*(1 .. n))
assert(!a.member?(x))
permutations(n, m - 1, a + [x])
end
end
assert() は pred が偽の場合は amb() を実行してバックトラックします。amb() を使うと順列を生成する関数 permutations() は簡単に実現できます。amb() で 1 から n までの要素を 1 つ選び、それが順列 a に含まれていないことを assert() で確認します。同じ要素が含まれていれば、バックトラックして異なる要素を選びます。n 個の要素を選んだら配列 a を返します。
それでは実行してみましょう。
irb> permutations(4, 4) => [1, 2, 3, 4] irb> amb => [1, 2, 4, 3] irb> amb => [1, 3, 2, 4] irb> amb => [1, 3, 4, 2] irb> amb => [1, 4, 2, 3]
このように、バックトラックするたびに順列を一つずつ生成することができます。
●解をすべて求める
非決定性のプログラムはバックトラックすることで全ての解を求めることができます。このとき、見つけた解を配列に格納して返す関数があると便利です。次のリストを見てください。
リスト : 見つけた解を配列に格納して返す
def bag_of
prev_fail = $amb_fail
result = []
if callcc {|cont|
$amb_fail = proc { cont.call(false) }
result.push(yield)
cont.call(true)
}
$amb_fail.call
end
$amb_fail = prev_fail
result
end
関数 bag_of() は与えられたブロックを実行して、その結果を配列 result に格納して返します。ブロックの中で非決定性計算を行う関数を呼び出します。最初に $amb_fail を局所変数 prev_fail に保存します。次に、callcc で脱出先の継続 cont を取り出して、$amb_fail に proc { cont.call(false) } をセットします。そして、ブロックを yield で実行して、その返り値を result に追加します。
cont.call(true) を実行すると、callcc の返り値が true となり、if の then 節にある $amb_fail.call が実行されます。ブロックの処理にバックトラックして、解が見つかればその値を返します。つまり、解が存在する限り次の処理が繰り返されます。
result.push(yield) -> cont.call(true) -> $amb_fail.call -> result.push(yield) -> ...
これで複数の解を result に格納することができます。ブロックで解が見つからない場合、最初に *amb-fail* にセットした proc { cont.call(false) } が実行されます。その結果、if 条件が偽と判定され、バックトラックを終了します。$amb_fail を元の値に戻してから result を返します。
簡単な実行例を示しましょう。
irb> bag_of do amb(1, 2, 3, 4, 5) end => [1, 2, 3, 4, 5] irb> bag_of do [amb(1, 2, 3), amb(4, 5)] end => [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]] irb> bag_of do permutations(3, 3) end => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
このように bag_of を使って全ての解を求めることができます。
●論理パズル
それでは簡単な例題として論理パズルを解いてみましょう。
３人の友達が、あるプログラミング競技会で１位、２位、３位になった。この３人は、名前も、好きなスポーツも、国籍も異なる。Michael はバスケットが好きで、アメリカ人よりも上位であった。イスラエル人の Simon はテニスをする者よりも上位であった。クリケットをするものが１位であった。誰がオーストラリア人か？ Richard はどのようなスポーツをするか？
- 出典：Leon Sterling, Ehud Shapiro (著), 松田利夫 (訳), 『Prolog の技芸』, 共立出版, 1988, (278頁より)
簡単な論理パズルなので、プログラムを作る前に考えてみてください。
●データ構造の定義
最初にデータ構造とアクセス関数を定義します。データは配列で表します。
[名前, 順位, 国籍, スポーツ]
このデータを amb() で作成します。次のリストを見てください。
リスト : データとアクセス関数の定義
def make_data(name)
[
name,
amb(1, 2, 3),
amb(:US, :IL, :AU),
amb(:basket, :cricket, :tennis)
]
end
# アクセス関数
def rank(data) data[1] end
def nation(data) data[2] end
def sports(data) data[3] end
amb() で順位 (1, 2, 3)、国籍 (:US, :IL, :AU)、スポーツ (:basket, :cricket, :tennis) の中から要素を一つ選びます。バックトラックすると異なる要素が選ばれて、新しいデータが生成されます。
●補助関数の作成
次は問題を解くための補助関数を作ります。
リスト : 補助関数の定義
# 国籍 x を探す
def find_nation(x, *args)
for y in args
return y if x == nation(y)
end
nil
end
# スポーツ x を探す
def find_sports(x, *args)
for y in args
return y if x == sports(y)
end
nil
end
# 重複した要素が有るか
def duplicate?(a, b)
a.zip(b) do |x, y|
return true if x == y
end
false
end
# 同じ要素が有るか
def check?(a, b, c)
duplicate?(a, b) or duplicate?(a, c) or duplicate?(b, c)
end
find_nation() は引数 args の中から国籍が x と等しい要素を返します。find_sports() は好きなスポーツが x と等しい要素を返します。duplicate?() は引数 a と b に重複した要素があれば true を返します。要素が全て異なる場合は false を返します。check?() は duplicate?() を呼び出して、引数 a, b, c に重複した要素があれば true を返します。
●論理パズルの解法
論理パズルの解法プログラムは次のようになります。
リスト : 論理パズルの解法 def puzzle m = make_data(:Michael) s = make_data(:Simon) r = make_data(:Richard) assert(!check?(m, s, r)) assert(sports(m) == :basket) assert(!(nation(m) == :US)) assert(nation(s) == :IL) assert(rank(m) < rank(find_nation(:US, m, s, r))) assert(rank(s) < rank(find_sports(:tennis, m, s, r))) assert(rank(find_sports(:cricket, m, s, r)) == 1) [m, s, r] end
最初に make_data() でデータを作成し、局所変数 m, s, r にセットします。そして、check?() で順位、国籍、スポーツで要素が重複していないかチェックします。あとは問題の条件を assert() でチェックしていくだけです。
- Michael の好きなスポーツはバスケットである。
- Michael の国籍はアメリカではない。
- Simon の国籍はイスラエルである。
- Michael は国籍がアメリカの人よりも上位である。
- Simon はテニスが好きな人よりも上位である。
- クリケットが好きな人が１位である。
条件を満たさない場合はバックトラックして新しいデータを生成します。最後に、見つけた解を出力します。とても簡単ですね。実行結果は次のようになります。
irb> initialize_amb => #<Proc: ... > irb> puzzle => [[:Michael, 2, :AU, :basket], [:Simon, 1, :IL, :cricket], [:Richard, 3, :US, :tennis]] irb> amb ...: AMB tree exhausted (AmbError)
解は 1 通りで、１位が Simon, ２位が Michael, ３位が Richard になります。ちなみに、最後の条件がない場合は 2 通りの解が出力されます。興味のある方は試してみてください。
●amb() は深さ優先探索
今回作成した amb() は、一つ前に実行した amb() の継続を局所変数 prev_fail に保存して、$amb_fail をバックトラックする継続に書き換えています。この処理は $amb_fail に配列をセットして、それをスタックとして使用すると簡単に実現することができます。
つまり、継続を $amb_fail にプッシュしておいて、バットラックするときは $amb_fail から継続をポップして実行します。この方法だと深さ優先探索していることがよくわかると思います。プログラムは次のようになります。
リスト : 非決定性 amb の修正
require 'continuation'
# エラー定義
class AmbError < StandardError
end
# 継続を格納するスタック
$amb_fail = []
# 初期化
def initialize_amb
$amb_fail = []
end
# スタックからデータを取り出してバックトラックする
def fail
if $amb_fail == []
raise AmbError, "AMB tree exhausted"
else
$amb_fail.pop.call
end
end
# 非決定性オペレータ
def amb(*args)
if args == []
fail
else
callcc {|ret|
args.each do |x|
callcc {|cont|
$amb_fail.push(proc {cont.call})
ret.call(x)
}
end
fail
}
end
end
# 条件を満たさない場合はバックトラックする
def assert(pred)
amb unless pred
end
# 見つけた解を配列に格納して返す
def bag_of
result = []
if callcc {|cont|
$amb_fail.push(proc {cont.call(false)})
result.push(yield)
cont.call(true)
}
fail
end
result
end
関数 initialize_amb() は大域変数 $amb_fail を空の配列に初期化します。関数 fail() は $amb_fail から pop() で継続を取り出して実行します。$amb_fail が空リストの場合はエラーを送出します。amb() は proc { cont.call } を $amb_fail に push してから、継続 ret を実行して要素を返します。bag_of() の修正も同じです。
●経路の探索
それでは簡単な例題として、拙作のページ Algorithms of Python 集合、グラフ、経路の探索 で取り上げた「経路の探索」を解いてみましょう。経路図を再掲します。
図 : 経路図
amb を使わずに深さ優先探索でプログラムすると次のようになります。
リスト : 経路の探索
# 隣接リスト
$adjacent = {
:a => [:b, :c],
:b => [:a, :c, :d],
:c => [:a, :b, :e],
:d => [:b, :e, :f],
:e => [:c, :d, :g],
:f => [:d],
:g => [:e]
}
# 深さ優先探索 (depth-first-search)
def dfs(goal, path)
if path[-1] == goal
print path, "\n"
else
$adjacent[path[-1]].each do |x|
dfs(goal, path + [x]) unless path.member?(x)
end
end
end
隣接リスト $adjacent はハッシュで表しています。関数 dfs() は経路を配列 path で管理します。末尾の要素が現在いる地点になります。path[-1] が goal であれば、経路 path を表示します。そうでなければ、$adjacent から隣接リストを取り出し、隣の地点 x を求めます。x が path に含まれていると巡回経路 (閉路) になるので、その地点へは進みません。そうでなければ、path に x を追加して dfs を再帰呼び出しします。
実行結果は次のようになります。
irb> dfs(:g, [:a]) [:a, :b, :c, :e, :g] [:a, :b, :d, :e, :g] [:a, :c, :b, :d, :e, :g] [:a, :c, :e, :g] => [:b, :c]
amb() を使ったプログラムは次のようになります。
リスト : 経路の探索
# 深さ優先探索
def dfs_amb(goal, path)
if path[-1] == goal
path
else
x = amb(*$adjacent[path[-1]])
assert(!path.member?(x))
dfs_amb(goal, path + [x])
end
end
goal に到達していない場合、amb() で隣接リストから要素を一つ選びます。そして、選んだ要素 x が path に含まれていないことを assert() で確認します。最後に、path の先頭に x を追加して探索を続行します。
実行結果は次のようになります。
irb> dfs_amb(:g, [:a]) => [:a, :b, :c, :e, :g] irb(main):003:0> fail => [:a, :b, :d, :e, :g] irb(main):004:0> fail => [:a, :c, :b, :d, :e, :g] irb(main):005:0> fail => [:a, :c, :e, :g] irb> fail ...: AMB tree exhausted (AmbError) irb> bag_of do dfs_amb(:g, [:a]) end => [[:a, :b, :c, :e, :g], [:a, :b, :d, :e, :g], [:a, :c, :b, :d, :e, :g], [:a, :c, :e, :g]]
amb() は深さ優先探索なので、最初に見つかる経路が最短経路とは限りません。最短経路を求めるには「幅優先探索」のほうが適しています。
●幅優先探索版 amb() の作成
それでは、amb() のアルゴリズムを幅優先探索に変更しましょう。基本的には $amb_fail をスタックからキューに変更するだけですが、それだけでは bag_of() の動作が実現できないので、ちょっとした工夫が必要になります。
それでは amb() を修正しましょう。次のリストを見てください。
リスト : 非決定性 amb (幅優先探索)
require 'continuation'
# エラー定義
class AmbError < StandardError
end
# 継続を格納するキュー
$amb_fail = []
# bag_of 用のスタック
$bag_fail = []
# 初期化
def initialize_amb
$amb_fail = []
$bag_fail = []
end
# スタックからデータを取り出してバックトラックする
def fail
if $amb_fail == []
if $bag_fail == []
raise AmbError, "AMB tree exhausted"
else
$bag_fail.pop.call(false)
end
else
$amb_fail.shift.call
end
end
# 非決定性オペレータ
def amb(*args)
if args == []
fail
else
callcc {|cont|
args.each do |x|
$amb_fail.push(proc {cont.call(x)})
end
fail
}
end
end
# 条件を満たさない場合はバックトラックする
def assert(pred)
amb unless pred
end
# 見つけた解を配列に格納して返す
def bag_of
result = []
prev_fail = $amb_fail
if callcc {|cont|
$amb_fail = []
$bag_fail.push(proc {cont.call(false)})
result.push(yield)
cont.call(true)
}
fail
end
$amb_fail = prev_fail
result
end
今回は配列を使ってキューを実装します。$amb_fail を [ ] で初期化します。データの追加は push() で配列の末尾に行い、shift() で配列の先頭からデータを取り出します。これでキューの動作になります。
amb() は簡単です。要素を返すための継続を取り出して cont にセットします。そして、proc { cont.call(x) } を $amb_fail に追加します。最後に関数 fail を呼び出して、キューに格納された継続を取り出してバックトラックします。amb() が最初に呼び出された場合、これで先頭の要素が返されます。
bag_of() はちょっと複雑になります。$amb_fail はキューなので、bag_of の処理を終了するための継続をキューに追加しても動作しません。そこで、新しいキューを生成して $amb_fail にセットし、ブロックの処理で発生したバックトラックはそのキューに格納します。そして、bag_of() の処理を終了するための継続をグローバル変数 $bag_fail にセットします。
yield でブロックを実行したあと、cont.call(true) を実行すると if 文の fail が実行され、ブロックの処理にバックトラックします。これで、ブロックの評価結果を result に格納していくことができます。
関数 fail() は $amb_fail が空でも $bag_fail が空でなければ、$bag_fail から継続を取り出して実行します。$bag_fail はスタックとして使用することに注意してください。要素がなくなると、最初に $bag_fail に格納した proc { call.cont(false) } が取り出されて実行されます。これで bag_of() の callcc { ... } の処理が終了し、$amb_fail を元のキューに戻して result を返します。
それでは、簡単な実行例を示しましょう。
irb> [amb(1,2,3), amb(4,5,6)] => [1, 4] irb> fail => [1, 5] irb> fail => [1, 6] irb> fail => [2, 4] irb> fail => [2, 5] irb> fail => [2, 6] irb> fail => [3, 4] irb> fail => [3, 5] irb> fail => [3, 6] irb> fail ...: AMB tree exhausted (AmbError) irb> bag_of do [amb(1,2,3), amb(4,5,6)] end => [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]]
amb() は幅優先探索なので [amb(1, 2, 3), amb(4, 5, 6)] を評価すると、先頭要素が 1 の組から順番に生成されます。
●経路の探索 (2)
それでは簡単な例題として、経路の探索を「幅優先探索」で行ってみましょう。amb() を使わない場合は次のようになります。
リスト : 経路の探索 (幅優先探索)
def bfs(start, goal)
q = [[start]]
while q.size > 0
path = q.shift
if path[-1] == goal
print path, "\n"
else
$adjacent[path[-1]].each do |x|
q.push(path + [x]) unless path.member?(x)
end
end
end
end
関数 bfs (breadth-first-search) は start から goal までの経路を幅優先で探索します。変数 q にキュー (配列) をセットします。キューから経路を取り出し、経路をのばしてキューに格納します。これで幅優先で経路を探索することができます。
実行結果は次のようになります。
irb> bfs(:a, :g) [:a, :c, :e, :g] [:a, :b, :c, :e, :g] [:a, :b, :d, :e, :g] [:a, :c, :b, :d, :e, :g] => nil
amb() を使ったプログラムは次のようになります。
リスト : 経路の探索 (幅優先探索: amb 版)
def bfs_amb(goal, path)
if path[-1] == goal
path
else
x = amb(*$adjacent[path[-1]])
assert(!path.member?(x))
bfs_amb(goal, path + [x])
end
end
プログラムは dfs_amb() とまったく同じで、名前を bfs_amb に変えただけです。amb が幅優先で動作するので、これで幅優先で経路を探索することができます。
それでは実行してみましょう。
irb> bfs_amb(:g, [:a]) => [:a, :c, :e, :g] irb> fail => [:a, :b, :c, :e, :g] irb> fail => [:a, :b, :d, :e, :g] irb> fail => [:a, :c, :b, :d, :e, :g] irb> fail ...: AMB tree exhausted (AmbError) irb> bag_of do bfs_amb(:g, [:a]) end => [[:a, :c, :e, :g], [:a, :b, :c, :e, :g], [:a, :b, :d, :e, :g], [:a, :c, :b, :d, :e, :g]]
このように、amb() が幅優先探索しているので、最初に見つかる経路が最短経路になります。
●水差し問題
それでは簡単な例題としてパズルを解いてみましょう。「水差し問題」はいろいろな呼び方があって、「水をはかる問題」とか「水を測り出す問題」と呼ばれることもあります。それでは問題です。
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
なお、この問題は拙作のページ Puzzle DE Programming 水差し問題 と同じです。内容は重複しましが、あしからずご了承ください。
水差し問題の場合、次に示す 3 通りの操作があります。
- 容器いっぱいに水を満たす。
- 容器を空にする。
- 他の容器に水を移す。
3 の操作は、容器が空になるまで水を移す場合と、もう一方の容器が満杯になるまで水を移す場合があります。容器は 2 つあるので、全部で 6 通りの操作があります。最初に、これらの操作を行う関数を定義します。プログラムは次のようになります。
リスト : 容器の操作
$max_a = 8
$max_b = 5
def get_a(state) state[0] end
def get_b(state) state[1] end
$action = [
# A を満杯にする
proc {|state| [$max_a, get_b(state)]},
# A を空にする
proc {|state| [0, get_b(state)]},
# A -> B
proc {|state|
a = get_a(state)
b = get_b(state)
w = $max_b - b
if a <= w
[0, a + b]
else
[a - w, b + w]
end
},
# B を満杯にする
proc {|state| [get_a(state), $max_b]},
# B を空にする
proc {|state| [get_a(state), 0]},
# B -> A
proc {|state|
a = get_a(state)
b = get_b(state)
w = $max_a - a
if b <= w
[a + b, 0]
else
[a + w, b - w]
end
}
]
状態は配列 [A, B] で表します。A は 8 リットルの容器の水の量、B は 5 リットルの容器の水の量を表します。容器を水で満たす、または空にする操作は簡単ですね。他の容器へ移す場合、たとえば A->B では、B の空き容量と A の水の量を比較して、少ない方が移す水の量 w になります。
プログラムは次のようになります。
リスト : 水差し問題の解法
# 幅優先探索
def solver(goal)
q = [[[0, 0]]]
while q.size > 0
move = q.shift
if move[-1][0] == goal or move[-1][1] == goal
print move, "\n"
break
else
$action.each {|act|
new_state = act.call(move[-1])
q.push(move + [new_state]) unless move.member?(new_state)
}
end
end
end
# amb
def solver_amb(goal, move)
if move[-1][0] == goal or move[-1][1] == goal
move
else
act = amb(*$action)
new_state = act.call(move[-1])
assert(!move.member?(new_state))
solver_amb(goal, move + [new_state])
end
end
solver() は amb() を使わないで幅優先探索を行います。手順は状態を配列に格納することで表します。最初に初期状態を格納した手順 [[0, 0]] をキュー q に格納します。次に、キューからデータをひとつ取り出して move にセットします。最後尾の状態 move[-1] で、A または B に水が goal リットルあれば解を見つけることができました。move を表示して break でループを脱出します。
そうでなければ、$action から操作関数を取り出します。ブロックの引数 act に操作関数がセットされます。状態 move[-1] に act を適用して新しい状態を生成し、変数 new_state にセットします。move に同じ状態がなければ、new_state を追加した新しい手順をキューに追加します。
solver_amb() の場合、ゴールに到達したら move をそのまま返します。そうでなければ、amb() で操作関数を一つ選んで act にセットします。そして、act.call(move[-1]) で新しい状態を生成して、変数 new_state にセットします。move に同じ状態が見つかった場合はバックトラックします。新しい状態であれば move に追加して solver_move() を再帰呼び出しします。
solver() を実行すると次のようになります。
irb> solver(4) [[0, 0], [0, 5], [5, 0], [5, 5], [8, 2], [0, 2], [2, 0], [2, 5], [7, 0], [7, 5], [8, 4]] => nil
このように、最短手順は 10 手になります。solver_amb() で実行すると、最短手順以外の解も求めることができます。
irb> solver_amb(4, [[0,0]]) => [[0, 0], [0, 5], [5, 0], [5, 5], [8, 2], [0, 2], [2, 0], [2, 5], [7, 0], [7, 5], [8, 4]] irb> fail => [[0, 0], [8, 0], [3, 5], [0, 5], [5, 0], [5, 5], [8, 2], [0, 2], [2, 0], [2, 5], [7, 0], [7, 5], [8, 4]]
最短手数の手順は 1 通りしかなく、次に短い手順は 12 手になりました。
改訂 2023 年 1 月 21 日