検索空間で最適なパスを見つけるためのA* アルゴリズムに精通しており、かなり標準的であると思われるその変形を探しています。
非形式的には、A* は遷移に続く一連の状態をトラバースします。検索はヒューリスティック関数によって導かれ、各状態について、そこから目標に到達するためのコストの下限を推定します。
操作上、次の値/関数でそれを記述することができます (私の Scala 表記法を許してください。数学よりも読みやすいと思います)。
val initial : State
val goal : State
def possibleTransitions(s : State) : Set[Transition]
def followTransition(s : State, t : Transition) : State
def estimateDistance(s1 : State, s2 : State) : Double
...そして、への遷移goalが見つかると、検索は終了します。
少し異なる設定のアルゴリズムを探しています。状態に遷移を適用するとき、1 つの新しい状態を生成する代わりに、新しい状態のセットを生成する必要があります。直観的に、これは、最終目標に到達するために満たす必要のある一連のサブ目標に対応しています。これにより、署名が次のように変更されます。
def followTransition(s : State, t : Transition) : Set[State]
すべての分岐が解決されると、検索は終了します。
このような問題を解決する 1 つの方法は、状態が一連の状態に対応する A* 問題として構成することだと思われますが、問題の構造を利用するためのより良い方法があるに違いないと信じずにはいられません。