Admissible Heuristic

释义 Definition

在搜索算法（尤其是 A* 搜索）中，“可采纳启发式函数”指永不高估从当前状态到目标状态的真实最小代价的启发式估计函数，即对真实代价给出一个下界（lower bound）。使用可采纳启发式通常能保证 A* 找到最优解（若其他条件满足）。此外该术语在某些语境下也可指“可接受/可允许的启发式”，但最常见的是上述 AI 搜索含义。

发音 Pronunciation (IPA)

/ədˈmɪsəbəl hjuːˈrɪstɪk/

例句 Examples

A* search requires an admissible heuristic to guarantee an optimal path.
A* 搜索需要一个可采纳启发式函数来保证得到最优路径。

Because the heuristic is admissible, the algorithm never overestimates remaining cost, so the first solution found with the lowest f-score is optimal.
由于该启发式函数是可采纳的，算法不会高估剩余代价，因此以最小 f 值找到的第一个解是最优解。

词源 Etymology

admissible 来自拉丁语 admittere（意为“允许进入、准许”），在数学与计算机科学中常引申为“满足条件而可被接受的”。heuristic 来自希腊语 heuriskein（意为“发现、找到”），指用来“帮助发现/求解”的经验性规则或估计方法。合在一起，“admissible heuristic”就是“满足可接受条件（不高估）的启发式估计”。

相关词 Related Words

• A*
• Heuristic
• Consistent
• Optimal
• Optimality
• Lower Bound
• Search
• Graph

文学与经典著作 Literary Works

• Artificial Intelligence: A Modern Approach（Russell & Norvig）——在 A* 搜索章节中讨论可采纳启发式与最优性保证。
• Hart, Nilsson, Raphael (1968), “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”——提出并形式化讨论 A* 及相关启发式条件（包括可采纳性）。
• Pearl (1984), Heuristics: Intelligent Search Strategies for Computer Problem Solving——系统阐述启发式搜索策略与理论基础，涉及可采纳启发式的作用。