爬山法
什么是爬山法?
爬山法是指经过评价当前的问题状态后，限于条件去增加这一状态与目标状态的差异，经过迂回前进，最终达到解决问题的总目标。就如同爬山一样，为了到达山顶，有时不得不先上矮山顶，然后再下来，这样翻越一个个的小山头，直到最终达到山顶。可以说，爬山法是一种"以退为进"的方法，往往具有"退一步进两步"的作用，后退乃是为了更有效地前进。爬山法也叫逐个修改法、瞎子摸象法。
简单地说，爬山法就是按照下述原则进行试探的方法。这就是在每一状态下都选取这样的步骤进行试探：由这个步骤所达到的终结状态是所有可容许步骤所能达到的终结状态中，最接近最终目标的一个。这样的步骤称为最优步骤。按照这样的原则依次选取步骤，顺序试探下去，直到最终目标为止。如果达不到最终目标，可以回过头来，从已经经历过的某一中间状态开始，改用直接效果稍差一点的次优步骤，沿着另一条分支途径再行试探下去。当然，也可以一下子回转到整个问题的起始状态，沿着另一条全新的途径进行试探。到底应当返回到什么状态开始另行试探，这要由解题者根据具体情况作出自己的判断。
爬山法要求人们在推演的每一步上作出局部性的合理选择．为进行试探提供了作出衡量、判别的一种原则，使试探工作能具有更明显的条理性和某种程度上的程序性与可操作性。在问题求解活动中．人们也往往是自觉或不自觉地运用着爬山法的原则。不过，尽管爬山法有着相当广泛的应用，但却并非是总能奏效的，因为它也有着明显的弱点和局限性。
首先，在许多思维课题的求解活动中，我们既无法具体地开列出从某一状态出发的所有容许推演步骤，更难以判定在这些步骤所得出的各种终结状态中哪一个同最终目标最为接近。例如，在求证某一几何命题时，一般情况下，我们并不清楚可以运用哪些几何定理，能够作出哪些辅助图形，更难以从各种推演步骤所可能得出的结果中把最接近于最终目标的结果选取出来。这种状况的存在，给爬山法的运用带来了原则性的困难。
其次，解决问题的有效思路大多是迂回曲折的。“曲径通幽处。禅房花木深”。对于需要充分发挥思维的创造性功能的问题求解来说．几乎总是需要历经曲折才能找到通向目标的路径。在某些情况下，甚至还需要暂时沿着同目标正相背离的途径进行一段路程，才能够达到探隐索幽，揭示事物底蕴，觅得待求结果的目的。与此相反，那些一开始就直接向目标逼近，能够带来明显进展的路径，却有可能把我们引入无法达到目标的死胡同之中。对于不少问题来说，甚至完全有可能“在解题过程的末尾困难成堆”。“这就像有许许多多小路，你可以沿着这些小路爬到很接近顶峰的地方，却只有少数几条路可以直接通到最高峰。所以爬山法(在解题的意义上)虽然能大大缩小尝试范围，却仍然不是解这类问题的好方法。你能用爬山法走完解这类问题的大半路程，却往往在最后时刻功亏一篑。”
应当指出，对于爬山法同推演路径的迂回曲折不相适应的弱点，我们是可以在一定程度上设法加以补救的。只要把目光放远一些，不是只看到当前的一步，而是看到接续下去的两步、三步乃至更多的步数，也就能够跨越局部存在的迂回曲折，看清楚在较大范围内真正能向上攀登的道路。
人们在求解问题时总是要力图达到目标；但经验丰富、眼界开阔的人可以看得更远一点，审度出欲进先退、欲取姑与的曲折关系。虽然在某一步上远离了目标，但在第二步、第三步上却可以前进得更多，使先前的损失得到加倍的补偿；而不是像没有经验的人那样，只能看到眼前的一步。虽然从所采取的那一步来说是前进了。但接着下去却会很快地面对绝壁悬崖，陷入走投无路的困境之中。这就如同下象棋一样．初学的人大多老是盯着对方的棋子，总想多“吃掉”一个，哪怕是“吃掉”一个无足轻重的小卒，也会一阵沾沾自喜．而无力认识这一步着法对以后的着法和整个棋局带来的不良后果。高明的棋手看到的就不止一步。他会对两三步、乃至更多步以后的情况作出判断。如果接下去几步之后确实能够把对方置于死地，即使在要着的一步上会引起车的丢失，也是乐意为之的。至于在思维课题的求解活动中怎样才能看得更远一点，认清真正取得进展的标志，却并不存在普遍有效的标 准与原则，只能主要凭借自己的经验和进行洞察与鉴别的能力来作出判断。
其次这是一种局部的搜索算法:
1).局部搜索算法为什么叫做局部呢??
有些搜索算法它都需要返回从初始状态到目标状态的这条路径作为这个问题的解；而实际中有很多最优化的问题，是不需要知道到达目标的这条路径。也就是说它不关心路径，它只关心状态本身，它需要算法找到一个符合要求的目标状态，那么这个目标状态本身才是问题的解。针对这一类问题我们可以采用局部搜索算法。
2).也就是说这个局部搜索算法不记录它的搜索过程，它只记录一个或多个当前状态，然后通过不断的改进修改当前状态，直到它满足目标约束，也就是说是一个目标状态为止。那么这个目标状态本身返回去作为这个问题的解，那么它叫做局部的原因就是因为它只储存当前状态。那么它并不像前面一样，系统的记录从初始结点到达后续结点、目标节点的路径，并不储存这些东西。它只是在当前状态这个局部领域里记录它的搜索。那么这个是局部搜索算法的思想和它适用的问题。
2.这种算法有一个很大的优点，就是它对存储空间的要求非常的低，它只需要存储当前状态，并不需要把它走过的结点都记录下来。所以它对于现实世界的问题，一般都是无限空间状态的问题。那么它是很有实用性的，也就是说它可以用来解 决一些实际的大问题。
来一个小小的问题
找图中函数在区间[5,8]的最大值
重点思路
爬山算法会收敛到局部最优，解决办法是初始值在定义域上随机取乱数100次，总不可能100次都那么倒霉。
实现
1234567891011121314151617181920212223242526272829 | import numpy as npimport matplotlib.pyplot as pltimport math# 搜索步长DELTA = 0.01# 定义域x从5到8闭区间BOUND = [5,8]# 随机取乱数100次GENERATION = 100def F(x): return math.sin(x*x)+2.0*math.cos(2.0*x)def hillClimbing(x): while F(x+DELTA)>F(x) and x+DELTA<=BOUND[1] and x+DELTA>=BOUND[0]: x = x+DELTA while F(x-DELTA)>F(x) and x-DELTA<=BOUND[1] and x-DELTA>=BOUND[0]: x = x-DELTA return x,F(x)def findMax(): highest = [0,-1000] for i in range(GENERATION): x = np.random.rand()*(BOUND[1]-BOUND[0])+BOUND[0] currentValue = hillClimbing(x) print('current value is :',currentValue) if currentValue[1] > highest[1]: highest[:] = currentValue return highest[x,y] = findMax()print('highest point is x :{},y:{}'.format(x,y)) |
|---|
行结果：
接着再写一个游戏:
import random
# 显示数字拼图
def disp(s, d):
# s和d是两个数字字符串，把0换成空格，把数字摆放到指定位置
s = ''.join(s).replace('0', ' ')
d = ''.join(d).replace('0', ' ')
print('''
+---+---+---+ +---+---+---+
| {0[0]} | {0[1]} | {0[2]} | | {1[0]} | {1[1]} | {1[2]} |
|---+---+---| |---+---+---|
| {0[3]} | {0[4]} | {0[5]} | ==> | {1[3]} | {1[4]} | {1[5]} |
|---+---+---| |---+---+---|
| {0[6]} | {0[7]} | {0[8]} | | {1[6]} | {1[7]} | {1[8]} |
|---+---+---| |---+---+---|
'''.format(s, d))
# 移动数字
def move(s, numstr):
if (numstr not in "12345678") or (not numstr):
return
t1 = s.index('0')
t2 = s.index(numstr)
# 字符在字符串中的位置除3的商对应游戏图中的行下标
# 除3的余数对应游戏图中的列下标
t = zip(divmod(t1, 3), divmod(t2, 3))
t = ''.join([str(abs(i-j)) for i, j in t])
# 如果输入的数字与空格相邻则移动
if t in ('01', '10'):
s[t1], s[t2] = s[t2], s[t1]
# 获取空格周边可移动数字
def getMoveable(s):
# 空格位置的行、列坐标
p, q = divmod(s.index('0'), 3)
# 空格上下的位置坐标
ls = [(p, i) for i in (q+1, q-1) if i in range(3)]
# 空给左右的位置坐标
ls += [(i, q) for i in (p+1, p-1) if i in range(3)]
return ls
# 爬山算法状态计算函数，从当前状态s到终态d所需要的总步数
def getInstance(s, d):
# 依次计算s和d中相同数字的距离，并求所有距离之和
sumi = 0
for n in '12345678':
t1 = divmod(s.index(n), 3)
t2 = divmod(d.index(n), 3)
sumi += abs(t1[0]-t2[0]) + abs(t1[1]-t2[1])
return sumi
# 让机器根据与目标各数字差距之和的策略选定一个移动数字
def choiceNum(s, moveable, d):
tmp = [100, '0']
for i in moveable:
s1 = s[::]
s1[s1.index('0')], s1[s1.index(i)] = i, '0'
getI = getInstance(s1, d)
if getI < tmp[0]:
tmp = getI, i
elif getI == tmp[0]:
tmp = getI, random.choice([i, tmp[1]])
return tmp[1]
# 打乱数字拼图顺序，以得到初始状态
def shufflemove(d, times):
s2 = d[::]
mov = '0'
for i in range(times):
mov1 = mov
mov = [s2[x[0]*3+x[1]] for x in getMoveable(s2)]
if mov1 in mov:
mov.remove(mov1)
mov = random.choice(mov)
move(s2, mov)
return s2
# 做题,当who为computer时为计算机解题
# 当who为human，即非computer时，人工解题
def do(s, d, who):
s1 = s[::]
num = ''
bushu = 0
while True:
if who != 'computer':
disp(s1, d)
# 已成功、步数太大或人工放弃时返回
if s1 == d or bushu >= 1000 or num == '0':
return bushu
# 确定可输入的数字
n_of_m = [s1[x[0]*3+x[1]] for x in getMoveable(s1)]
if who == 'computer':
# 机器答题不允许后退
if num in n_of_m:
n_of_m.remove(num)
num = choiceNum(s, n_of_m, d)
else:
# 人工答题允许后退
prompt = '第{0}步{1}(输入0退出)=>'.format(bushu, n_of_m)
num = input(prompt)[0]
# 输入0步数设为999，视为主动放弃并退出
if num == '0':
bushu = 999
# 移动数字
move(s1, num)
bushu += 1
# 主程序开始
print('-'*34)
print('拼图游戏'.center(34, '*'))
print('''
**玩法：左边的图通过移动空格相邻的数字到
空格处，最终得到右边的图，游戏即完成。只
要输入空格相邻的数字，该数字即被移到空格
处。=>左边的数字为你已经移动的步数及你可
移动的数字。完成任务的步数越少，你的游戏
成绩越高。祝你幸运！
''')
print('-'*34)
# 为简化，设定固定数字目标，其中0显示为空方块
d = list('123804765')
# 为简化，让机器从目标开始随机逆移动,先只移动6步
# 也可以设置难度，移动步数越多，恢复越难。
s = shufflemove(d, 6)
# 先让计算机用简易爬山算法去解题，由于爬山算法本身的原因，不一定能得到最优解
cpstep = do(s, d, 'computer')
# 显示开始与结束状态及机器解题情况
disp(s, d)
print('这个题目机器用了{0}步! '.format(cpstep))
if cpstep > 1000:
print("机器用了1000步还没解出，看你的了！")
# 用于计人工移动的步数
bushu = 0
# 人工解题开始
hmstep = do(s, d, 'human')
# 显示游戏结果
if hmstep < cpstep:
print("你胜利，真了不起！")
elif hmstep == cpstep:
print("你与机器持平局，加油!")
else:
print("哈，你输给了机器，这可是用爬山算法哦!")
nm的,写python最大的感受就是好想买个游标卡尺,气死我了