我正在玩一个视频游戏，我想制作一个程序来计算实现固定 6 项目目标的全局最优构建/升级路径。
需要考虑时间、成本、库存限制和有效性（短期/中期/长期）评级。识别局部有效性峰值也受到欢迎，但可选。我不知道如何对这个问题进行分类，但我猜它是一种图形搜索。多个标准正在优化的事实让我感到困惑。
问题详情：
- 您的包中有 6 个免费插槽可存放物品。
- 项目分为两类：基本项目和复合项目。
- 复合项目是从基本项目和其他复合项目构建/合并的。
- 如果您有足够的金币，您可以一次性购买复合物品及其缺失的子组件，只需使用 1 个库存槽。
- 各种复合项目的构建路径是固定的，许多基本组件包含在多个配方中。
- 随着时间的推移，黄金以固定的速度赚取，也以小的非确定性爆发的形式赚取。
- 时间是有界的：它以固定的刻度（秒）递增，最大值：2400。
- 存在不超过 50 个项目，可能更少。
所以，想想问题...
首先解决黄金/时间问题
我们可以忽略不确定性方面，也可以使用一些统计平均值。让我们让生活变得轻松，暂时忽略它。由于黄金和时间现在在我们的简化版本中直接相关，因此它们可以在逻辑上合并。
可行路径的组合扩展
可以从 6 个目标项目中的每一个构建自上而下的图表，指示它们各自的升级层次结构。可以连接在各个层次结构之间共享的组件，从而做出分支决策。组件之间的边缘可以通过它们的成本来加权。在这一点上，这听起来像是一个最短路径问题，除了有多个并行和重叠的目标。
现在的问题是：库存限制如何影响这一点？
库存/成本约束添加了一个上下文，它既禁用（没有空闲槽；没有足够的金币），又启用（两个项目合并释放槽）各种分支决策，基于先前的选择和经过的时间。此外，在某些情况下，节省黄金并在非固定时期内无所事事的可能性可能是最佳的。
如何扩展所有可行的可能性？是否必须在每个给定步骤完成？总共有多少种组合？这是否属于拓扑组合学？
更新：
问：如何扩展所有可行的可能性？
项目构建路径是一个依赖图。依赖关系的正确评估顺序由图的拓扑排序给出。一张图可能有多个有效的评估顺序。
更新 2：
问：总共有多少种组合？
好像是要算的，没有数值公式。
算法 3.2，第 150 页，“关于计算有向无环图的拓扑序数”，作者：Wing-Nig Li、Zhichun Xiao、Gordon Beavers
伪代码：
f(g) | vertex_count(g) == 1 = 1
f(g) = ∑ {f(g \ {v}) for all v ∈ deg0set}
deg0set = {vertex_in_degree(g,x) == 0 for all x ∈ vertices(g)}
数学代码：
f[g_/; Length[VertexList[g]] == 1] := 1
f[g_] := With[
{deg0set = Select[VertexList[g], VertexInDegree[g,#] == 0&]},
Sum[f[VertexDelete[g,v]], {v,deg0set}]
]
评级有效性
如果上述扩展产生的可能性少于几十亿，我们可以使用 OpenCL/CUDA 进行穷举搜索。我不确定还有哪些其他选项可用，因为大多数图形搜索似乎只是解决一个标准。