0

我的数学课远远落后，我目前正在努力为我遇到的问题找到一个体面的解决方案：我有一棵树，其中的节点是动作，并且根据多个标准“加权”：所说的行动，它将花费的时间，必要的资源，干扰等......

我想在这棵树中找到最小化成本和时间的路径，或者干扰和成本和时间等。我的问题是我不知道该怎么做，除非上来使用全局成本函数 F(cost, time, resources,...)，并使用 F(...) 的结果作为我唯一的权重应用常规树遍历算法。但是，我该如何想出 F ？像“F(cost, time, resources) = a * cost + b * time + c * resources”这样的东西感觉很“不专业”......

编辑：

我想避免使用“求和”这个词，因为我不确定这是否真的是要走的路，但本质上，这就是我正在做的事情：计算来自的每个“路径”或“分支”的总成本该顶部节点，到其中一个叶子，并选择最小化成本的“路径”或“分支”。问题是每个节点都有一个基于所需时间、财务成本、资源使用等的权重。

因此，正如斯蒂芬所说，似乎不可避免地必须提出一个公式，将所有这些参数减少到每个节点的一个全局成本，然后我可以在沿树向下移动时跨节点求和，并选择路径最小化总成本。

所以我想我的问题真的是，是否有选择该功能的方法？

感谢您的回答和评论，现在我的头脑开始变得更加清晰了。

4

3 回答 3

1

想出F是最重要的。如果我可以给你 6 成本和 5 时间或 5 时间和 6 成本，你更喜欢哪个？您的成本函数需要考虑到这一点。不幸的是，没有任何算法可以为你解决这个问题。在我坐下来为我正在开发的优化应用程序写 F 之前，我否认了这一点。最坏的情况，将参数留给用户修改。

于 2009-01-08T10:45:55.907 回答
1

假设我们有四对 (x, y)，例如 (1, 4), (1, 5), (2, 3), (3, 3)。现在您要最小化“x 和 y”。你什么意思？如果您先最小化 x，然后再最小化 y，您最终会得到 (1, 4)。如果首先最小化 y，然后最小化 x，你会找到 (2, 3)。

除非您选择全局成本函数 F(x, y)，就像在您的观察中一样，否则我看不出“两者”的任何含义。（无论如何，一旦选择了 F，可能仍然有多个最小点。）顺便说一句，在我看来，线性组合（正乘数 a,b,c 被理解为“权重”）根本不是“不专业的” ，至少如果您不知道更合适的成本函数可能是什么。

编辑：

因此，正如斯蒂芬所说，似乎不可避免地必须提出一个公式，将所有这些参数减少到每个节点的一个全局成本，然后我可以在沿树向下移动时跨节点求和，并选择路径最小化总成本。

警告。实际上，只有当 F 是线性的时，这种策略才有意义。当然，成本、时间、资源等是加法函数，在某种意义上说 time(node1 -> node2 -> node3) = time(node1) + time(node2) + time(node3)，但通常情况并非如此对于 F，除非它是线性的。(即 F(cost(node1 -> node2)) = F(cost(node1) + cost(node2)) != F(cost(node1)) + F(cost(node2))。)

如果选择非线性全局成本函数，正确的策略是计算每个节点的总成本、总时间、从根到该节点的总资源，并仅计算（然后最小化）终端节点的 F。

于 2009-01-08T13:52:25.377 回答
0

为什么像A*这样的普通图搜索算法不起作用？

对于路径成本函数，您可以使用相关标准的运行总和。到目标的距离更加困难......

它可能是到最近的叶子的距离，为所有或部分节点预先计算，尽管这听起来非常昂贵。根据你的树的结构，你可能会想出一个更便宜的低估 - 例如，如果它完全平衡，它是微不足道的。

于 2009-01-08T11:27:43.593 回答