algorithm - 使用什么算法来计算最快的 build 建筑物顺序？

对于我正在玩的游戏，我想知道 build 多个建筑物的最快顺序。有问题的游戏是OGame，如果您熟悉它，那将是一个加号，但显然我将解释游戏的基本知识:

播放器具有许多可用的差异资源。

玩家可以 build 建筑物，一次最多可以 build 一栋建筑物。

建筑物具有不同的级别，例如A建筑物1层，A建筑物2层等。

build 建筑物的资源成本每级增加。

Buildings也需要花费时间来构建，因此每级也增加。

一些建筑物产生不同的资源，每级建筑物的资源也会增加。

一些建筑物会更改计算，从而使建筑物的 build 速度更快。

我已经明确选择不显示方程式，因为它们不是简单明了的，不需要建议算法。

我选择通过以下操作对此建模:

StartUpgradeBuildingAction :此操作通过从可用资源中减去成本来启动升级过程。

FinishUpgradeBuildingAction :此操作通过及时进行来完成升级过程。这也会产生资源。

WaitAction :此操作将时间提前X秒，同时根据资源生产来生产资源。

应当注意的是，状态空间是无限的，其特征在于存在通往最终配置的多条路径(所有请求的建筑物均已 build )，每条路径可能花费不同的时间和不同的资源量。你最终会最终。现在，我对最快的路径(顺序)最感兴趣，如果有多个相等的路径，则应该选择成本最低的路径。

我已经尝试了以下方法:

广度优先搜索

深度优先搜索

迭代加深深度优先搜索

迭代加深A *搜索

A *搜索

不幸的是，所有这些算法要么花费太长时间，要么使用太多内存。

由于谷歌搜索没有给我任何进一步的线索，因此我在这里提出以下问题:

是否已有与我的问题匹配的模型？我想以商业信息系统为例，就已经遇到了这类问题。

是否存在提供最佳解决方案的算法？如果是这样，哪一个？

是否有一种算法可以提供接近最佳解决方案的解决方案？如果是这样，哪一个？

任何帮助表示赞赏。

最佳答案

没有一种算法可以为您的问题提供最佳解决方案。您尝试的方法都是合理的。但是，尝试过A *搜索并没有多大意义，因为A *搜索依赖于评估特定配置的启发式方法(即，它为耗时量， build 的建筑物的数量和选择提供了一个值资源等)。通过良好的启发式搜索，A *搜索可能会迅速为您提供一个很好的解决方案。找到这种启发式方法需要对参数有充分的了解(建筑物的成本，升级的好处等)。

但是，我的感觉是，您的问题的结构方式使得一系列构建决策可以在经过少量步骤之后明显胜过其他一系列决策。假设您按此顺序 build 建筑物A，B和C。只要有必要的资源可用，就可以构建每个组件。然后，您尝试使用C，A，B顺序。您可能会发现，如果您拥有相同的建筑物，则另一种方法会主导另一种方法，但是在一种方法中，您的资源要多于另一种方法。当然，如果您拥有许多不同的资源，则可能性较小。您可能拥有更多的资源X，但拥有更少的Y，这使得情况很难进行比较。如果可能的话，好处是您无需进行启发式操作，但您可以清楚地看到应该遵循的道路以及应该切断的道路。

无论如何，我将探索需要采取的步骤，直到您基于这样的考虑找到可以消除的路径为止。如果您很快找到它们，则应遵循广度优先的策略并尽快修剪分支。深度优先搜索会冒您花费大量时间探索劣等路径的风险。

关于algorithm - 使用什么算法来计算最快的 build 建筑物顺序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35139949/