next up previous
: 実験結果 : 図の最適化 : 図のレイアウト

コストの合計を見積もる

以上の式は,知識状態の予期される決定コストの相互の帰納的な決定を見積もる. 知識状態のEDCは,その状態からの最適なFMPアプリケーションのEPCとなり, FMPアプリケーションのEPCは,FMPを適用する予期されるコストに,FMPが適用された後に残った予期されるEDCを加えたものになる. この帰納はEDCがゼロになる最終ノードにおいて,最低位となる. 対象認識図からのそれぞれのパスは,中間目標または,失敗ノードになるので, 帰納はうまく定義される.

さらに,認識のコストの合計は,最初の状態のEDCsと,LFEアルゴリズムで選択されたTPsの予期されたコストで見積もることができる. 代表的なレベルの最初の状態のEDCは,そのレベルの仮定を証明,または拒否する予期されたコストを見積もる. TPsの前提条件からそれぞれのレベルの生成された仮定の数の合計を見積もり, 最初の状態のEDCによって重複させることで, 証明のコストの合計は見積もられる. TPが実行される回数がLFEアルゴリズムの結果から見積もられるので, 認識の予期されたコストの合計は,簡単に分かる.



SATO Yoshihiro 平成12年10月3日