如何定义随机搜索问题的完备性？
我们是否可以将其定义为找到解决方案的概率极限为1的搜索？
Can we just define it to be the search with the probability limit of find a solution to be 1?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
简短的回答：是的
较长的回答：为了声称搜索算法[甚至随机]是“完整的”，您必须证明如果有答案，算法将在有限的时间内找到答案。
这意味着，您必须证明，如果有答案，则无论如何都不可能存在未完成[或以错误答案完成]路径。因此，您需要证明以 1 的概率找到解决方案[完全正确！不是近似！]，以显示随机算法是“完整的”
例如，最陡爬坡 带有人行道 [你可以去具有相同效用值的邻居] - 不完整，因为你可以进入无限循环并且永远找不到任何解决方案。但是，如果将人行道的数量限制为有限数量
K，则它是完整的，因为如果存在局部最小值，算法最终会找到一个，概率为 1。short answer: yes
longer answer: In order to claim a search algorithm [even stochastic] is "complete" you must show that if there is an answer, the algorithm will find an answer, in a finite time.
This means, you must show that if there is an answer, there cannot be, with any probability, a non-finishing [or finishing with wrong answer] path. So, you need to show that a solution will be found with probability 1 [exactly! not approximately!], to show a stochastic algorithm is "complete"
For example, steepest ascent hill climbing with side walks [you can go to a neighbor with the same utility value] - is not complete, since you can enter an infinite loop and never find any solution. However, if you limit the number of side walks to a finite number
K, it is complete, because if there is a local minimum, eventually the algorithm will find one, with probability 1.