【アルゴリズム】【Ruby】深さ優先検索、幅優先検索

思いついてチャレンジした問題が難しすぎて解けない、せかいです。
こんばんは。

実はこのブログを書いてから、師匠からすぐに回答メールを貰っていまして。

[コード]
･･･
これを作るまで酔った状態で1時間。
最後で sort して  uniq してるのが実にだめ。
単純に全部列挙するのはよいアイデアではないが、
まずはここから考えるといいかもね

うえーん（泣）
こんな酔っ払いの変人に負けるなんて･･･

このいけてないコード、世界中に公開しますから！

だめ

だったので、コードはお見せできませんが、

(0 0 0 0) から初めて
(1 0 0 0) を作ってチェック、(2 0 0 0)　を作ってチェック
みたいなのを網羅してる。

アルゴリズム的には深さ優先探索で解をさがしにいってるね
深さ優先探索っていうのを知らんと難しいかもしれん
逆にいえば、深さ優先探索しってれば、実装できるよ

とのこと。

　
あまりにコードが難しすぎたので、一旦は他の問題を解いていたのですが

せっかくちゃんと問題解いて解説までつけたのに、
せかいさんの反応が微妙で寂しいかぎりです

やばい！
師匠が泣いてる！
これは今日中に何とかしないと！

問題再掲

数が二つ与えられて、片方の数字を、
もう片方の数字以下の数字の組み合わせで表現する

（例）
１０　と　１　⇒[1,1,.....,1]
４　と　３　⇒[3,1][2,2][2,1,1][1,1,1,1]
４　と　２　⇒[2,2][2,1,1][1,1,1,1]

考え方の指針

合計がmになる組み合わせをとりあえず全部列挙する。
出した組み合わせの中から、nより大きい数字を使っている組み合わせをはじく。

※列挙は、深さ優先・幅優先の二通り考えてみる

こういう「全部列挙」ってコンピューターならではの考え方。
目からウロコでした。

　
■全部列挙：深さ優先

def separate m
   state = Array.new(m,0)
   _separate(state, [], 0, m)
end

def _separate(state, result, sum, m)
   return result if sum == m
   ok = (sum+1 == m)
   (0..sum).each do |i|
      tmp = state.dup
      tmp[i] += 1
      result << tmp if ok
      _separate(tmp, result, sum+1, m)
   end
   result
end

p separate(4)

　
■実行結果

[[4, 0, 0, 0], [3, 1, 0, 0], [3, 0, 1, 0], [3, 0, 0, 1], [3, 1, 0, 0], [2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1], [3, 0, 1, 0], [2, 1, 1, 0], [2, 0, 2, 0], [2, 0, 1, 1], [3, 1, 0, 0], [2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1], [2, 2, 0, 0], [1, 3, 0, 0], [1, 2, 1, 0], [1, 2, 0, 1], [2, 1, 1, 0], [1, 2, 1, 0], [1, 1, 2, 0], [1, 1, 1, 1]]

nより大きい数字の組み合わせをはじく

コード全量

def separate m
   state = Array.new(m,0)
   _separate(state, [], 0, m)
end

def _separate(state, result, sum, m)
   return result if sum == m
   ok = (sum+1 == m)
   (0..sum).each do |i|
      tmp = state.dup
      tmp[i] += 1
      result << tmp if ok
      _separate(tmp, result, sum+1, m)
   end
   result
end

def sieve(candidates, n)
   result = []
   candidates.each do |candidate|
      acceptable = true
      candidate.each do |i|
        acceptable = false if i > n
      end
      result << candidate if acceptable
   end
   result
end

def generate(m,n)
   candidates = separate(m)
   sieve(candidates, n)
end

p generate(4,2)

　
■実行結果

[[2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1], [2, 1, 1, 0], [2, 0, 2, 0], [2, 0, 1, 1], [2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1], [2, 2, 0, 0], [1, 2, 1, 0], [1, 2, 0, 1], [2, 1, 1, 0], [1, 2, 1, 0], [1, 1, 2, 0], [1, 1, 1, 1]]

幅優先

def separate(m)
  same_levels = [Array.new(m,0)]
  _separate(same_levels, m, 0)
end

def _separate(same_levels, m, i)
  return same_levels if i>= m
  ok = (i+1 == m)
  next_levels = []
  same_levels.each do |current|
    (0..m-1).each do |k|
      tmp = current.dup
      tmp[k] += 1
      next_levels << tmp
    end
  end
  if ok
    return next_levels
  end
  _separate(next_levels, m, i+1)
end
p separate(3)

■実行結果

[[3, 0, 0], [2, 1, 0], [2, 0, 1], [2, 1, 0], [1, 2, 0], [1, 1, 1], [2, 0, 1], [1, 1, 1], [1, 0, 2], [2, 1, 0], [1, 2, 0], [1, 1, 1], [1, 2, 0], [0, 3, 0], [0, 2, 1], [1, 1, 1], [0, 2, 1], [0, 1, 2], [2, 0, 1], [1, 1, 1], [1, 0, 2], [1, 1, 1], [0, 2, 1], [0, 1, 2], [1, 0, 2], [0, 1, 2], [0, 0, 3]]

「nより大きい数の存在する組み合わせは弾く」のsieveメソッドは同じなので省略。

　
なんとか出来た。

探索は強力なツールなので
これが使えるようになると、色々な問題に応用できるよ。

数独とか、オセロとか
川渡り問題とか
全部結局は探索問題なんで。

うーむ。
川渡り問題は私も知ってる。
考えてみよう。