5

我正在寻找最佳算法来优化同时做出的决策，以便在合理的时间内找到快速的结果。simultaion 做了一些“滴答”，偶尔需要做出决定。最终达到目标状态。（如果您做出非常糟糕的决定，可能永远无法达到目标状态）

有许多许多目标状态。我想用最少的滴答声找到目标状态（一个滴答声大约相当于现实生活中的一秒。”我基本上想决定在尽可能短的时间内做出哪些决定来达到目标​​，

关于问题域的几点：

  • 我可以立即产生一系列选择，这些选择将导致解决方案。它不会是最优的。
  • 我有一个合理的启发式函数来确定什么是一个好的决定
  • 我有一个合理的函数来确定从节点到目标的最小可能时间成本。

算法：

  • 我需要处理这个问题大约 10 秒钟，然后给出我能给出的最佳答案。
  • 我相信 A* 会为我找到最佳解决方案。问题是决策树太大了，我无法足够快地计算它。
  • IDA* 会在 10 秒内给我很好的前几个选择，但我需要一条通向目标的路径。

目前我正在考虑从已知的非最佳目标路径开始，然后可能使用模拟退火并尝试在 10 秒内改进它。

什么是一个很好的算法来研究试图解决这类问题？

4

2 回答 2

1

让我们弄清楚一些事实。

1）确定哪个决策是最好的唯一方法是测试每个可能的决策并根据某些标准评估结果。

2）我们极不可能有时间来决定通过每一个可能的决定，因此我们必须限制未来我们将评估该决定的时间。

3）我们不太可能做出最好的举动〜永远〜。不只是经常，而是永远。除非你只有几个决定，否则每次你做出决定时，都会有一个更好的决定，你没有做。

4）我们可以利用我们之前的决定如何发挥我们的优势。

把所有这些放在一起......假设当我们做出决定时，我们评估未来 30 个滴答声中会发生什么，在 30 个滴答声中，我们可以检查实际发生的情况是否与我们在 30 个滴答刻前模拟的相符。如果是这样，我们知道该决定会导致可预测的结果，我们应该更少使用该决定。如果我们没有这样做，或者结果比我们希望的要好，我们应该更多地使用这个决定。

理想情况下，您将在...模拟您的模拟...中使用您的逻辑来评估它。然后，当您进入“真实”模拟时，您就有更好的机会更早地做出更好的决定。当然，与模拟的模拟结果相比，对实际模拟结果的结果给予更高的权重。

于 2011-02-24T01:03:23.013 回答
1

看看有限差异搜索，在最大差异搜索或光束搜索上以越来越宽松的限制重复。

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

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

于 2011-02-24T05:46:03.167 回答