假设我想改变 A* 中的逻辑，试图找到最有用的路径（即增益最高的路径）而不是找到最短路径（即成本最低的路径）。
就我而言，目标并不固定为唯一的结束节点。节点定义为具有距离的任何节点B从起点开始。
在普通版本（“找到最短路径”）中，我需要不要高估成本（即找到小于或等于实际成本的启发式方法）。
在我的修改版本中（“找到最有用的路径”），边缘被标记为效用而不是成本，并且我希望在给定通过的约束的情况下最大化最终收益最多 B 条边。为了使 A* 发挥作用，我是否应该高估效用（即找到大于或等于实际效用的启发式方法）？
EDIT:更正式化，让
f(n) = g(n) + h(n)
是节点的效用，由以下部分组成：
-
g(n)：从起始节点到n
-
h(n)：启发式，即对我从n到目标（其中目标是一个节点，其与起点的距离为B)
Should h(n)被高估并且f(n)最大化以确定最佳路径？
请注意B是一个预算，因此它可以完全花完，即没有必要找到一条比B steps.
你的问题是最长路径问题，即强 NP 困难。这意味着，不仅有（几乎可以确定）不禁食exact算法，但也有（几乎可以确定）不好近似算法。
不幸的是，您要么必须暴力破解，要么诉诸各种方法全局优化技术，如退火、遗传编程等。
正如 @Charles 所建议的，否定边权重的符号是行不通的，因为 A* 无法处理负边权重。和其他算法 which can处理负边权重仍然无法处理负循环。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
