Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

記事投稿キャンペーン 「2024年!初アウトプットをしよう」
@jerrywdlee

続: Rubyでかの有名な水の移し替えパズルを解く(ちゃんと探索アルゴリズムを使う)

Last updated at Posted at 2024-01-06

はじめに

去年の12月は下記 「Rubyでかの有名な水の移し替えパズルを解く」 を投稿しました。

@nodai2h_ITC さんよりコメントを頂いて、「幅優先探索」 を活用した方が、ランダムウォークよりも合理であると指摘されました。

まったくご指摘通りでした🙇‍♀️。

しかし私の不勉強である故、なかなか綺麗な探索木のコードを書けなくて(決してゲームに没頭したせいではありません)、記事の更新を放置してました。
昨日、@mogamoga1337さんよりJavaScriptで探索木を使った解き方が投稿されたので、サボっては行けないと思い、連休中殴り書いたRuby版探索木コードを整理して投稿します。

[2024-01-09更新] 続編の続編も更新しました！

方法

容器の抽象化

まず、前回同様に抽象化を行います。今回は「幅優先探索」と「深さ優先探索」両方を行いたいため、容器クラスJugをjug.rbとして外出して、requireします。

jug.rb
class Jug
  attr_accessor :max, :vol # 最大容量＆残量を定義

  def initialize(max_capacity, vol = 0)
    @max = max_capacity # 最大容量
    @vol = vol # 現在の残量
  end

  def capacity # 空き容量
    @max - @vol
  end

  def fill # 満タンにする
    @vol = @max
  end

  def empty # 空にする
    @vol = 0
  end

  def pour(jug) # 別の容器に注ぐ
    pour_vol = [@vol, jug.capacity].min
    jug.vol += pour_vol
    @vol -= pour_vol

    pour_vol
  end
end

幅優先探索

とにかく可能なステップを網羅して探索します。中止条件としては、「２つの容器に入っている水の量の組み合わせが、前に一度ありました」としています。その際、該当ステップを進行しても目的の量に辿り着けないと判断します。

jug_bfs.rb
require "./jug" # 容器クラス

# 幅優先探索
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def bfs(s_max, l_max, t_vol)
  jug_s = Jug.new(s_max); jug_l = Jug.new(l_max) # 2つの容器の初期化

  queue = [] # 探索中のノードを保持するキュー
  queue << { steps: [], vols: [[jug_s.vol, jug_l.vol]] } # ルートノードの投入

  loop do # 不適切なノードをどんどん捨てるので、無限ループにはならない
    return nil if queue.empty? # 結果が見つからない(処理するノードがもうない)時

    curr_node = queue.shift # 処理したいノードを取り出す
    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.vol = s_vol; jug_l.vol = l_vol # ２つの容器をセットアップ
      pour_vol = nil # もし該当操作は「注ぐ」の場合、注いだ量の初期化

      case o_label
      when 'SE'
        jug_s.empty
      when 'LE'
        jug_l.empty
      when 'SF'
        jug_s.fill
      when 'LF'
        jug_l.fill
      when 'S2L'
        pour_vol = jug_s.pour jug_l
      when 'L2S'
        pour_vol = jug_l.pour jug_s
      end

      # 2つの容器に入った水の量の組み合わせは既に存在した場合、
      # 無限ループに入ったと判断し、このノードを切り捨てる
      next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]

      # 処理結果を新しいノードとして追加
      queue << {
        steps: curr_node[:steps] + [o_label + pour_vol.to_s],
        vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
      }
    end
  end
end

ツリー構造

下記６種類の操作しかできないので、

  • 3L容器を空に
  • 5L容器を空に
  • 3L容器を満タンに
  • 5L容器を満タンに
  • 3L容器から5L容器へ注ぐ
  • 5L容器から3L容器へ注ぐ

1つのノードに6つのノードが派生し、次に6つのノードが派生するとみなします。
ただし、一部の操作は変化を起こさない、また一部の操作は以前出現した結果に戻ることがあるので、X印をつけて、このノードは終了と示します。
探索方向としては、各階層(ステップ)の使用可能なノードしらみつぶすように走査しています。

ルートノード[[0, 0]]
├── Step1: 3L容器を空に[[0, 0], [0, 0]] X
├── Step1: 5L容器を空に[[0, 0], [0, 0]] X
├── Step1: 3L容器を満タンに[[0, 0], [3, 0]]
│   ├── Step2: 3L容器を空に[[0, 0], [3, 0], [0, 0]] X
│   ├── Step2: 5L容器を空に[[0, 0], [3, 0], [3, 0]] X
│   ├── Step2: 3L容器を満タンに[[0, 0], [3, 0], [3, 0]] X
│   ├── Step2: 5L容器を満タンに[[0, 0], [3, 0], [3, 5]]
│   │   ├── Step3: 3L容器を空に[[0, 0], [3, 0], [3, 5], [0, 5]]
│   │   │   └── 次のステップへ続く...
│   │   ├── Step3: 5L容器を空に[[0, 0], [3, 0], [3, 5], [3, 0]] X
│   │   ├── Step3: 3L容器を満タンに[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   │   ├── Step3: 5L容器を満タンに[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   │   ├── Step3: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   │   └── Step3: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   ├── Step2: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [0, 3]]
│   │   ├── Step3: 3L容器を空に[[0, 0], [3, 0], [0, 3], [0, 3]] X
│   │   ├── Step3: 5L容器を空に[[0, 0], [3, 0], [0, 3], [0, 0]] X
│   │   ├── Step3: 3L容器を満タンに[[0, 0], [3, 0], [0, 3], [3, 3]]
│   │   │   └── 次のステップへ続く...
│   │   ├── Step3: 5L容器を満タンに[[0, 0], [3, 0], [0, 3], [0, 5]]
│   │   │   └── 次のステップへ続く...
│   │   ├── Step3: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [0, 3], [0, 0]] X
│   │   └── Step3: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [0, 3], [0, 0]] X
│   └── Step2: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [3, 0]] X
├── Step1: 5L容器を満タンに[[0, 0], [0, 5]]
│   ├── Step2: 3L容器を空に[[0, 0], [0, 5], [0, 5]] X
│   ├── Step2: 5L容器を空に[[0, 0], [0, 5], [0, 0]] X
│   ├── Step2: 3L容器を満タンに[[0, 0], [0, 5], [3, 5]]
│   │   └── 次のステップへ続く...
│   ├── Step2: 5L容器を満タンに[[0, 0], [0, 5], [0, 5]] X
│   ├── Step2: 3L容器から5L容器へ注ぐ[[0, 0], [0, 5], [0, 5]] X
│   └── Step2: 5L容器から3L容器へ注ぐ[[0, 0], [0, 5], [3, 2]]
│       └── 次のステップへ続く...
├── Step1: 3L容器から5L容器へ注ぐ[[0, 0], [0, 0]] X
└── Step1: 5L容器から3L容器へ注ぐ[[0, 0], [0, 0]] X

実行結果

カウンター入れて実行してみます。

s_max, l_max, t_vol = [3, 5, 4]
cnt = 0
bfs(s_max, l_max, t_vol) do
 cnt += 1
end

=> {
  :steps=>["LF", "L2S3", "SE", "L2S2", "LF", "L2S1"],
  :vols=>[[0, 0], [0, 5], [3, 2], [0, 2], [2, 0], [2, 5], [3, 4]]
}

cnt
=> 47

６ステップの最適解に辿り着いて、かつループ回数は47回でした。ランダムウォークの約500回よりは断然早いでした。そして冗長なIF文を排除してコードの見通しもだいぶ良くなりました。

実行結果の整形

前回は実行中も日本語を無理やりブッチ込んだせいか、コードの可読性が悪くなったので、今回は結果の整形を外出します。
そして print_result.rb として保存すれば、後述「深さ優先探査」を行う際そのまま使え回せます。

print_result.rb
# 探索の結果ノードを出力
# @param [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @return [nil] 返り値はない
def print_result(res, s_max, l_max)
  unless res
    puts "結果見つかりませんでした"
    return
  end

  res[:steps].each_with_index do |label, i|
    vol = res[:vols][i + 1] # 該当ステップの処理結果を取得

    step_str = case label
    when 'SE'
      "#{s_max}L容器を空っぽにした"
    when 'LE'
      "#{l_max}L容器を空っぽにした"
    when 'SF'
      "#{s_max}L容器を満タンにした"
    when 'LF'
      "#{l_max}L容器を満タンにした"
    when /S2L(\d+)/
      "#{s_max}L容器から#{l_max}L容器へ#{$1}Lを注いだ"
    when /L2S(\d+)/
      "#{l_max}L容器から#{s_max}L容器へ#{$1}Lを注いだ"
    end

    puts step_str = "Step#{i + 1}: #{step_str} (#{s_max}L容器: #{vol[0]}L, #{l_max}L容器: #{vol[1]}L)"
  end;nil
end

実行してみると

s_max, l_max, t_vol = [3, 5, 4]; cnt = 0
res = bfs(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: 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 = 47

もちろん他の組み合わせたも実行して見ます。

s_max, l_max, t_vol = [5, 9, 7]
cnt = 0
res = bfs(s_max, l_max, t_vol) { cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"

Step1: 9L容器を満タンにした (5L容器: 0L, 9L容器: 9L)
Step2: 9L容器から5L容器へ5Lを注いだ (5L容器: 5L, 9L容器: 4L)
Step3: 5L容器を空っぽにした (5L容器: 0L, 9L容器: 4L)
Step4: 9L容器から5L容器へ4Lを注いだ (5L容器: 4L, 9L容器: 0L)
Step5: 9L容器を満タンにした (5L容器: 4L, 9L容器: 9L)
Step6: 9L容器から5L容器へ1Lを注いだ (5L容器: 5L, 9L容器: 8L)
Step7: 5L容器を空っぽにした (5L容器: 0L, 9L容器: 8L)
Step8: 9L容器から5L容器へ5Lを注いだ (5L容器: 5L, 9L容器: 3L)
Step9: 5L容器を空っぽにした (5L容器: 0L, 9L容器: 3L)
Step10: 9L容器から5L容器へ3Lを注いだ (5L容器: 3L, 9L容器: 0L)
Step11: 9L容器を満タンにした (5L容器: 3L, 9L容器: 9L)
Step12: 9L容器から5L容器へ2Lを注いだ (5L容器: 5L, 9L容器: 7L)

cnt = 183

答えの出ない組み合わせも試して見ます。

s_max, l_max, t_vol = [3, 6, 4]
cnt = 0
res = bfs(s_max, l_max, t_vol) { cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"

結果見つかりませんでした
cnt = 31

深さ優先探索

深さ優先探索といえば、再帰を使うのは定番です。あえてループに直さず、再帰で書いています。
[2024-01-09更新] ループVerはこちらです。

require "./jug" # 容器クラス
require "./print_result" # 結果印字用メソッド

# 深さ優先探索
# @param [Int] s_max 容器(小)の最大容量
# @param [Int] l_max 容器(大)の最大容量
# @param [Int] t_vol 取りたい水の量
# @param [Hash] 途中の結果: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を返す
def dfs(s_max, l_max, t_vol, curr_node = nil, &block)
  curr_node = { steps: [], vols: [[0, 0]] } unless curr_node # ルートノードのセットアップ

  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'
      jug_s.empty
    when 'LE'
      jug_l.empty
    when 'SF'
      jug_s.fill
    when 'LF'
      jug_l.fill
    when 'S2L'
      pour_vol = jug_s.pour jug_l
    when 'L2S'
      pour_vol = jug_l.pour jug_s
    end

    # 2つの容器に入った水の量の組み合わせは既に存在した場合、
    # 無限ループに入ったと判断し、このノードを切り捨てる
    next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]

    # 処理結果を新しいノードとして追加
    new_node = {
      steps: curr_node[:steps] + [o_label + pour_vol.to_s],
      vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
    }

    res_new = dfs(s_max, l_max, t_vol, new_node, &block) # 再帰的に呼び出す
    return res_new if res_new # 結果を下のスタックに渡す
  end

  nil # 見つからない時はnilを返す
end

ツリー構造

「幅優先探索」の時と同じように1つのノードに6つのノードが派生しています。これ以上使用できないノードにX印をつけています。
しかし探索方向は「幅優先探索」と違くて、使える一つのノードを可能な限り探索を行ってから他のノードへの探索へ切り替えます。

ルートノード[[0, 0]]
├── Step1: 3L容器を空に[[0, 0], [0, 0]] X
├── Step1: 5L容器を空に[[0, 0], [0, 0]] X
├── Step1: 3L容器を満タンに[[0, 0], [3, 0]]
│   ├── Step2: 3L容器を空に[[0, 0], [3, 0], [0, 0]] X
│   ├── Step2: 5L容器を空に[[0, 0], [3, 0], [3, 0]] X
│   ├── Step2: 3L容器を満タンに[[0, 0], [3, 0], [3, 0]] X
│   ├── Step2: 5L容器を満タンに[[0, 0], [3, 0], [3, 5]]
│   │   ├── Step3: 3L容器を空に[[0, 0], [3, 0], [3, 5], [0, 5]]
│   │   │   ├── Step4: 3L容器を空に[[0, 0], [3, 0], [3, 5], [0, 5], [0, 5]] X
│   │   │   ├── Step4: 5L容器を空に[[0, 0], [3, 0], [3, 5], [0, 5], [0, 0]] X
│   │   │   ├── Step4: 3L容器を満タンに[[0, 0], [3, 0], [3, 5], [0, 5], [3, 5]] X
│   │   │   ├── Step4: 5L容器を満タンに[[0, 0], [3, 0], [3, 5], [0, 5], [0, 5]] X
│   │   │   ├── Step4: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [0, 5], [0, 5]] X
│   │   │   └── Step4: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2]]
│   │   │       ├── Step5: 3L容器を空に[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2], [0, 2]]
│   │   │       │   └── 次のステップへ続く...
│   │   │       ├── Step5: 5L容器を空に[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2], [3, 0]] X
│   │   │       ├── Step5: 3L容器を満タンに[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2], [3, 2]] X
│   │   │       ├── Step5: 5L容器を満タンに[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2], [3, 5]] X
│   │   │       ├── Step5: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2], [0, 5]] X
│   │   │       └── Step5: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [0, 5], [3, 2], [3, 2]] X
│   │   ├── Step3: 5L容器を空に[[0, 0], [3, 0], [3, 5], [3, 0]] X
│   │   ├── Step3: 3L容器を満タンに[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   │   ├── Step3: 5L容器を満タンに[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   │   ├── Step3: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   │   └── Step3: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [3, 5], [3, 5]] X
│   ├── Step2: 3L容器から5L容器へ注ぐ[[0, 0], [3, 0], [0, 3]]
│   │   └── 次のステップへ続く...
│   └── Step2: 5L容器から3L容器へ注ぐ[[0, 0], [3, 0], [3, 0]] X
├── Step1: 5L容器を満タンに[[0, 0], [0, 5]]
│   └── 次のステップへ続く...
├── Step1: 3L容器から5L容器へ注ぐ[[0, 0], [0, 0]] X
└── Step1: 5L容器から3L容器へ注ぐ[[0, 0], [0, 0]] X

実行結果

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: 3L容器を満タンにした (3L容器: 3L, 5L容器: 0L)
Step2: 5L容器を満タンにした (3L容器: 3L, 5L容器: 5L)
Step3: 3L容器を空っぽにした (3L容器: 0L, 5L容器: 5L)
Step4: 5L容器から3L容器へ3Lを注いだ (3L容器: 3L, 5L容器: 2L)
Step5: 3L容器を空っぽにした (3L容器: 0L, 5L容器: 2L)
Step6: 5L容器から3L容器へ2Lを注いだ (3L容器: 2L, 5L容器: 0L)
Step7: 5L容器を満タンにした (3L容器: 2L, 5L容器: 5L)
Step8: 5L容器から3L容器へ1Lを注いだ (3L容器: 3L, 5L容器: 4L)

cnt = 8

おや？最適解ではない答えが出ましたね。
資料を調べたら、「最短経路」を求めたい場合は「幅優先探索」が適していると書いていますね。
逆に、「可能な答え」を何でもいいから一つ求めたい場合は、「深さ優先探索」の方が早いです。
上記実行結果もその通り、最適解ではないものの、たった8回の再帰で一つの答えを見つけました。


ちなみに下記のように、答えの出ない組み合わせで実行すると、幅優先探索と同じように探索木の全てのノードをスキャンしていました。回数も幅優先探索と同じ31回でした。

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

反復深化深さ優先探索

どうしても深さ優先探索で「最短経路」を求めたい場合は、「反復深化深さ優先探索」が利用可能です。
名前通り、探索の深さを制限して、該当深さで答えが出ない場合、深さ制限の上限を徐々にアップして探索を繰り返します。
ゲーム制作で有名なかの A*アルゴリズム も「反復深化深さ優先探索」の発展型です。

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(s_max, l_max, t_vol, &block)
  root = { steps: [], vols: [[0, 0]] } # ルートノードを初期化
  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] curr_node 途中の結果: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [Hash] 結果のノード: `{ steps: 操作ステップ, vols: 途中の容量変化 }`
# @return [nil] 結果見つからない際は `nil` を
def dls(s_max, l_max, t_vol, depth, curr_node, &block)
  s_vol, l_vol = curr_node[:vols].last # それぞれの容器の現在の容量を取得
  return curr_node if s_vol == t_vol || l_vol == t_vol # 結果見つかった時は結果ノードを返す

  return if depth == 0

  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'
      jug_s.empty
    when 'LE'
      jug_l.empty
    when 'SF'
      jug_s.fill
    when 'LF'
      jug_l.fill
    when 'S2L'
      pour_vol = jug_s.pour jug_l
    when 'L2S'
      pour_vol = jug_l.pour jug_s
    end

    # 2つの容器に入った水の量の組み合わせは既に存在した場合、
    # 無限ループに入ったと判断し、このノードを切り捨てる
    next if curr_node[:vols].include? [jug_s.vol, jug_l.vol]

    # 処理結果を新しいノードとして追加
    next_node = {
      steps: curr_node[:steps] + [o_label + pour_vol.to_s],
      vols: curr_node[:vols] + [[jug_s.vol, jug_l.vol]],
    }
    
    if depth > 0 # 深さの残りがまだある時、再帰的に呼び出す
      res_new = dls(s_max, l_max, t_vol, depth - 1, next_node, &block)
      return res_new if res_new
    end
  end

  nil # 見つからない時はnilを返す
end

[2024-01-09更新] 反復深化深さ優先探索の方もループVerがあります。

実行結果

s_max, l_max, t_vol = [3, 5, 4]; cnt = 0
res = iddfs(s_max, l_max, t_vol) { |r| 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: 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 = 78

6ステップの最適解に辿り着けましたが、78回もの再帰を使いました(幅優先探索は47回)。
最適化されていない時の反復深化深さ優先探索だと、既に探索済のノードを、深さ制限が増大した際にまた探索し直されますので、探索木のサイズが大きい場合は気をつけた方が良いです。
また、特殊な判断ロジックを入れない限り、「全てのノードを辿りましたが、見つかりませんでした」とわからないので、無限ループに陥りやすいです。

先ほどと同じように、答えの出ない組合せ[3, 6, 4]で実行すると、設定した最大深度(9999回)まで実行され、再帰回数はなんと30万回でした。

s_max, l_max, t_vol = [3, 6, 4]; cnt = 0
res = iddfs(s_max, l_max, t_vol) { |r| cnt += 1 }
print_result(res, s_max, l_max)
puts "cnt = #{cnt}"

結果見つかりませんでした
cnt = 309832

前述した反復深化深さ優先探索の問題は「訪れたノードを記憶する仕組み」を組み込めば対策はできますが、その分メモリを消耗するので、深さ優先探索の利点の一つ「空間計算量の少なさ」が消えてしまいます(むしろこの時は幅優先探索を使うべきです)。

感想

文系出身(自分の大学は生物学でしたが、似たようなものです)のエンジニアとして、探索木のようなアルゴリズムを咄嗟の反応で思い出すのはやはり難しいでした。将来応用情報の受験も視野に入れているので、情報系の教科書を一回見通す必要性をますます感じます。

参考

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?