据我了解，启发式的可接受性是在给定的评估节点的“实际距离成本”范围内。我不得不为状态空间上的 A* 解决方案搜索设计一些启发式方法，并且使用有时可能返回负值的启发式方法获得了很多积极的效率，因此使某些节点更“接近”目标国家在边境有较高的地位。
但是，我担心这是不可接受的，但在网上找不到足够的信息来验证这一点。我确实找到了德克萨斯大学的一篇论文，该论文似乎在后来的一个证明中提到“......因为启发式函数是非负的”。谁能证实这一点？我认为这是因为返回一个负值作为您的启发式函数会使您的 g-cost 变为负数（因此会干扰 A* 的“默认”dijkstra-esque 行为）。
结论：产生负值的启发式函数本身并不是不可接受的，但有可能破坏 A* 的保证。
有趣的问题。从根本上说，可接纳性的唯一要求是启发式算法永远不会高估到目标的距离。这很重要，因为在错误的地方高估可能会人为地使最佳路径看起来比另一条路径更糟糕，并阻止它被探索。因此，可以提供高估的启发式算法失去了对最优性的任何保证。低估不会带来相同的成本。如果您低估了朝着某个方向前进的成本，最终边权重加起来会大于朝着不同方向前进的成本，因此您也会探索那个方向。唯一的问题是效率损失。
如果您的所有边都有正成本，则负启发式值只能被低估。从理论上讲，低估只会比更精确的估计更糟糕，因为它提供的有关路径潜在成本的信息非常少，并且可能会导致更多节点被扩展。尽管如此，它不会是不可接受的。
然而，这里有一个例子证明负启发式值在理论上有可能打破 A* 的保证最优性：
在此图中，通过节点 A 和 B 显然更好。这将具有 3 的成本，而不是通过节点 C 和 D 的成本 6。但是，C 和 D 的负启发式值D 将导致 A* 在探索节点 A 和 B 之前通过它们到达终点。本质上，启发式函数一直认为这条路径会变得更好，直到为时已晚。在 A* 的大多数实现中，这将返回错误的答案，尽管您可以通过继续探索其他节点直到 f(n) 的最大值大于您找到的路径的成本来纠正这个问题。请注意，此启发式没有任何不可接受或不一致的地方。实际上，我真的很惊讶非否定性没有被更多地提及为 A* 启发式的规则。
当然，这表明您不能随意使用返回负值而不担心后果的启发式方法。尽管是负面的，对于给定问题的给定启发式方法完全有可能会非常好地工作。对于您的特定问题，不太可能发生这样的事情（我发现它对您的问题非常有效，并且仍然想更多地思考为什么会这样）。