部分問題に分割する場合
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 02:02 UTC 版)
分割統治法のように、部分問題に分割したうえで全体問題を解いた方が効率的な問題もある。A* 同様の通常の状態遷移はどれかがゴールに到達すれば良いので OR と呼び、部分問題に分割する場合は全ての部分問題が解けないといけないので AND と呼ぶと、探索木が AND/OR 木になる。AND で状態を分割する際、ゴールも分割する必要がある。 同じ状態が2度出現した場合に1つのノードにまとめると AND/OR グラフになる。閉路のない AND/OR グラフに対する A* アルゴリズムに対応する物が1968年に開発され、1980年に AO*アルゴリズム と命名された。閉路のある AND/OR グラフに対する A* アルゴリズムに対応する A0アルゴリズム は1976年に開発された。AND ノードのコストを「辺のコスト＋部分問題のコストの最大値」や「辺のコスト＋部分問題のコストの総和」などの単調非減少関数で定義すると、ヒューリスティック関数が許容的であれば、A* 同様、最適解が求まる。なお、閉路のない AND/OR グラフは文脈自由文法（タイプ-2 文法）、閉路のある AND/OR グラフは制限のない文法（タイプ-0 文法）に1対1対応することが証明されている。
※この「部分問題に分割する場合」の解説は、「A*」の解説の一部です。
「部分問題に分割する場合」を含む「A*」の記事については、「A*」の概要を参照ください。
ウィキペディア小見出し辞書の「部分問題に分割する場合」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 部分問題に分割する場合のページへのリンク
