And%E2%80%93or_tree
AN AND-ORツリーがあるグラフィック表現の減少の問題に（または目標）接続詞および選言部分問題（またはサブゴール）の。
コンテンツ 1 例 2 定義
3 検索戦略
4 論理プログラミングとの関係
5 2人用ゲームとの関係
6 参考文献
例
and-orツリー：
目標削減法を使用して、問題Pを解くための探索空間を表します。
QとRの場合はP
Sの場合はP
Q if T
Q if U
定義
最初の問題Pを考えると0とフォームのメソッドを問題解決のセット：
P Pであれば
1と…とP nは 関連するand-orツリーは、次のようなラベル付きノードのセットです。
ツリーのルートは、Pで標識したノードである0。
問題またはサブ問題Pにより、フォームPのすべての方法であればP標識すべてのノードnについて1と…及びP nは、子供のノードNのセットが存在1、…、N N N、そのようなノードのを各ノードNすることを私はPによって標識されているI。ノードは、他のメソッドに関連付けられている可能性のあるNの子と区別するために、円弧で結合されています。
問題Pでラベル付けされたノードNは、Pの形式のメソッドがない場合（つまり、Pが「ファクト」である場合）、成功ノードです。Pを解く方法がない場合、ノードは故障ノードです。
同じアークで結合されたノードNのすべての子が成功ノードである場合、ノードNも成功ノードです。それ以外の場合、ノードは障害ノードです。
検索戦略
and-orツリーは、問題を解決するための検索スペースのみを指定します。スペースを検索するためのさまざまな検索戦略が可能です。これらには、ソリューションの望ましさの測定値を使用して、ツリーの深さ優先、幅優先、または最良優先の検索が含まれます。検索戦略は、シーケンシャル、一度に1つのノードの検索または生成、または並列、複数のノードの検索または生成を並行して行うことができます。
論理プログラミングとの関係
および-またはツリーの生成に使用されるメソッドは、命題論理プログラム（変数なし）です。変数を含む論理プログラムの場合、結合サブ問題の解は互換性がなければなりません。この複雑さを条件として、および-またはツリーの順次および並列検索戦略は、論理プログラムを実行するための計算モデルを提供します。
2人用ゲームとの関係
また、ツリーを使用して、2人用ゲームの検索スペースを表すこともできます。このようなツリーのルートノードは、ゲームの初期状態から開始して、プレーヤーの1人がゲームに勝つという問題を表しています。特定のプレイ状態からゲームに勝つプレーヤーの問題Pでラベル付けされたノードNが与えられると、動きに応答するすべての対戦相手に対応する、結合された子ノードの単一のセットが存在します。これらの子ノードのそれぞれについて、プレーヤーのすべての防御動作に対応する、非結合の子ノードのセットが存在します。
でゲーム木を解決するための証明番号検索アルゴリズムの家族、ゲームの木がすると-や樹木マップされます。MAXノード（つまり、プレーヤーの移動を最大化する）はORノードとして表され、MINノードはANDノードにマップされます。検索がバイナリゴールのみで行われる場合、マッピングが可能です。これは通常、「移動するプレーヤーがゲームに勝つ」です。
参考文献
ルガー、ジョージF。; Stubblefield、William A.（1993）。人工知能：複雑な問題解決のための構造と戦略（2版）。ベンジャミン/カミングス。ISBN 978-0-8053-4785-2。
Nilsson、Nils J.（1998）。人工知能：新しい統合。モーガンカウフマン。ISBN 978-1-55860-467-4。“