はじめに
まさか「Rubyでかの有名な水の移し替えパズルを解く」シリーズの続々編まで書けると思いませんでした。
先日続編の方で、深さ優先探索は再帰で書きましたが、再帰の深さによってパフォーマンスが心配で、連休を乗じてイテレーション(繰り返し処理、ループ)での書き方も投稿いたします。
前回までのあらすじ
方法
(単純の)深さ優先探索
require "./jug" # 容器クラス
require "./print_result" # 結果印字用メソッド
# 深さ優先探索(イテレーション)
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def dfs(s_max, l_max, t_vol, &block)
stack = [{ steps: [], vols: [[0, 0]] }] # スタックにルートノードをセットアップ
loop do
return nil if stack.empty? # 結果が見つからない(処理するノードがもうない)時
curr_node = stack.pop # 処理したいノードを取り出す
s_vol, l_vol = curr_node[:vols].last # それぞれの容器の現在の容量を取得
return curr_node if s_vol == t_vol || l_vol == t_vol # 結果見つかった時は結果ノードを返す
yield curr_node if block_given? # カウンターや途中の処理状況を確認するためのHook
# 6種類の操作をラベリングし、それぞれ処理を行う
# 無効な操作が発生した場合は結果次第排除する
%w[SE LE SF LF S2L L2S].each do |o_label|
jug_s = Jug.new(s_max, s_vol); jug_l = Jug.new(l_max, l_vol) # 2つの容器の初期化
pour_vol = nil # もし該当操作は「注ぐ」の場合、注いだ量の初期化
case o_label
when 'SE' then jug_s.empty
when 'LE' then jug_l.empty
when 'SF' then jug_s.fill
when 'LF' then jug_l.fill
when 'S2L' then pour_vol = jug_s.pour jug_l
when 'L2S' then pour_vol = jug_l.pour jug_s
end
# 2つの容器に入った水の量の組み合わせは既に存在した場合、
# 無限ループに入ったと判断し、このノードを切り捨てる
next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]
# 処理結果を新しいノードとして追加
stack << {
steps: curr_node[:steps] + [o_label + pour_vol.to_s],
vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
}
end
end
nil # 見つからない時はnilを返す
end
深さ優先探索で再帰を使わない場合は、手書きでスタックを管理する必要があります。
「幅優先探索」に似たような書き方となりますが、幅優先探索方はQueue(FIFO)で探索中のノードを保持し、深さ優先探索はStack(LIFO)でノードを保持します。
ちなみに、print_resultの中身は こちら です。
結果確認
s_max, l_max, t_vol = [3, 5, 4]; cnt = 0
res = dfs(s_max, l_max, t_vol) { cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"
実行してみると、当たり前ですが、最適解ではないものが返されました。
面白いことで、再帰の方で書いたメソッドと違う結果になりました。
見た感じ、再帰で書いた方とイテレーションで書いた方、逆サイドから処理を行うようです。
Step1: 5L容器を満タンにした (3L容器: 0L, 5L容器: 5L)
Step2: 5L容器から3L容器へ3Lを注いだ (3L容器: 3L, 5L容器: 2L)
Step3: 5L容器を満タンにした (3L容器: 3L, 5L容器: 5L)
Step4: 5L容器を空っぽにした (3L容器: 3L, 5L容器: 0L)
Step5: 3L容器から5L容器へ3Lを注いだ (3L容器: 0L, 5L容器: 3L)
Step6: 3L容器を満タンにした (3L容器: 3L, 5L容器: 3L)
Step7: 3L容器から5L容器へ2Lを注いだ (3L容器: 1L, 5L容器: 5L)
Step8: 5L容器を空っぽにした (3L容器: 1L, 5L容器: 0L)
Step9: 3L容器から5L容器へ1Lを注いだ (3L容器: 0L, 5L容器: 1L)
Step10: 3L容器を満タンにした (3L容器: 3L, 5L容器: 1L)
Step11: 3L容器から5L容器へ3Lを注いだ (3L容器: 0L, 5L容器: 4L)
cnt = 11
ちなみに答えの出ない組み合わせ(3, 6, 4)で探索すると、同じ結果になります。
s_max, l_max, t_vol = [3, 6, 4]; cnt = 0
res = dfs(s_max, l_max, t_vol) { cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"
結果見つかりませんでした
cnt = 31
反復深化深さ優先探索
require "./jug" # 容器クラス
require "./print_result" # 結果印字用メソッド
# 反復深化深さ優先探索
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def iddfs_v2(s_max, l_max, t_vol, &block)
root = { steps: [], vols: [[0, 0]] } # ルートノードを初期化
stack = []
9999.times do |depth| # 無限ループ対策
res = dls(s_max, l_max, t_vol, depth, root, &block)
return res if res
end
nil # 結果見つからない時はnilを返す
end
# 深さ制限探索(イテレーション)
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @param [Int] depth 制限深さ
# @param [Hash] root ルートノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [Hash] 結果ノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def dls(s_max, l_max, t_vol, depth, root , &block)
stack = [root] # スタックにルートノードをセットアップ
loop do
return nil if stack.empty? # 結果が見つからない(処理するノードがもうない)時
curr_node = stack.pop # 処理したいノードを取り出す
s_vol, l_vol = curr_node[:vols].last # それぞれの容器の現在の容量を取得
return curr_node if s_vol == t_vol || l_vol == t_vol # 結果見つかった時は結果ノードを返す
curr_depth = curr_node[:vols].size - 1 # 処理対象のノードの深さを今までの処理結果より算出
next if curr_depth >= depth # 深度達した際は処理しない
yield curr_node if block_given? # カウンターや途中の処理状況を確認するためのHook
# 6種類の操作をラベリングし、それぞれ処理を行う
# 無効な操作が発生した場合は結果次第排除する
%w[SE LE SF LF S2L L2S].each do |o_label|
jug_s = Jug.new(s_max, s_vol); jug_l = Jug.new(l_max, l_vol) # 2つの容器の初期化
pour_vol = nil # もし該当操作は「注ぐ」の場合、注いだ量の初期化
case o_label
when 'SE' then jug_s.empty
when 'LE' then jug_l.empty
when 'SF' then jug_s.fill
when 'LF' then jug_l.fill
when 'S2L' then pour_vol = jug_s.pour jug_l
when 'L2S' then pour_vol = jug_l.pour jug_s
end
# 2つの容器に入った水の量の組み合わせは既に存在した場合、
# 無限ループに入ったと判断し、このノードを切り捨てる
next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]
# 処理結果を新しいノードとして追加
stack << {
steps: curr_node[:steps] + [o_label + pour_vol.to_s],
vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
}
end
end
nil # 見つからない時はnilを返す
end
結果確認
s_max, l_max, t_vol = [3, 5, 4]; cnt = 0
res = iddfs_v2(s_max, l_max, t_vol) { |r| cnt += 1; }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"
実行してみると、ちゃんと最適解を見つかりました。こちらも面白いことに、処理回数は再帰の方よりやや少なくなりましたが、幅優先探索の47回よりは多いです。
Step1: 5L容器を満タンにした (3L容器: 0L, 5L容器: 5L)
Step2: 5L容器から3L容器へ3Lを注いだ (3L容器: 3L, 5L容器: 2L)
Step3: 3L容器を空っぽにした (3L容器: 0L, 5L容器: 2L)
Step4: 5L容器から3L容器へ2Lを注いだ (3L容器: 2L, 5L容器: 0L)
Step5: 5L容器を満タンにした (3L容器: 2L, 5L容器: 5L)
Step6: 5L容器から3L容器へ1Lを注いだ (3L容器: 3L, 5L容器: 4L)
cnt = 62