図のレイアウト

代表的なそれぞれのレベルにおいて，直接的な非周期の図は，FMPアプリケーションのシーケンスの全ての可能性を表し構成されている． 図は，特徴を計算しない新しく生成された仮定と一致する，単一の知識状態から始まる． コントロールプログラムは，どのFMPを最初に適用するべきか選択するので， 完全な知識状態のような，初めの状態は，チョイスノードからとなる． このようなFMPアプリケーションのノードは，新しい知識状態 (それぞれの可能な特徴の値の1つ) を導く．そして，この状態は， FMPを接続する． 図の拡大は，中間目標の知識状態か，残った中間目標の1つ1つと互換性がない知識状態に達するまで続く．

例えば，図3.7は，2つのFMPsと，{ a1, b1 } の中間目標に表されるレベルの最初の図を示している． 図の構築は最初の状態から始まり，それぞれのFMPによって，チャンス状態を追加することで広がる． FMPsは5つの新しい知識状態を合わせたものへ導かれる．しかし，そのうち3つは，中間目標 { a1, b1 } とは互換性のない失敗状態となる． その他の2つの状態は，それぞれ，もう1つずつ適用される，FMPを有する． さらに，このFMPは，1つが中間目標の状態で，3つが失敗状態の，4つの知識状態へ導く．

もっと形式的に述べると，認識図の各レベルの最終的な状態として，中間目標の状態と，失敗状態を参照する． 知識状態 $n$ から最終的な状態への仮定のプロモートをするコストは，知識状態 $n$ の予期される決定コスト (EDC) と呼ばれ， FMP $v$ を用いた状態 $n$ から最終的な状態へ達する予期されるコストは，$n$ と $v$ の予期されたパスコスト (EPC) と呼ばれる． 特徴はそれぞれ独立しているので，集合 $R(v)$ として，FMP $v$ の結果の可能性と， $P ( f\vert v, n), f \in R(v)$ として戻ってくる特殊な特徴の値 $f$ の確率を示す．

知識状態のEDCsは，最終的な状態から始まり，認識図を用いて，逆方向に働くことで計算される． 明確に言えば，中間目標，または失敗状態のEDCはゼロになる:

$$EDC(n) = 0,~ n \in \{ terminal~ states \}.$$

FMPアプリケーションのノードからの最終的な状態への到達の予期されるパスコストは，

$$EPC(n,v) = C(v) + \sum\limits_{f \in R(v)} {\left( {P(f\vert n,v) \times EDC(n \cup f)} \right)}$$

であり，ここで， $n$ は特徴の値の集合として表現される知識状態，$n \cup f$ は特徴の値 $f$ が戻ってくるFMP $v$ に結果としてなる知識状態， そして，$C(v)$ は $v$ に適用する見積もられたコストとなる．

知識状態のEDCは，このEDCから実行されるFMPsの最も小さいEPCで，

$$EDC(n) = \mathop {\min }\limits_{v \in VP(n)} \left( {EPC(n,v)} \right)$$

となり，ここで， $VP(n)$ はノード $n$ のFMPsアプリケーションの集合となる． 最小のコストを決定するツリーは，特設的な非周期の図の単一の通過を行うことと，最終のノードから始めることと， 最初の状態と逆方向の作業をすることで作り出される． 各知識状態においては，その取り除く仮定はその状態から適用される各FMPのEPCを計算し， 最も小さいEPCの1つ以外の全てのFMPアプリケーションのノードを取り除く． 最終的な結果は，最小コストの決定ツリーになる．

図3.8は，図3.7に示された最初の図を取り除いた結果で，最終ノードから始まり，逆に働いている． 取り除くアルゴリズムが考慮される最初のチョイス状態は $a1$ と $b1$ になる． しかし，これらの状態は，それぞれただ1つの選択を有しており，最小のコストの選択は効果がない． システムが特徴Aと特徴Bのどちらを計算するか選択できるので， 次のチョイスノードは最初の状態 { } で，2つの選択がある． しかし，図3.7に示されているように，特長Bが最初に計算された場合，仮定の証明の予期されたコスト (EPC) は1.53で， 特長Aからの場合は，1.4になる．結果的に,最適アルゴリズムは,図3.7の最初のノードからBの選択を取り除くことで, 図3.8は，最適な決定ツリーだけを示している.