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

きっちりやるなら　↓

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

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

---

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


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌─ドア４──　　　　　　　　　　　　　　　┌─ドア２──
　　　　　　　　　　├─ドア５──　　　　　　　　　　　　　　　├─ドア３──
　　　　┌─ドア１─┤　　　　　　　　　　　　　　　┌─ドア１─┤
　○　　│　　　　　└─ドア６──　　　　　　○　　│　　　　　└─ドア４──
　大　─┤　　　　　┌─ドア７──　宝　　　　大　─┤　　　　　┌─ドア６──　宝
　　　　│　　　　　├─ドア８──　　　　　　　　　│　　　　　├─ドア７──
　　　　├─ドア２─┤　　　　　　　　　　　　　　　├─ドア５─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└─ドア３─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


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

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


　　　　　　　　　　　　　はじまる☆！

　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　ＢＯＭ　　　　　　　　　　　　　　　　　　　ＢＯＭ
　　　　　　｜｜｜　┌─ドア４──　　　　　　　　　　　｜｜｜　┌─ドア２──
　　　　　○＼Ｖ／　├─ドア５──　　　　　　　　　　○＼Ｖ／　├─ドア３──
　　　　┌大＞　＜─┤　　　　　　　　　　　　　　　┌大＞　＜─┤
　　　　│　　　　　└─ドア６──　　　　　　　　　│　　　　　└─ドア４──
　…　─┤　　　　　┌─ドア７──　宝　　　　…　─┤　　　　　┌─ドア６──　宝
　　　　│　　　　　├─ドア８──　　　　　　　　　│　　　　　├─ドア７──
　　　　├─ドア２─┤　　　　　　　　　　　　　　　├─ドア５─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└─ドア３─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ＢＯＭ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　｜｜｜
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　○＼Ｖ／
　　　　　　　　　　┌─ドア４──　　　　　　　　　　　　　　　┌大＞　＜──
　　　　　　　　　　├─ドア５──　　　　　　　　　　　　　　　├─ドア３──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤
　　　　│　ＢＯＭ　└─ドア６──　　　　　　　　　│　　　　　└─ドア４──
　…　─┤　｜｜｜　┌─ドア７──　宝　　　　…　─┤　　　　　┌─ドア６──　宝
　　　　│○＼Ｖ／　├─ドア８──　　　　　　　　　│　　　　　├─ドア７──
　　　　├大＞　＜─┤　　　　　　　　　　　　　　　├─ドア５─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└─ドア３─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ＢＯＭ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　｜｜｜
　　　　　　　　　　┌─ドア４──　　　　　　　　　　　　　　　┌○＼Ｖ／──
　　　　　　　　　　├─ドア５──　　　　　　　　　　　　　　　├大＞　＜──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤
　　　　│　　　　　└─ドア６──　　　　　　　　　│　　　　　└─ドア４──
　…　─┤　　　　　┌─ドア７──　宝　　　　…　─┤　　　　　┌─ドア６──　宝
　　　　│　　　　　├─ドア８──　　　　　　　　　│　　　　　├─ドア７──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├─ドア５─┤
　　　　│　ＢＯＭ　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　｜｜｜　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│○＼Ｖ／　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└大＞　＜─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　　　ＢＯＭ　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　｜｜｜　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　○＼Ｖ／　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　┌大＞　＜──　　　　　　　　　　　　　　　┌　ＢＯＭ──
　　　　　　　　　　├─ドア５──　　　　　　　　　　　　　　　├　｜｜｜──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤○＼Ｖ／
　　　　│　　　　　└─ドア６──　　　　　　　　　│　　　　　└大＞　＜──
　…　─┤　　　　　┌─ドア７──　宝　　　　…　─┤　　　　　┌─ドア６──　宝
　　　　│　　　　　├─ドア８──　　　　　　　　　│　　　　　├─ドア７──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├─ドア５─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─
　「全部ドアだった……」


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　　　ＢＯＭ　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　｜｜｜　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　┌○＼Ｖ／──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├大＞　＜──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤　　　　
　　　　│　　　　　└─ドア６──　　　　　　　　　│　ＢＯＭ　└…　　　──
　…　─┤　　　　　┌─ドア７──　宝　　　　…　─┤　｜｜｜　┌─ドア６──　宝
　　　　│　　　　　├─ドア８──　　　　　　　　　│○＼Ｖ／　├─ドア７──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├大＞　＜─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─
　　　　　　　　　　　　　　　　　　　　　　「空部屋だった……」


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…ＢＯＭ──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…｜｜｜──　　　　　　　　　　　　　　　├…ＢＯＭ──
　　　　┌…　　　─┤○＼Ｖ／　　　　　　　　　　　┌…　　　─┤　｜｜｜
　　　　│　　　　　└大＞　＜──　　　　　　　　　│　　　　　└○＼Ｖ／──
　…　─┤　　　　　┌─ドア７──　宝　　　　…　─┤　　　　　┌大＞　＜──　宝
　　　　│　　　　　├─ドア８──　　　　　　　　　│　　　　　├─ドア７──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├…　　　─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─
　　　　　　　　　　　　　　　　　　　　　　「キタコレー！」


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…　　　──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…ＢＯＭ──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　｜｜｜　　　　　　　　　　　┌…　　　─┤　ＢＯＭ
　　　　│　　　　　└○＼Ｖ／──　　　　　　　　　│　　　　　└…｜｜｜──
　…　─┤　　　　　┌大＞　＜──　宝　　　　…　─┤　　　　　┌○＼Ｖ／──　…
　　　　│　　　　　├─ドア８──　　　　　　　　　│　　　　　├大＞　＜──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├…　　　─┤
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└─ドア８──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─
　「キタコレー！」


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…　　　──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…　　　──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　ＢＯＭ　　　　　　　　　　　┌…　　　─┤　　　　
　　　　│　　　　　└…｜｜｜──　　　　　　　　　│　　　　　└…　　　──
　…　─┤　　　　　┌○＼Ｖ／──　…　　　　…　─┤　　　　　┌…ＢＯＭ──　…
　　　　│　　　　　├大＞　＜──　　　　　　　　　│　　　　　├　｜｜｜──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├…　　　─┤○＼Ｖ／
　　　　│　　　　　└─ドア９──　　　　　　　　　│　　　　　└大＞　＜──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　　　　　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└─ドア９─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…　　　──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…　　　──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤　　　　
　　　　│　　　　　└…　　　──　　　　　　　　　│　　　　　└…　　　──
　…　─┤　　　　　┌…ＢＯＭ──　…　　　　…　─┤　　　　　┌…　　　──　…
　　　　│　　　　　├…｜｜｜──　　　　　　　　　│　　　　　├…　　　──
　　　　├…　　　─┤○＼Ｖ／　　　　　　　　　　　├…　　　─┤　　　　
　　　　│　　　　　└大＞　＜──　　　　　　　　　│　ＢＯＭ　└…　　　──
　　　　│　　　　　┌─ドア１０─　　　　　　　　　│　｜｜｜　┌─ドア１０─
　　　　│　　　　　├─ドア１１─　　　　　　　　　│○＼Ｖ／　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└大＞　＜─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…　　　──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…　　　──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤　　　　
　　　　│　　　　　└…　　　──　　　　　　　　　│　　　　　└…　　　──
　…　─┤　　　　　┌…　　　──　…　　　　…　─┤　　　　　┌…　　　──　…
　　　　│　　　　　├…ＢＯＭ──　　　　　　　　　│　　　　　├…ＢＯＭ──
　　　　├…　　　─┤　｜｜｜　　　　　　　　　　　├…　　　─┤　｜｜｜
　　　　│　　　　　└○＼Ｖ／──　　　　　　　　　│　　　　　└○＼Ｖ／──
　　　　│　　　　　┌大＞　＜──　　　　　　　　　│　　　　　┌大＞　＜──
　　　　│　　　　　├─ドア１１─　　　　　　　　　│　　　　　├─ドア１１─
　　　　└…　　　─┤　　　　　　　　　　　　　　　└…　　　─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…　　　──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…　　　──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤　　　　
　　　　│　　　　　└…　　　──　　　　　　　　　│　　　　　└…　　　──
　…　─┤　　　　　┌…　　　──　…　　　　…　─┤　　　　　┌…　　　──　…
　　　　│　　　　　├…　　　──　　　　　　　　　│　　　　　├…　　　──
　　　　├…　　　─┤　ＢＯＭ　　　　　　　　　　　├…　　　─┤　ＢＯＭ
　　　　│　　　　　└…｜｜｜──　　　　　　　　　│　　　　　└…｜｜｜──
　　　　│　　　　　┌○＼Ｖ／──　　　　　　　　　│　　　　　┌○＼Ｖ／──
　　　　│　　　　　├大＞　＜──　　　　　　　　　│　　　　　├大＞　＜──
　　　　└…　　　─┤　　　　　　　　　　　　　　　└…　　　─┤
　　　　　　　　　　└─ドア１２─　　　　　　　　　　　　　　　└─ドア１２─


　　　　　　　幅優先探索　　　　　　　　　　　　　　　　　深さ優先探索　　　
━━━━━━━━━━━━━━━━━━━　　　━━━━━━━━━━━━━━━━━━━
　　　　　　　　　　┌…　　　──　　　　　　　　　　　　　　　┌…　　　──
　　　　　　　　　　├…　　　──　　　　　　　　　　　　　　　├…　　　──
　　　　┌…　　　─┤　　　　　　　　　　　　　　　┌…　　　─┤　　　　
　　　　│　　　　　└…　　　──　　　　　　　　　│　　　　　└…　　　──
　…　─┤　　　　　┌…　　　──　…　　　　…　─┤　　　　　┌…　　　──　…
　　　　│　　　　　├…　　　──　　　　　　　　　│　　　　　├…　　　──
　　　　├…　　　─┤　　　　　　　　　　　　　　　├…　　　─┤　　　　
　　　　│　　　　　└…　　　──　　　　　　　　　│　　　　　└…　　　──
　　　　│　　　　　┌…ＢＯＭ──　　　　　　　　　│　　　　　┌…ＢＯＭ──
　　　　│　　　　　├…｜｜｜──　　　　　　　　　│　　　　　├…｜｜｜──
　　　　└…　　　─┤○＼Ｖ／　　　　　　　　　　　└…　　　─┤○＼Ｖ／
　　　　　　　　　　└大＞　＜──　　　　　　　　　　　　　　　└大＞　＜──


「ふぅ」



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

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


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

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





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

---

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


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

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

　歌詞Ａメロ（※１）　　　　　　　　　　　　歌詞Ａメロ（※１）

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

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

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

　サビ　　　　　　　　　　　　　　　　　　　サビ

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

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



：│┃