理解深度优先分支和星际争霸2的绑定实现

Question

问题是我发现很难理解DFBB是如何工作的，对于这种情况，参数和输出应该是什么

我正在为《星际争霸2》创建一个AI，它将处理游戏中的构建顺序（对于人族团队）。我计划遵循链接（见下文）中描述的方法，该方法遵循与我所追求的非常相似的东西。总结一下我的计划：

需要建造的不同类型的建筑物的清单会给我。建筑需要矿物和天然气（这是游戏中的货币），一些建筑有先决条件（意味着其他建筑需要先建造，然后才能建造），建造它们需要一定的时间

在这篇文章中，他们使用了深度优先分支和绑定来计算最佳的构建顺序，这意味着可以以最快的方式构建列表中的建筑。这是他们的伪代码：

其中状态S由S=（当前游戏时间、可用资源、正在进行但尚未完成的操作、工人收入数据）表示。这篇文章描述了S是如何派生的，它是通过三个函数来实现的，所以我理解bit

如前所述，我正在努力理解在他们所描述的伪代码中，起始状态S、目标G、时间限制t和界限b应该表示为什么

我只知道三件事是肯定的：需要建造的建筑物的清单，我目前拥有的消耗品（矿物和天然气），资源（即我已经在游戏中拥有的建筑物）。这应该以某种方式应用于算法，但不清楚函数的输入应该是什么。输出应该是一个按正确顺序排序的列表，因此，如果我按照建筑物进入的顺序在何处建造建筑物，那么它应该全部解决，并且应该是可以在其中完成的最佳时间

例如，我应该迭代列表中的建筑，并在每个元素上运行DFBB，目标是查看建筑是否可以建造。但是，在这种情况下，时间限制应该设置成什么样子，界限意味着什么？这仅仅是成本吗

请解释如何在列表上运行此函数，以便找到构建它的最佳路径。这篇文章很容易阅读，但是我需要一些帮助来理解它是如何工作的，以及如何将它应用到我的问题中

文章链接：https://ai.dmi.unibas.ch/research/reading_group/churchill-buro-aiide2011.pdf

Answer 1

开始状态S是游戏开始时的初始状态。我相信你们有100个雷区和指挥中心还有12个？SCV，这就是你的开始

这里的目标是列出你想要的建筑。满足的条件是所有的建筑目标也都在S

时间限制是指你愿意花费多少时间来获得结果。如果你将它设置为5秒，它可能会给你一个次优的解决方案，但它会在5秒内完成。如果算法完成搜索，它将提前返回。如果您不介意，请将其忽略，但请确保为文件编写解决方案，以防发生意外

Bound b是构建所有内容的游戏内时间限制。您最初将其设置为无限或某个明显的值（如10分钟？）。当你找到一个解决方案时，b会被更新，所以你找到的每一个新解决方案都必须比上一个更快（在游戏中）

一些注释。确保可能的操作（步骤9中的子级）包括不做任何事情（等待更多资源）和构建SCV

另一件可能缺失的事情是SCV运动速度的正确建模。这些单位需要搬到一个地方去建造一些东西，他们也需要时间才能重新开始采矿