著者

片山 裕一 笹尾 茂樹 菅田 一博 井須 尚紀 清水 忠昭

雑誌

全国大会講演論文集

巻号頁・発行日

vol.49, pp.59-60, 1994-09-20

---

本研究の目的は,グラフ探索法としてA^*アルゴリズムを用い,ヒューリスティックな知識を利用したグラフ探索を行い,その結果からヒューリスティックな知識の質を向上させることである.グラフ探索とは,与えられた問題をグラフで表現し,問題を解くためにグラフを探索することである.グラフは節点と節点対を結ぶ枝から成り,枝にはコストが与えられている.出発節点から目標節点までの経路のうち,コストの総和が最小な経路(最適解)を見つけることが,グラフ探索の目的である.Aアルゴリズムは,任意の節点nから目標節点までのコストが推定でき,その推定値を取り入れることによって効率よく解を求める方法である.さらに,A^*アルゴリズムでは,目標までのコストの真値h(n)と推定値h^^(n)の間にh^^(n)≤h(n)の関係が成立しており,必ず最適解を見つけることができる.また,推定値h^^(n)が真値h(n)に近いほど,ヒューリスティックな知識の質が高いといい,グラフ探索の効率が高い.