高级搜索之爬山法（Hill Climbing）_hillclimbing算法

一、通俗理解

        爬山的目标是朝最高的方向移动，而当爬山者位于分岔路口的时候，介于视野受限无法知道哪条路才是通往最高峰，但是我们可以判断每条路的陡峭程度来选择路径，即保证至少这一段路是爬得最高的，爬山者会遵循这个原则一直爬，直到一个山峰即没有往上只有往下的路停止

二、性质

• 局限性：采用贪婪局部搜索，每次都选择当前邻近状态中能够最大化目标函数值的状态，而不考虑长远的影响
• 空间复杂度小：只需记录当前状态和其每个后继状态的目标函数值
• 时间复杂度相对小：在很大的状态空间内能很快朝着解的方向进展

三、不具有完备性的原因

• 山肩：比它相邻的每个地方都高，但是比最高峰要低-->爬山法陷入局部最优解
• 山脊：一连串的局部最优值-->爬山法陷入死循环
• 平原：领域的目标函数值几乎一样-->爬山法效率很低或直接失效

四、算法流程

        比较简单， 每一次都从当前解的领域解中找到目标函数值最大的解作为候选解更新，一旦找到最优解则退出，或者到达最大迭代次数也退出

五、八皇后问题

描述：将8个皇后放置在一个8×8的棋盘上，使得不存在两个皇后位于同行、同列和同对角线

import random
 
#随机生成一个棋盘
def initial_state(board_size):
    state = random.sample(range(board_size),board_size)
    return state
 
 
#统计冲突函数：输入皇后位置列表，返回当前位置下的冲突数量
def count_conflicts(state):
    conflicts = 0
    size = len(state)
    for i in range(0,size-1):
        for j in range(i+1,size):
            diag1 = (state[i] - i) == (state[j] - j)
            diag2 = (state[i] + i) == (state[j] + j)
            if state[i] == state[j] or diag1 or diag2:
                conflicts += 1
    return conflicts
 
#皇后位置改变函数：输入新位置，返回新列表
def move_queen(new_col,row,state):
    new_state = list(state)
    new_state[row] = new_col
    return new_state
 
#爬山法
def climb_hills(cur_state,max_iterations=1000):
    iterations = 0
    size = len(cur_state)
    cur_conflicts = count_conflicts(cur_state)
    # 不断更新当前状态为后继最佳状态，直到冲突数为0或到达最大迭代数
    while cur_conflicts != 0 and iterations < max_iterations:
        # 以行序为主序即从上往下遍历，将每行的皇后的当前列改变为最佳列
        for row in range(size):                                     
            cur_col = cur_state[row]
            best_col = cur_state[row]
            best_conflicts = cur_conflicts
            # 找到当前行的最佳列
            for new_col in range(size):                             
                if new_col != cur_col:
                    #横移皇后得到的新状态和新冲突数
                    new_state = move_queen(new_col,row,cur_state)   
                    new_conflicts = count_conflicts(new_state)      
                    #当且仅当新冲突数＜旧冲突数时，才更新
                    if new_conflicts < best_conflicts:              
                        best_col = new_col
                        best_conflicts = new_conflicts
            cur_state[row] = best_col
            cur_conflicts = best_conflicts
        iterations += 1
    return cur_state
 
 
state = initial_state(8)
print('起始棋盘：', state)
result = climb_hills(state)
if count_conflicts(result) == 0:
    print('成功：', result)
else:
    print('失败：', result)
 

六、评测

1. 从一个随机生成的八皇后问题的状态开始，最陡上升的爬山法86％的情况下会被卡住，只有14%的问题实例能求解。
2. 这个算法速度很快，成功找到最优解的平均步数是4步，被卡住的平均步数是3步，但这对于包含88=16,777,216个状态的状态空间已经是不错的结果