请输入您要查询的百科知识:

 

词条 爬山算法
释义

简介

爬山算法是一种局部择优的方法,采用启发式方法,是对深度优先搜索的一种改进,它利用反馈信息帮助生成解的决策。 属于人工智能算法的一种。

算法:

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

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/15 23:35:02