T を、各ノードが状態を表すツリーとします。ルートは初期状態を表します。親から子へのエッジは、状態を変更するために親で実行できるアクションを指定します (新しい状態は子になります)。各エッジはゲインに関連付けられています。つまり、親状態から子状態に遷移することで何かを得ることができます。
さらに、ルート ノードからリーフ ノードまでの各パスの長さは Q であるとします。
私の目的は、長さ Q の最も有望なパス、つまり最大のゲインを保証するパスを見つけることです (パス ゲインは、パスのエッジに付加されたゲインの合計として定義されます)。
T が非常に巨大になる可能性があるため、明らかに、ツリー全体を探索せずにこれを実行したいと考えています。
そこで、A* を適用することを考えました。A* を使用してグラフ内の最短経路を見つけることができることは知っていますが、次のようになります。
- コストはありませんが、利益があります
- 最長のパスを見つけたい (実際には、開始ノードからの距離が最長ではなく、重みを合計した場合に最大の値が得られるパス)
- グラフではなくツリーがあります（サイクルはありません！）
最終的に、私はあなたに提起したい一連の質問を思いつきました:
- A* はこのタイプの問題に適していますか? 適用することで最適解を見つけられるでしょうか？
- A* は、最短パスの場合に現在のノードからゴールまでのコストの (過小) 推定値を使用する必要があるため、現在のノードからゴールまでのゲインの (過大な) 推定値を探して使用する必要がありますか?それはヒューリスティックですか？
- T のノード n が与えられた場合、私の考えは、n の子によって達成されるゲインの合計としてヒューリスティック h(n) を計算することでした。これはそれほど厳密ではない可能性があります。もっと良い解決策があると思いますか？
編集: ツリー内のノード n が与えられた場合、n から出るエッジに付加されたゲインは量 U(n) よりも大きくすることはできません。さらに、U(n) は、n の深さが大きくなるにつれて、ますます小さくなります。