A*算法走迷宫

A*算法是一种启发式搜索算法。与常见的深度优先、广度优先等算法相区别的是,A*算法可以为下一次搜索提供一个启发式信息,来让每一次搜索步都在朝着“很可能”的方向前进。这样就明显比其他无方向的搜索算法优秀得多!

A*算法考虑到了从该位置到终点的估价信息和从起点到当前位置的代价信息。将这两者作为启发式信息。也就是说,每一个不同的搜索状态,都会有一个由启发式信息产生的估价函数值。在搜索过程中,我们可以优先搜索股价函数值低的状态空间(因为它们更倾向于快速走到终点)。

A*算法与其他遍历搜索算法类似,唯一的区别在于,A*算法每次会将接下来的所有搜索步排序,寻找一个估价函数值最低的情况进行搜索。其基本结构如下:

def 查找表=[]  
查找表.push(起点状态)
while 查找表不为空:  
    当前状态=查找表[1] # 从查找表中取出第一个状态
    if 当前状态.is_arrive is True:
        return 查找到可行解
    从当前状态扩展出所有下一步的可行状态 -> 添加到查找表中
    sort(查找表, 依据=估价函数值) # 如果是非启发式搜索,则不需要这一步
return 无解  

上面这段代码中,排序的依据是估价函数值,而这个估价函数的选取将会直接影响到查找的速度(不会影响到准确性,因为A*算法也是一种穷举搜索算法,只不过搜索得有方向)。估价函数S=H+G,其中H为从起点到当前位置的代价,G为从当前位置到目标位置的预测代价。而G是很难知道的,在这里我们使用所谓的“曼哈顿距离”————当前位置到终点的横纵坐标距离和并且乘10倍。

下面是用Python实现的A*算法迷宫搜索,是这次算法分析与设计的实验作业:

# -*- coding:utf8
__author__ = 'shibotian'  
import copy

class Map:  
    """
    用来存储图的类
    """
    def __init__(self, param):
        if isinstance(param, str):  # 从文件中读取迷宫
            filename = param
            with open(filename) as infile:
                lines = infile.readlines()

                # 去掉换行符
                # for i, line in zip(range(len(lines)), lines):
                for i, line in enumerate(lines):
                    lines[i] = line.strip('\n')

                self.data = [[lines[i][j] for j in range(len(lines[0]))]for i in range(len(lines))]  # 复制到data中
                self.dim = (len(lines), len(lines[0]))  # 迷宫维度
                self.current_position = [0, 0]  # 当前位置
                self.data[0][0] = '+'  # 设置初始位置已走
                self.h_value = 0

    def __str__(self):
        string = ''
        for line in self.data:
            for word in line:
                string += str(word)
            string += '\n'
            pass
        return string

    def move_up(self):
        copy_map = copy.deepcopy(self)
        copy_map.current_position[0] -= 1
        if copy_map.current_position[0] < 0:
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '0':
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '+':
            return None
        copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] = '+'
        copy_map.h_value += 1
        return copy_map

    def move_down(self):
        copy_map = copy.deepcopy(self)
        copy_map.current_position[0] += 1
        if copy_map.current_position[0] >= copy_map.dim[0]:
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '0':
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '+':
            return None
        copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] = '+'
        copy_map.h_value += 1
        return copy_map

    def move_left(self):
        copy_map = copy.deepcopy(self)
        copy_map.current_position[1] -= 1
        if copy_map.current_position[1] < 0:
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '0':
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '+':
            return None
        copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] = '+'
        copy_map.h_value += 1
        return copy_map

    def move_right(self):
        copy_map = copy.deepcopy(self)
        copy_map.current_position[1] += 1
        if copy_map.current_position[1] >= copy_map.dim[1]:
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '0':
            return None
        if copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] == '+':
            return None
        copy_map.data[copy_map.current_position[0]][copy_map.current_position[1]] = '+'
        copy_map.h_value += 1
        return copy_map

    # 估计值
    def evaluate(self):
        return (self.h() + self.g())
        pass

    def h(self):
        return self.h_value

    def g(self):  # 此处采用曼哈顿距离*10
        return ((self.dim[0] - self.current_position[0]) + (self.dim[1] - self.current_position[1])) * 10

    # 判断是否到达终点
    def is_arrive(self):
        return True if (self.current_position[0]+1, self.current_position[1]+1) == self.dim else False

if __name__ == '__main__':  
    in_map = Map("maze5.data")
    print "The maze is"
    print in_map
    array = [in_map]
    while len(array) is not 0:
        # 取第一个节点
        current_map = array.pop(0)

        # 判断是否已经到达终点
        if current_map.is_arrive() is True:
            print "Final!"
            print current_map
            exit()

        # 如果还没到终点则进行扩展
        up_map = current_map.move_up()
        down_map = current_map.move_down()
        left_map = current_map.move_left()
        right_map = current_map.move_right()
        if up_map is not None:
            array.insert(0, up_map)
        if down_map is not None:
            array.insert(0, down_map)
        if left_map is not None:
            array.insert(0, left_map)
        if right_map is not None:
            array.insert(0, right_map)

        # 按照估价值从小到大排序
        array = sorted(array, cmp=lambda x, y: cmp(x.evaluate(), y.evaluate()))
        pass

    # 找不到
    print "Can not find path"
    pass

Friskit

继续阅读此作者的更多文章