AI中的搜索算法 | The War Of Mine

本文主要整理下AI中最常用搜索算法, 包括BFS, A*

本文的图就是用这个开源项目生成的

BFS

伪代码

//引入一个集合，用来保存已经走过的路口
closed = {}
q = newqueue
q.enqueue(newpath(start))
while q is not empty
    p = q.dequeue
    //如果下面closed集合中包含了路径p的最后一个路口
    //p.last则忽略
    if closed contains p.last  
        continue
    //如果路径p的最后一个路口即是目的地，则直接返回p
    if p.last == destination 
        return p
    //否则将该点p.last加入到closed集合中
    closed.add(p.last)
    //把点p.last相邻的点加入到队列中
    foreach n in p.last.neighbours 
        q.enqueue(p.continuepath(n))
//找不到合适的路
return null

A*

相比BFS, 相当于队列需要考虑该状态离出发点和到终点的一个目标函数, 认为这个目标函数越高, 就优先从队列中推出, 由于不知道离终点多远, 一般近似用曼哈顿距离.

伪代码如下

//引入一个集合，用来保存已经走过的路口
closed = {}
q = newqueue;
//q为优先队列，记录路径的消耗以及路径，起始点消耗为0
q.enqueue(0, newpath(start))
while q is not empty
    //优先队列弹出消耗最小的路径
    p = q.dequeueCheapest
    if closed contains p.last 
        continue;
    if p.last == destination 
        return p
    closed.add(p.last)
    foreach n in p.last.neighbours 
        //获得新的路径
        newpath2 = p.continuepath(n)
        //将新路径的总消耗（G+H)，和新路径分别入队
        q.enqueue(newpath.G + estimateCost(n, destination), newpath2)

return null

这里估计可以用曼哈顿距离(所以是启发式算法)

将A*具体应用, 可以用到贪吃蛇, 8-puzzle问题.

具体可以用BFS, DDFS, A*(不同的启发算法可以由不同的结果, 一般用曼哈顿距离).

Reference

AI for 8 puzzles对该问题的求解

good article

A*的一个C++实现

A*改进

Minmax with Alpha Beta Pruning

所谓minmax, 包含两个步骤, 当我们构建好了目标函数(比如下棋问题, 赢了就算+10分, 输了就算-10分), 对我们自己来说肯定是选择使得目标函数最大的步骤, 这就是max步骤.但是当你下完了之后, 对手会朝着使得同一目标函数最小的方向走(也就是和你相反的反向), 这就是min步骤. 实际上可以看到是递归穷举的, 可以引入alpha-beta剪枝来减少计算量.

def minmax(board, depth):
    global choice
    result = check_win_game(board)
    if result != CONT_GAME:
        return unit_score(result, depth)

    depth += 1
    scores = []
    steps = []

    for step in get_available_step(board):
        score = minmax(update_state(board,step,depth),depth)
        scores.append(score)
        steps.append(step)

    if depth % 2 == 1:
        max_value_index = scores.index(max(scores))
        choice = steps[max_value_index]
        return max(scores)
    else:
        min_value_index = scores.index(min(scores))
        choice = steps[min_value_index]
        return min(scores)