edX ColumbiaXのAI (CSMM.101x) Week3のまとめです。
今回取り上げられているヒューリスティック検索や前回の講義で取り上げられている、幅優先探索等を日本語で理解するためには、下記サイトを参照致しました。
ヒューリスティック探索
幅優先探索と反復深化
欲張り法 (greedy strategy)
3.1 Heuristic and Greedy Search Algorithm
前回説明されたUninformed Searchに対し、解に近づいているかどうかがわかるInformed Searchが今回の講義のテーマです。
最良優先探索(Greedy best-first search)、Aスター探索、反復深化Aスター探索がInformed Searchの例としてあげられています。
3.2 A* Search and Optimality
Aスター探索となぜ、それが最適な解を提示し得るかの説明がされています。
3.3 Search Algorithms Recap
ここでは、今まで説明された、BFS, DFS, IDS, UCS, A*, IDA*, Greedy best first search, A* Searchの各種アルゴリズムの特徴が説明されています。
ここまでの講義の最重要点ですので、別途まとめてポスト予定です。
3.4 Local Search (局所探索法)
局所探索法としてHill Climbing 山登り法の説明がされています。
Week 3 Quiz: Heuristic Search
ヒューリスティック関数の性質に関する質問で1問間違えたものの、他はすべて正解ができました。ヒューリスティック関数が許容的(admissible)かどうか、特定条件下で各アルゴリズムのcompletnessはどうか、といった設問が多かったです。
Week 3 Discussion Questions
ダイクストラ法と均一コスト法の比較を行っている下記論文が紹介されています。こちらも別途ポスト予定の探索アルゴリズムまとめで言及する予定です。
Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm
http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357
今回取り上げられているヒューリスティック検索や前回の講義で取り上げられている、幅優先探索等を日本語で理解するためには、下記サイトを参照致しました。
ヒューリスティック探索
幅優先探索と反復深化
欲張り法 (greedy strategy)
3.1 Heuristic and Greedy Search Algorithm
前回説明されたUninformed Searchに対し、解に近づいているかどうかがわかるInformed Searchが今回の講義のテーマです。
最良優先探索(Greedy best-first search)、Aスター探索、反復深化Aスター探索がInformed Searchの例としてあげられています。
3.2 A* Search and Optimality
Aスター探索となぜ、それが最適な解を提示し得るかの説明がされています。
3.3 Search Algorithms Recap
ここでは、今まで説明された、BFS, DFS, IDS, UCS, A*, IDA*, Greedy best first search, A* Searchの各種アルゴリズムの特徴が説明されています。
ここまでの講義の最重要点ですので、別途まとめてポスト予定です。
3.4 Local Search (局所探索法)
局所探索法としてHill Climbing 山登り法の説明がされています。
Week 3 Quiz: Heuristic Search
ヒューリスティック関数の性質に関する質問で1問間違えたものの、他はすべて正解ができました。ヒューリスティック関数が許容的(admissible)かどうか、特定条件下で各アルゴリズムのcompletnessはどうか、といった設問が多かったです。
Week 3 Discussion Questions
ダイクストラ法と均一コスト法の比較を行っている下記論文が紹介されています。こちらも別途ポスト予定の探索アルゴリズムまとめで言及する予定です。
Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm
http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357
