如果启发式函数以一致的方式高估，那么可接纳性在 A* 搜索中是否重要？
Does admissibility even matter in A* search if the heuristic function overestimates in a consistent manner?
假设节点的启发值是达到目标的实际成本 x 10^5 怎么办？具有最小 f 成本的节点仍然从优先级队列的顶部弹出。
例如：f(n) = g(n) + h(n)、where h(n) = h1(n) x 10^5, where h1(n) = h1′(n)
根据定义，h这里是对实现目标的实际成本的高估。
我问的原因是因为我无法真正看到有或没有该常数因子的算法在性能上的差异。如果那么 h 是否可以接受为什么会很重要？
What if the heuristic value of a node is, let’s say, actual cost of
getting to goal x 10^5?
假设使用完美的启发式函数 h'(n)，它总是等于从n到最近的目标节点的路径的剩余成本，如果启发式函数在常数因子中高估，那么将找到相同的路径不管h是否是可接受的。
您可以将您的示例视为使用 Dijkstra 在图 G 上进行搜索，其中所有弧的成本乘以一个常数因子，从而产生一个新图 G'。 G 中的每条最短路径都是 G' 中的最短路径。
备注：如果启发式高估但不是所有节点的常数因子，则答案将相反。在这种情况下，A*并不能保证找到最优解。
编辑： 阅读@Mehrdad 关于概括评估函数以考虑 non-additive 成本 的回答后，从纯粹的角度出发显然，我不会说我们在成本为 non-additive 时应用 A*。 A* 解决了最短路径问题 并且假设成本是累加的，实际上，它的所有形式属性都基于该假设。
如果将成本最小化标准概括为包括 non-additive 解决方案路径的成本度量，那么恕我直言，我们正在谈论一个不同的问题，因此解决它的算法也不同。在这种情况下，我认为这个问题在文献中被称为NSAP（non-additive最短路径）。可以在 Rina Dechter 和 Judea Perl 的这篇论文中找到这方面的一个例子：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3090&rep=rep1&type=pdf（第 507 页）他们称解决泛化问题 BF* 的算法，因为他们正在研究 A* 在移除限制、附加成本度量和附加评估函数时的行为。
是：
总的来说：可采性是A*最优的充分条件，而不是必要条件。当然，您可能会发现存在不可接受的启发式算法，它也是 returns 最佳结果；只是此时 A* 不提供任何保证。
特别是：“以一致的方式”含糊不清，但如果您考虑“缩放”以符合此描述，请注意您的缩放启发式可能会失败 如果成本不是累加的。请注意，A* 而不是 要求评估函数为 f = g + h。虽然乍一看不直观，但一个问题完全有可能和现实地具有其他评估函数，其中 甚至没有意义 添加路径成本（例如，您的成本可能是概率） .
另请注意，“一致性”has an entirely different meaning 与您正在使用的一致，因此在使用该术语时要小心。在通常的定义下，一致的启发式不可能是不可接受的。
假设节点的启发值是达到目标的实际成本 x 10^5 怎么办？具有最小 f 成本的节点仍然从优先级队列的顶部弹出。
例如：f(n) = g(n) + h(n)、where h(n) = h1(n) x 10^5, where h1(n) = h1′(n)
根据定义，h这里是对实现目标的实际成本的高估。
我问的原因是因为我无法真正看到有或没有该常数因子的算法在性能上的差异。如果那么 h 是否可以接受为什么会很重要？
What if the heuristic value of a node is, let’s say, actual cost of getting to goal x 10^5?
假设使用完美的启发式函数 h'(n)，它总是等于从n到最近的目标节点的路径的剩余成本，如果启发式函数在常数因子中高估，那么将找到相同的路径不管h是否是可接受的。
您可以将您的示例视为使用 Dijkstra 在图 G 上进行搜索，其中所有弧的成本乘以一个常数因子，从而产生一个新图 G'。 G 中的每条最短路径都是 G' 中的最短路径。
备注：如果启发式高估但不是所有节点的常数因子，则答案将相反。在这种情况下，A*并不能保证找到最优解。
编辑： 阅读@Mehrdad 关于概括评估函数以考虑 non-additive 成本 的回答后，从纯粹的角度出发显然，我不会说我们在成本为 non-additive 时应用 A*。 A* 解决了最短路径问题 并且假设成本是累加的，实际上，它的所有形式属性都基于该假设。
如果将成本最小化标准概括为包括 non-additive 解决方案路径的成本度量，那么恕我直言，我们正在谈论一个不同的问题，因此解决它的算法也不同。在这种情况下，我认为这个问题在文献中被称为NSAP（non-additive最短路径）。可以在 Rina Dechter 和 Judea Perl 的这篇论文中找到这方面的一个例子：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3090&rep=rep1&type=pdf（第 507 页）他们称解决泛化问题 BF* 的算法，因为他们正在研究 A* 在移除限制、附加成本度量和附加评估函数时的行为。
是：
总的来说：可采性是A*最优的充分条件，而不是必要条件。当然，您可能会发现存在不可接受的启发式算法，它也是 returns 最佳结果；只是此时 A* 不提供任何保证。
特别是：“以一致的方式”含糊不清，但如果您考虑“缩放”以符合此描述，请注意您的缩放启发式可能会失败 如果成本不是累加的。请注意，A* 而不是 要求评估函数为 f = g + h。虽然乍一看不直观，但一个问题完全有可能和现实地具有其他评估函数，其中 甚至没有意义 添加路径成本（例如，您的成本可能是概率） .
另请注意，“一致性”has an entirely different meaning 与您正在使用的一致，因此在使用该术语时要小心。在通常的定义下，一致的启发式不可能是不可接受的。