我熟悉用于在搜索空间中查找最佳路径的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。
我正在寻找一种稍微不同设置的算法：当将转换应用到状态时，我需要生成一组新状态，而不是生成一个新状态。直观地说，这对应于一组子目标，我需要满足这些子目标才能达到最终目标。这会更改签名，如下所示：
def followTransition(s : State, t : Transition) : Set[State]
当所有分支都解决时，搜索终止。
似乎解决此类问题的一种方法是将它们构建为 A* 问题，其中一个状态对应于我的一组状态，但我不禁相信必须有更好的方法来利用问题的结构。