ノードがシステムの状態を表し、エッジがアクションを表す深さの木B(つまり、すべてのパスの長さが) を考えてみましょう。B
各アクションa in ActionSetにはゲインがあり、システムをある状態から別の状態に移行させます。一連のアクションA-B-CまたはC-B-A(またはこれらのアクションの他の順列) を実行すると、同じ利益が得られます。さらに：
- 前に実行されたアクションの数が多いほど、が求められ
aたときの合計ゲインの増加は低くなりますa - 各パスによって達成されるゲインは、量 よりも大きくすることはできません
H。つまり、一部のパスでは よりも低いゲインを達成する場合がありますがH、アクションを実行すると合計ゲインが に等しくなるとH、その時点以降に実行される他のすべてのアクションはゲインを獲得します。0 - 一連の行動によって得られるもの
#b,h,j, ..., a#はg(a)(0 <= g(a) <= H) - ルートからリーフへのパスでアクションが実行されると、同じパスで再度実行することはできません
アルゴリズムの適用1. 次のアルゴリズムを適用します (A* に似ています)。
- ルートから開始します。
- のすべてのアクションを含むツリーの最初のレベルを展開し
ActionSetます。展開された各アクションaには gainがありますf(a) = g(a) + h(a)。ここで、g(a)は前述のように定義されており、他のアクションh(a)を実行することで得られるものの推定値ですB-1 a*最大化するアクションを選択f(a)- の子を展開します
a* B最高を保証するルートからリーフまでのアクションのパス全体に到達するまで、2 ～ 3 を繰り返しf(n)ます。新しく選択されたアクションは、以前のレベルで放棄されたノードからも選択できることに注意してください。たとえば、a*ノードの最大化を展開した後f(a)にルートの子である場合、それが新しい最適なノードとして選択されます
アルゴリズムの適用 2。g(n)ここで、知識プラスヒューリスティック関数のコンポーネントのみを調べる貪欲なアルゴリズムがあるとしますf(n)。つまり、このアルゴリズムは、既に獲得したゲインに従ってアクションを選択します。
a最初のステップで、ゲインを最大化するアクションを選択しますg(a)b2番目のステップで、ゲインを最大化するアクションを選択しますg(b)
請求。実験的証拠により、2 つのアルゴリズムが同じ結果をもたらすことがわかりましたが、これは混在している可能性があります (たとえば、最初のアルゴリズムはシーケンスA-B-Cを示唆し、2 番目のアルゴリズムは を示唆していますB-C-A)。しかし、私はその理由を理解することに成功しませんでした。
私の質問は: 2 つのアルゴリズムが同じ結果を返すことを証明する正式な方法はありますか?
ありがとうございました。