铁塔防御资金生成优化

Question

我正在考虑优化塔式防御游戏Bloons TD 6中的货币生成(“农业”)。为了简单起见，只考虑一小部分农场类型，它每一轮购买和生产一定数量的钱(实际上农场在这一轮中产生金钱，但忽略这一点)。也有可能以一定比例的购买成本(例如75%)出售农场，最终目标是在固定数量的回合(例如40次)之后积累尽可能多的资金。

如果有帮助，下面是一些示例数字：

• 商人:价格3000美元，每轮
• 优惠贸易200美元:从商船升级成本5500美元，从
• 贸易帝国每轮生产500美元:限制1，从优惠贸易升级到23000美元，每轮生产800美元，有一个复杂的交互作用，根据有多少

而增加现有商人和优惠贸易的收入。

我的第一个想法是将其实现为动态编程，但没有一种简单的方法可以将其分解为子问题。状态可以表示为(圆形、金钱、农场)，但这些值可能会成倍地呈现出许多(整数)值，而且也不清楚要最大化什么:贪婪地使每轮资金最大化永远不会导致任何投资。

查看此问题的一种自然方法是树搜索，其中每个节点表示每一轮的游戏状态，每个边缘表示在各轮之间可能采取的操作(可以进行多个操作，如买入/卖出)。另一种说法是，每一个边都是一个动作，例如“买农场”或“前进一轮”。

一种比穷尽搜索更好的树搜索必须有某种启发式的指导，所以我从现在到最后提出了金钱+总销售价值+总农场收入的启发式。这代表结束的钱，如果你不做进一步的最后，然后出售所有的农场。

此外，我想出了一些潜在的搜索策略：

有限深度的

1. 贪婪搜索:尽可能深入地搜索，例如5轮，移动到具有最佳启发式值的解，然后重复。我不确定这个算法是否有名字，但就像国际象棋引擎只能看到10步深，然后不得不移动(然而，国际象棋引擎使用α-β剪枝来修剪多个分支)

。

如果启发式值至少是已知启发式值的一小部分，并且被认为足够好，

1. Branch-and-bound:将保持候选解决方案队列，并分支(前进一轮并尝试所有操作)。我不清楚具体的实现细节。

这些是现实的做法吗？用什么算法来解决这类离散步骤问题的优化问题？

Answer 1

我建议计算每个农场的净现值(净现值)。从每个给出最大NPV的状态中选择边缘。从零折现率开始，然后进行实验。

例如(根据你的例子)

NPV(商船)= 200 * RR - 750

( RR是剩余的子弹数。)

如果RR = 40，那么NPV是7250，如果RR = 5，NPV = 250