トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

蟻本 - 全探索

[蟻本]

蟻本 - 全探索

  再帰

  • フィボナッチ数列を再帰で求める

+ フィボナッチ数列

  スタック・キュー

スタック

  • stackはArrayで表現できる
    • pushArray#pushArray#<<
    • topArray#last
    • popArray#pop
s = []

s << 1   # [] -> [1]
s << 2   # [1] -> [1,2]
s << 3   # [1,2]-> [1,2,3]
p s.last # top
s.pop
p s      # [1,2]
s.pop
p s      # [1]

キュー

  • queueもArrayで表現できる
    • pushArray#pushArray#<<
    • firstArray#first
    • popArray#shift
q = []

q << 1   # [] -> [1]
q << 2   # [1] -> [1,2]
q << 3   # [1,2]-> [1,2,3]

q.shift  # [1,2,3] -> [2,3]
q.shift  # [2,3] -> [3]
q.shift  # [3] -> []

  深さ優先探索

  • 何をもって深さ優先探索と呼ぶのだろうか?
    • Wikipediaより…
 形式的には、深さ優先探索は、探索対象となる木の最初のノードから、
 目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。

+ 深さ優先探索

例題(The Number of Island - AOJ 0067)

+ Rubyのサンプルコード

例題(How Many Islands? - AOJ 1160)

+ Rubyのサンプルコード

  幅優先探索

  特殊な状態の列挙

  枝刈り

お名前: コメント: