読者です 読者をやめる 読者になる 読者になる

全探索の勉強

Algorithms

今日は深さ優先探索幅優先探索で1日が終了したみたいです。

chokudaiさんのとこのアルゴリズム勉強会でDFSとBFSの講義があったのでまずはスライドで
http://www.slideshare.net/chokudai/wap-atcoder2

んで、kyuridenamidaさんがまとめてくれていた、典型問題の演習。
http://d.hatena.ne.jp/kyuridenamida/20111009/1318087144#c

探索アルゴリズムには
uninformed searchとinfromed searchに大別されるらしいですね。
盲目的探索 blind searchとヒューリスティック探索 heuristic searchとも分けられます。
競技プログラミングで出てくるのは前者の方が断然多いです。
ヒューリスティック探索とか見たことないです。見ても使えるなんて思いません。
blind searchの方は

リスト探索:線形探索、二分探索、内挿探索
木探索:幅優先探索深さ優先探索、深さ制限探索、均一コスト探索、反復深化探索、双方向探索
グラフ探索:ダイクストラクラスカル、ワーシャルフロイド

とかに分けられてて、リストはあのアルゴリズムの一番最初に勉強するやつです。
グラフ探索は木探索の拡張だとかなんとか。

まあGWもあと2日ありますし、少しは上達できるかなと思ってます。