使用多值节点查找树中的最小路径

Question

我的数学课程远远落后，我正在努力为我遇到的问题找到一个合适的解决方案：我有一棵树，其中节点是动作，并且是“加权”的。根据多个标准：所述行动的成本，所需的时间，必要的资源，干扰等......

我想在这棵树中找到最小化成本和时间的路径，例如干扰和成本和时间等。我的问题是我不知道怎么做，除了通过提出全局成本函数F（成本，时间，资源......），并使用F（...）的结果作为我唯一的权重应用常规树遍历算法。 但是，我怎么想出F？像“F（成本，时间，资源）= a *成本+ b *时间+ c *资源”之类的东西感觉非常“不专业”......

编辑：

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

因此，如Stephan所说，似乎不可避免地要提出一个公式，它将所有这些参数减少到每个节点的一个全局成本，然后我可以在树上行进时在节点之间求和，然后选择最小化总成本的路径。

所以我想我的问题确实是，有一种选择该功能的方法吗？

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

Answer 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被理解为“权重”）不是“非专业的”。至少，如果你不知道更合适的成本函数是什么。

编辑：

  

因此，如Stephan所说，似乎不可避免地要提出一个公式，它将所有这些参数减少到每个节点的一个全局成本，然后我可以在树上行进时在节点之间求和，然后选择最小化总成本的路径。

注意。事实上，只有当F是线性时，这种策略才有意义。当然，成本，时间，资源等是附加功能，在时间（node1 - > node2 - ＆gt; node3）=时间（node1）+时间（node2）+时间（node3）的意义上，但通常这不是F的情况，除非它是线性的。 （即F（成本（node1 - > node2））= F（成本（node1）+成本（node2））！= F（成本（node1））+ F（成本（node2））。）

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

Answer 2

提出F是最重要的事情。如果我能给你6个成本，5个时间或5个时间和6个成本，你更喜欢哪个？您的成本函数需要考虑到这一点。遗憾的是，没有算法会为你解决这个问题。在我坐下来写了一篇我正在研究的优化应用程序的F之前，我否认了一个星期。最糟糕的情况是，留下参数供用户修补。

Answer 3

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

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

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