我们是否可以将其定义为找到解决方案的概率限制为1的搜索？
最佳答案
简短的回答:是的
更长的答案:为了声称搜索算法 [even stochastic] 是“完整的”，您必须证明如果有答案，该算法将在有限时间内找到答案。 这意味着，您必须表明，如果有答案，则不可能存在未完成的 [或以错误答案完成] 路径。因此，您需要证明找到概率为 1 的解决方案[完全正确!不是大约!]，以显示随机算法是“完整的”
例如，steepest ascent hill climbing人行道[你可以去一个具有相同效用值(value)的邻居] - 不完整，因为你可以进入无限循环并且永远找不到任何解决方案。但是，如果您将人行道的数量限制为有限数量 K，它就是完整的，因为如果存在局部最小值，算法最终会以概率 1 找到一个。
关于algorithm - 如何定义随机搜索问题的完备性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7782309/