AND/ORグラフ

問題分割法


与えられた問題が独立した部分問題に分割できる場合(不定積分や因数分 解などの数式処理等)や，二人で行うゲーム(オセロ，チェス，将棋等)に適用 する．

　

• 不定積分の例
  
• 3目並べの例

AND/ORグラフ


状態空間と同様に，AND/ORグラフでも各ノードは状態を表す．各ノードは AND分岐，OR分岐 と呼ばれるエッジで別のノードの集合につながれる．

AND分岐: 問題Pがいくつかの部分問題 {P_i}に分解でき，{P_i}が全て 解けた時にPも解ける場合，Pに対応するノード n_Pから各 P_iに対応するノードn_PiにAND分岐による エッジを張る．n_PはANDノードと呼 ばれる．

OR分岐: 問題Pがいくつかの部分問題 {P_i}に分解でき，{P_i}のうち 一つでも解ける時にPも解ける場合，Pに対応するノード n_Pから各P_iに対応するノード n_PiにOR分岐によるエッジを張る．n_Pは ORノードと呼ばれる．

AND分岐，OR分岐と二人ゲームの関係


二人ゲームをプレイヤの立場で考える．

自分の手番について考える場合，可能な手 の中から自分を勝利または有利に導く手を探すので，OR分岐になる．

相手の手番について考える場合，原理的に は相手のうつ全ての手について考える必要があるのでAND分岐になる．

...Return

• 講義の詳細