イラストで学ぶ人工知能概論を再度勉強する　第３章　最適経路の探索

はじめに

とある理由で
「二重文節構造」のアイデアに触れた時から大ファンになった
谷口忠大先生の名著「イラストで学ぶ人工知能概論」を
じっくり勉強しなおしたくなって
改訂第2版を購入しなおした。

本noteは、その備忘録

ホイールダック2号、最短経路でゴールに向かう（宝箱を探す必要はない）

第３章　最適経路の探索

講義スライドと谷口忠大先生本人の講義動画が
谷口忠大先生から提供されています

講義スライド

3.1　最適経路の探索とヒューリスティックな知識

3.1.1　経路のコスト
ノードからノードへの移動にかかるコストを考え、経路のコストを最小化する問題に定式化する

3.1.2　ヒューリスティックな知識としての予測評価値
各ノードからゴールまでの予測評価値を発見的（ヒューリスティック）に与える）各ノードの移動にかかるコストから計算したものではなく、単なる予測値（適当に与える。後半で分かるが、まったく適当というわけでもない）

3.2　最適探索

3.2.1　最適探索のアルゴリズム
オープンリストとクローズドリストを用いて、できるだけコストが小さな状態を優先して探索する

3.3　最良優先探索

オープンリストとクローズドリストを用いて、できるだけ予測評価値が小さな状態を優先して探索する

3.4　A*アルゴリズム

オープンリストとクローズドリストを用いて、コストと予測評価値の双方がバランスよく小さくなる状態を優先して探索する

ホイールダック2号の最短経路探索

完全自立型のホイールダック2号が、
最適経路でダンジョンの迷路を抜けて出口に到達する

本章の最重要ポイント

オープンリストとクローズドリストを用いて
最適経路を探索する方法を3つ学んだ
１．コスト優先
２．評価値優先
３．コストと評価値のバランスをとる

おわりに

いよいよ本格的な話になってきた。

実際にアルゴリズムを追体験しないと
アルゴリズムのすごさがわからない。

時間がかかってもアルゴリズムの通りに探索して
アルゴリズムの特徴を理解しよう