用于优化模拟决策的最佳算法

Question

我正在寻找最佳算法来优化同时进行的决策,以便在合理的时间内找到快速结果.同意做了许多"滴答",偶尔需要做出决定.最终达到目标状态.(如果做出非常糟糕的决定,就有可能永远不会达到目标状态)

有很多目标国家.我想找到具有最少蜱数的目标状态(蜱在现实生活中大致相当于一秒."我基本上想要决定在尽可能短的几秒内做出哪些决定来达到目标​​,

关于问题域的一些观点:

• 直接蝙蝠我可以产生一系列选择,这将导致一个解决方案.它不会是最佳的.
• 我有一个合理的启发式函数来确定什么是一个好的决定
• 我有一个合理的功能来确定从节点到目标的最小可能时间成本.

算法:

• 我需要处理这个问题大约10秒钟,然后给出最好的答案.
• 我相信A*会找到我最理想的解决方案.问题是决策树会很大,以至于我无法快速计算出来.
• IDA*会在10秒钟内给我一个很好的前几个选择,但我需要一条路径到目标.

目前我认为我将从目标的已知非最佳路径开始,然后可能使用模拟退火并尝试在10秒内改进它.

试图解决这类问题的研究算法是什么？

Answer 1

看一下有限差异搜索，重复最大差异搜索或波束搜索的越来越宽松的限制。

如果您有良好的启发式方法，您应该能够使用它来比较各个选择 - 对于有限差异搜索，并比较部分解决方案，对于波束搜索。

看看是否可以为部分解决方案的任何扩展的好坏设定一个上限。然后，您可以删除部分解决方案，这些解决方案无法扩展以击败启发式结果，或者在一系列深度不断增加的迭代搜索中迄今为止找到的最佳结果。