最优性剪枝

一句话理解

最优性剪枝：当前估计不可能比已知答案更好，就停。

为什么要学

求最优解的搜索。

讲解

维护当前最优 ans。若乐观估计都赢不了 ans，剪掉。

估价必须乐观，否则会漏更优解。

例子

已走 10 步，就算剩下全走最短也 > ans，不必继续。

常见错误

• 估价不乐观，剪掉真正更好的解。
• ans 初值太紧或太松。