爬山法实践

人工智能将搜索定义为：从初态开始，找到一系列步骤，通过一组中间的搜索状态，到达预定义的终态。

以9宫格数字滑块拼图为例：

• 运算符就是每次可选的动作，即上下左右移动滑块；

• 评估函数，就是离完成目标还有多少距离；

• 终止标准，接近目标到一定程度，或者完成目标，或者行动步数、时间超过一定程度。

• 初始评估函数1，简单为离终态的累计滑动数量之和。在例子中，需要219步才能完成。

• 评估函数2，增加了数字加权，权值大优先滑动，优化后需要34步完成。

import copy;

#finalStatus = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
finalStatus = [[1, 2, 3], [8, 0 , 4], [7, 6, 5]]

def distance1(number, line, index):
    distancef = 0
    for linef in range(len(finalStatus)):
        for indexf in range(len(finalStatus[linef])):
            numberf = finalStatus[linef][indexf]
            if numberf == number:
                distancef = abs(line - linef) + abs(index - indexf)
                break
        if distancef > 0:
            break
    return distancef

def judgement1(status):
    length = 0
    for line in range(len(status)):
        for index in range(len(status[line])):
            number = status[line][index]
            if number != 0 and finalStatus[line][index] != number:
                length = length + distance1(number, line, index)
    return length


def distance2(number, line, index):
    distancef = 0
    for linef in range(len(finalStatus)):
        for indexf in range(len(finalStatus[linef])):
            numberf = finalStatus[linef][indexf]
            if numberf == number:
                if number == 1:
                    distancef = (abs(line - linef) + abs(index - indexf)) * 10
                elif number == 2 or number == 3:
                    distancef = (abs(line - linef) + abs(index - indexf)) * 5
                elif number == 4 or number == 5:
                    distancef = (abs(line - linef) + abs(index - indexf)) * 2
                else:
                    distancef = abs(line - linef) + abs(index - indexf)
                break
        if distancef > 0:
            break
    return distancef

def judgement2(status):
    length = 0
    for line in range(len(status)):
        for index in range(len(status[line])):
            number = status[line][index]
            if number != 0 and finalStatus[line][index] != number:
                length = length + distance2(number, line, index)
    return length



def new_status_from(status):
    status_list = []
    for line in range(len(status)):
        for index in range(len(status[line])):
            number = status[line][index]
            if number == 0:
                if line != 0:
                    status_t = copy.deepcopy(status)
                    status_t[line][index] = status[line - 1][index]
                    status_t[line - 1][index] = 0
                    status_list.append(status_t)
                if line != 2:
                    status_t = copy.deepcopy(status)
                    status_t[line][index] = status[line + 1][index]
                    status_t[line + 1][index] = 0
                    status_list.append(status_t)
                if index != 0:
                    status_t = copy.deepcopy(status)
                    status_t[line][index] = status[line][index - 1]
                    status_t[line][index - 1] = 0
                    status_list.append(status_t)
                if index != 2:
                    status_t = copy.deepcopy(status)
                    status_t[line][index] = status[line][index + 1]
                    status_t[line][index + 1] = 0
                    status_list.append(status_t)
                break
    return status_list


listTemp = []
listSeen = []

def is_new_move(status):
    if status in listSeen:
        return False
    else:
        return True


#beginStatus = [[4, 3, 2], [1, 6, 5], [8, 0, 7]]
beginStatus = [[0, 2, 1], [6, 7, 4], [3, 8, 5]]

listTemp.append(beginStatus)
while len(listTemp) > 0:
    print len(listSeen)
    status0 = listTemp[0]
    print status0[0]
    print status0[1]
    print status0[2]
    length = judgement1(status0)
    print length
    print '----------'
    if length <= 0:
        break
    else:
        listSeen.append(status0)
        listTemp.pop(0)
        status_list = new_status_from(status0)
        status_list = filter(is_new_move, status_list)
        for status in status_list:
            listTemp.append(status)
        listTemp = sorted(listTemp, key=lambda status: judgement2(status), reverse=False)