きふわらべのブロマガ

「深さ優先探索」と「幅優先探索」

2015/05/21 19:16 投稿

コメント:2

  • タグ:
  • コンピュータ将棋
  • 探索
  • 深さ優先探索
  • 幅優先探索
きっちりやるなら ↓

    実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)

を読むのがいいんだが、
説明のレベルが低いブログにも、読者のレベルに合わせた 存在意義はあると思うんだぜ☆



探索は、調べものを調べる順番のことだぜ☆
ドアを開ける順番を振ってみたんだぜ☆


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━
          ┌─ドア4──               ┌─ドア2──
          ├─ドア5──               ├─ドア3──
    ┌─ドア1─┤               ┌─ドア1─┤
 ○  │     └─ドア6──      ○  │     └─ドア4──
 大 ─┤     ┌─ドア7── 宝    大 ─┤     ┌─ドア6── 宝
    │     ├─ドア8──         │     ├─ドア7──
    ├─ドア2─┤               ├─ドア5─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └─ドア3─┤               └─ドア9─┤
          ─ドア12─               ─ドア12─


    まず手前のドアを全部            まず1部屋を
    開けてから、                奥まで突入して、
    次のドアを開けていく            その部屋を全部調べてから
    んだぜ☆                  隣の部屋も全部調べて
                          いくんだぜ☆

 ↑ こっちの人は、             ↑ こっちの人は
   何を言っているか分からないと        ドアを開けて部屋に入ったら、
   思うが、                  入ってきたドアから一度出て、
   来た道を帰らずに              隣のドアまで走っていく☆
   開けたいドアの前に
   瞬間移動できる☆


             はじまる☆!

       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
      BOM                   BOM
      ||| ┌─ドア4──           ||| ┌─ドア2──
     ○\V/ ├─ドア5──          V/ ├─ドア3──
    ┌大> <─┤               ┌> <─┤
    │     └─ドア6──         │     └─ドア4──
 … ─┤     ┌─ドア7── 宝    … ─┤     ┌─ドア6── 宝
    │     ├─ドア8──         │     ├─ドア7──
    ├─ドア2─┤               ├─ドア5─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └─ドア3─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
                                  BOM
                                  |||
                                 \V/
          ┌─ドア4──               ┌> <──
          ├─ドア5──               ├─ドア3──
    ┌…   ─┤               ┌   ─┤
    │ BOM └─ドア6──         │     └─ドア4──
 … ─┤ ||| ┌─ドア7── 宝    … ─┤     ┌─ドア6── 宝
    │\V/ ├─ドア8──         │     ├─ドア7──
    ├> <─┤               ├─ドア5─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └─ドア3─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
                                     
                                  BOM
                                  |||
          ┌─ドア4──               ┌\V/──
          ├─ドア5──               ├> <──
    ┌…   ─┤               ┌…   ─┤
    │     └─ドア6──         │     └─ドア4──
 … ─┤     ┌─ドア7── 宝    … ─┤     ┌─ドア6── 宝
    │     ├─ドア8──         │     ├─ドア7──
    ├   ─┤               ├─ドア5─┤
    │ BOM └─ドア9──         │     └─ドア8──
    │ ||| ┌─ドア10─         │     ┌─ドア10─
    │\V/ ├─ドア11─         │     ├─ドア11─
    └> <─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
            BOM                      
            |||                      
           ○\V/                      
          ┌大> <──               ┌ BOM──
          ├─ドア5──               ├ |||──
    ┌…   ─┤               ┌…   ─┤○\V/
    │     └─ドア6──         │     └大> <──
 … ─┤     ┌─ドア7── 宝    … ─┤     ┌─ドア6── 宝
    │     ├─ドア8──         │     ├─ドア7──
    ├…   ─┤               ├─ドア5─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └…   ─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─
 「全部ドアだった……」


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
            BOM                      
            |||                      
          ┌○\V/──               ┌…   ──
          ├大> <──               ├…   ──
    ┌…   ─┤               ┌…   ─┤    
    │     └─ドア6──         │ BOM └…   ──
 … ─┤     ┌─ドア7── 宝    … ─┤ ||| ┌─ドア6── 宝
    │     ├─ドア8──         │○\V/ ├─ドア7──
    ├…   ─┤               ├大> <─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └…   ─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─
                      「空部屋だった……」


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌BOM──               ┌…   ──
          ├|||──               ├…BOM──
    ┌…   ─┤○\V/           ┌…   ─┤ |||
    │     └大> <──         │     └○\V/──
 … ─┤     ┌─ドア7── 宝    … ─┤     ┌大> <── 宝
    │     ├─ドア8──         │     ├─ドア7──
    ├…   ─┤               ├   ─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └…   ─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─
                      「キタコレー!」


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌   ──               ┌…   ──
          ├BOM──               ├…   ──
    ┌…   ─┤ |||           ┌…   ─┤ BOM
    │     └○\V/──         │     └|||──
 … ─┤     ┌大> <── 宝    … ─┤     ┌○\V/── …
    │     ├─ドア8──         │     ├大> <──
    ├…   ─┤               ├…   ─┤
    │     └─ドア9──         │     └─ドア8──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └…   ─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─
 「キタコレー!」


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌…   ──               ┌…   ──
          ├…   ──               ├…   ──
    ┌…   ─┤ BOM           ┌…   ─┤    
    │     └|||──         │     └…   ──
 … ─┤     ┌○\V/──     … ─┤     ┌BOM── 
    │     ├大> <──         │     ├ |||──
    ├…   ─┤               ├…   ─┤○\V/
    │     └─ドア9──         │     └大> <──
    │     ┌─ドア10─         │     ┌─ドア10─
    │     ├─ドア11─         │     ├─ドア11─
    └…   ─┤               └─ドア9─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌…   ──               ┌…   ──
          ├…   ──               ├…   ──
    ┌…   ─┤               ┌…   ─┤    
    │     └…   ──         │     └…   ──
 … ─┤     ┌BOM── …    … ─┤     ┌…   ── …
    │     ├…|||──         │     ├…   ──
    ├…   ─┤○\V/           ├…   ─┤    
    │     └大> <──         │ BOM └…   ──
    │     ┌─ドア10─         │ ||| ┌─ドア10─
    │     ├─ドア11─         │○\V/ ├─ドア11─
    └…   ─┤               └大> <─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌…   ──               ┌…   ──
          ├…   ──               ├…   ──
    ┌…   ─┤               ┌…   ─┤    
    │     └…   ──         │     └…   ──
 … ─┤     ┌…   ── …    … ─┤     ┌…   ── …
    │     ├…BOM──         │     ├…BOM──
    ├…   ─┤ |||           ├…   ─┤ |||
    │     └○\V/──         │     └○\V/──
    │     ┌大> <─         │     ┌大> <
    │     ├─ドア11─         │     ├─ドア11─
    └…   ─┤               └…   ─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌…   ──               ┌…   ──
          ├…   ──               ├…   ──
    ┌…   ─┤               ┌…   ─┤    
    │     └…   ──         │     └…   ──
 … ─┤     ┌…   ── …    … ─┤     ┌…   ── …
    │     ├…   ──         │     ├…   ──
    ├…   ─┤ BOM           ├…   ─┤ BOM
    │     └|||──         │     └|||──
    │     ┌○\V/──         │     ┌○\V/
    │     ├大> <──         │     ├大> <
    └…   ─┤               └…   ─┤
          ─ドア12─               └─ドア12─


       幅優先探索                 深さ優先探索   
━━━━━━━━━━━━━━━━━━   ━━━━━━━━━━━━━━━━━━━
          ┌…   ──               ┌…   ──
          ├…   ──               ├…   ──
    ┌…   ─┤               ┌…   ─┤    
    │     └…   ──         │     └…   ──
 … ─┤     ┌…   ── …    … ─┤     ┌…   ── …
    │     ├…   ──         │     ├…   ──
    ├…   ─┤               ├…   ─┤    
    │     └…   ──         │     └…   ──
    │     ┌BOM──         │     ┌BOM──
    │     ├…|||──         │     ├…|||──
    └…   ─┤○\V/           └…   ─┤○\V/
          大> <──               └大> <


「ふぅ」



コンピューター将棋は 幅優先探索をやっているだろう☆
ピタッと奥へ進むのをやめるので、目の前に王手のドアがあるのが分かるじゃないか、
と人間が言っても さっさっと引き返すんだぜ☆
水平線効果 が起こるのはこっちだな☆ww 人間の勝手な言い分な気がするぜ☆ww
上位のコンピューターは、対策してると思うんだぜ☆

「水平線から出た先は、思ったより悪い景色ではなかった☆ 運が良かった」
とか台詞が聞けることもあるな☆www


人間は、入らなくていい部屋が分かってるのか、深さ優先探索をしているんじゃ
ないだろうか☆?
最初に間違った部屋に入っているかも知れないんだが、そんなこと分からないんだぜ☆
勘と、選択肢をバサッと捨てて 奥へ進む力が優れているのかもしれないな☆ww

ファンタ が起こるのはこっちだな☆www
1手詰めを逃すとか、上位のコンピューターはしないからな☆ww





きふわらべが 深さ優先探索 をやっていたので、 幅優先探索に直すんだぜ(ボソ



プログラムのしかた☆
==========


       幅優先探索                深さ優先探索   
━━━━━━━━━━━━━━━━━━  ━━━━━━━━━━━━━━━━━━━

            作詞・むずでょ              作詞・むずでょ

 歌詞Aメロ(※1)            歌詞Aメロ(※1)

   ♪見えているドアを全て開けたァ      ♪最初のドアに入ったァ

    その先に見えているドアを         入った部屋の最初のドアを
    全部 覚えていたァ            開けて入ったァ

                         ドアがないときは出てたァ

 サビ                   サビ

    1度開けたドアのことは          ドアがないときは出てたァ
    2度と入らないと覚えていたァ

 ※1…深さ (2回) 繰り返す       ※1…深さ (行けるとこまで) 繰り返す



:│┃

コメント

piyopiyo
No.1 (2015/11/23 00:07)
第三回将棋電王トーナメントのソフト紹介ページから来ました。

将棋ソフトプラグラミングは、とても興味があるのにわからないというもどかしさを感じていました。
きふわらべ」の紹介文を読んで、とてもその点すっきりしました。
レベルの低い人のための場があってよい」。すっきりするしなかったことの気づきとその解です。
ちなみに、解説は最後の例え(貴族100人)あたりからわかりませんでした。
また2回目読みしてみます。
その点、紹介文はとてもありがたく読ませていただきました。また、その観点から賞賛を送りたいです。


低レベルグループのためのもの(ブログ、メディア、コミュニティ)が欲しいですね。もっと。
理解はある程度できると思うので。速度を落とせば。

トップの人に追いつくことは叶わないだろうし、ソフトを強くすることにも理解が及ばず限界がくるでしょうが(トップの人より比較的早くに)。けど、少しは理解したいですしね。

なんだか、できるひとできないひと」のテーマになってしまいました。

今後も低レベル向けにお願いしたいですね。

低レベル向けの本も、十分需要あると思いますね。
低レベルのほうが多いわけですから。できるひとよりも。


むずでょ@電王トーナメント42位 (著者)
No.2 (2017/05/17 08:24)
>>1
コメントが付いているとは 気づかなかったぜ、 何をやっているんだぜ ニコニコ動画☆(^~^)!

貴族のあたりは 時間がなくて 急いで書いたんで 説明が ずっけんどん なんだぜ☆(^~^)
ボナンザメソッドが どう点が付いているかは 保木さんに聞いてくれだぜ☆(^▽^)wwwwwwww
教えるヒマもないだろうけど☆(^▽^)wwwwwwwwwwwww
コメントを書き込むにはログインしてください。

いまブロマガで人気の記事