可容许启发式函数

Definition

在路径查找和搜索问题中，可容许启发式函数提供了到达目标节点实际成本的下界。通过保证估计成本始终小于或等于实际成本，它确保了搜索算法（如A*）能找到最优解。

Summary

搜索算法中的一种启发式函数，它从不高估到达目标的真实成本，从而保证最优性。

Key Concepts

• 下界
• 最优性保证
• A*搜索
• 成本估计

Use Cases

• GPS导航路线规划
• 解谜游戏（如八数码问题）
• 障碍物丰富环境中的机器人运动规划

Related Terms

• consistent heuristic (一致启发式函数)
• A* algorithm (A*算法)
• search optimization (搜索优化)
• pathfinding (路径查找)