Dijkstra 或 A* 是否可以使用完整路径的成本函数正常工作？
Will Dijkstra or A* work correctly with cost a function of full path?
我正在考虑的是：当一个节点成为当前节点时，计算"on the fly"每个邻居的成本，其中成本是到达当前节点的完整路径的函数。我无法想象这会如何打破算法的假设，但我有一种感觉。
无论如何，出于存储原因，我正在进行即时计算，但新事物是成本是所涉及的两个节点以上的函数。可以吗？
如果可能预先计算每对节点之间的旅行成本，那么绝对没有理由不能使用 Dijkstra 或 A*，只要因为 none 你的边缘权重可以是负数。
如果无法预先计算成本，则很可能是您在寻路过程中做错了什么，因为这可能取决于搜索的状态。 :)
据我所知，它并没有打破Dijsktra算法的假设，即你仍然可以继续使用它。然而，当你想这样做时，它确实需要你完全重新构造你的图表。
更详细地说，您不能再简单地使用 Node-Indices {1,...,N}，但是您的状态需要类似于 {(1,all-ways-to-get-there), ... , (N,all-ways-to-get-there)}。这将带来糟糕的指数缩放。
这是因为 Dijkstra 算法（如动态规划）依赖于问题可以分成几部分并在那里解决的事实，而这里不是这种情况。
这里有一个例子，为什么它不能被 "normal" Dijkstra 完成：假设你的函数将成本分配给给定的方式 {node_1, node_2, ..., node_N} 被称为 f 并且被认为是任意的。那么目前您当前的最佳成本或最佳路径 {node_1, ..., node_{N-1}} 是完全无关紧要的，因为您无法对此做出任何暗示 - 您所能做的就是计算出每条可能的路径，该路径呈指数增长并且对于大图是没有希望的。
但是，如果您的函数满足某些要求，可能还有更好的事情要做。例如，在最简单的情况下，当你的函数是线性的，f({path1} + {path2}) = f({path1}) + f({path2})]，"original" Dijkstra 算法被恢复。
我正在考虑的是：当一个节点成为当前节点时，计算"on the fly"每个邻居的成本，其中成本是到达当前节点的完整路径的函数。我无法想象这会如何打破算法的假设，但我有一种感觉。
无论如何，出于存储原因，我正在进行即时计算，但新事物是成本是所涉及的两个节点以上的函数。可以吗？
如果可能预先计算每对节点之间的旅行成本，那么绝对没有理由不能使用 Dijkstra 或 A*，只要因为 none 你的边缘权重可以是负数。
如果无法预先计算成本，则很可能是您在寻路过程中做错了什么，因为这可能取决于搜索的状态。 :)
据我所知，它并没有打破Dijsktra算法的假设，即你仍然可以继续使用它。然而，当你想这样做时，它确实需要你完全重新构造你的图表。
更详细地说，您不能再简单地使用 Node-Indices {1,...,N}，但是您的状态需要类似于 {(1,all-ways-to-get-there), ... , (N,all-ways-to-get-there)}。这将带来糟糕的指数缩放。
这是因为 Dijkstra 算法（如动态规划）依赖于问题可以分成几部分并在那里解决的事实，而这里不是这种情况。
这里有一个例子，为什么它不能被 "normal" Dijkstra 完成：假设你的函数将成本分配给给定的方式 {node_1, node_2, ..., node_N} 被称为 f 并且被认为是任意的。那么目前您当前的最佳成本或最佳路径 {node_1, ..., node_{N-1}} 是完全无关紧要的，因为您无法对此做出任何暗示 - 您所能做的就是计算出每条可能的路径，该路径呈指数增长并且对于大图是没有希望的。
但是，如果您的函数满足某些要求，可能还有更好的事情要做。例如，在最简单的情况下，当你的函数是线性的，f({path1} + {path2}) = f({path1}) + f({path2})]，"original" Dijkstra 算法被恢复。