什么是爬山算法
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/27 16:15:31
什么是爬山算法
什么是爬山算法
什么是爬山算法
给出了一种求解整数背包问题的爬山解法,并对该算法的计算复杂度及最坏情形进行了理论分析.通过与经典的求解背包问题方法的对比研究,给出了该算法的适用范围并展示其优越性.数值实验表明,该算法简便易行,在其适用范围内具有计算复杂度低,近优程度高等优点.
我在百度上找的！～～
简介
爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 属于人工智能算法的一种。
算法：
function HILL-CLIMBING(problem) returns a state that is a local maximum
inputs: problem, a prob...
全部展开
我在百度上找的！～～
简介
爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 属于人工智能算法的一种。
算法：
function HILL-CLIMBING(problem) returns a state that is a local maximum
inputs: problem, a problem
local variables: current, a node
neighbor, a node
current <- MAKE-NODE(INITIAL-STATE[problem])
loop do
neighbor <- a highest-valued successor of current
if VALUE[neighbor]<= VALUE[current] then return STATE[current]
current <- neighbor
算法解释：
从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。
算法优缺点
优点
避免遍历，通过启发选择部分节点，从而达到提高效率的目的。
缺点
因为不是全面搜索，所以结果可能不是最佳。
爬山算法一般存在以下问题：
1）、局部最大：某个节点比周围任何一个邻居都高，但是它却不是整个问题的最高点。
2）、高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。
3）、山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。
其他相关算法
stochastic hill climbing
First-choice hill climbing
Ramdom-restart hill climbing
Simulated annealing search
Local beam search
如果您认为本词条还有待完善，需要补充新内容或修改错误内容，请 编辑词条
收起