A*算法是对Best-First算法的一种改进，核心思想是广搜，利用open表和close表对节点进行剪枝，同时利用启发式测度来选择最优的扩展节点。

A*算法在满足一定条件下找到的解必然是最优解。

最短路得到最优解条件：A*算法的启发式函数h如果小于等于真实值n的话，那么算法是能得到最优解的，若h大于等于真实值n，那么就不能保证得到最优解。

主要数据结构：

opened_table：采用优先队列实现的小顶堆，用于存放待扩展结点，同时利用F值作为排序指标；
closed_table：采用set（红黑树）实现，便于快速查找格是否存在于closed_table中；
启发式函数：采用曼哈顿距离作为启发式函数，即当前节点与终点的水平、竖直相差方格的数目之和；

问题描述：

精灵王子Haposola一大早从城堡中起床，要去沙漠中河流消失的地方寻找失落的宝藏。长路漫漫，处处险恶，精灵王子要尽快到达目标地点。以下图为输入，寻找地图上给出的起点和终点间的最小代价路径。规则和条件如下。
(1) 每一步都落在方格中，而不是横竖线的交叉点。
(2) 灰色格子表示障碍，无法通行。
(3) 在每个格子处，若无障碍，下一步可以达到八个相邻的格子，并且只可以到达无障碍的相邻格子。其中，向上、下、左、右四个方向移动的代价为1，向四个斜角方向移动的代价为√2。
(4) 在一些特殊格子上行走要花费额外的地形代价。比如，黄色格子代表沙漠， 经过它的代价为4；蓝色格子代表溪流，经过它的代价为2；白色格子为普通地形，经过它的代价为0。
(5) 经过一条路径总的代价为移动代价+地形代价。其中移动代价是路径上所做的所有移动的代价的总和；地形代价为路径上除起点外所有格子的地形代价的总和。

地图

启发式函数：

H = G * 5 + F
其中G代表已走过的真实距离；F代表当前点到目标点的曼哈顿距离；

为什么要给G乘上5？

因为任务的要求是要走过路程最短，因此我们的启发式测度更加的看重实际走过的距离，而不是通过曼哈顿距离估计的路程。
所以给G赋予更大的权值，保证我们得到的解是最优解，即最短路程。【就是一个加权的思路】

地图处理：

值得一提的是，由于我们的地图是图片的形式给出的，那么我们需要将图片转化为数组读入程序。此处借助Python的第三方库PIL实现地图输入的采样、以及实验结果的生成。
通过均匀采样将地图图片输入转化为字符数组的函数。
同时对于预测得到的路径，我们也需要根据我们的结果，再生成结果地图，详见代码。

算法步骤：

1.  首先将给定图2输入程序；
2.  通过均匀采样，将其转化为字符数组，y代表沙漠，g代表障碍，w代表普通道路，b代表溪流；
3.  输入起点和终点，同时将起点、终点、字符数组存储的地图输入算法；
4.  把起始格添加到opened表；
5.  如果开启列表不为空，重复如下的工作：
    a)  寻找开启列表中F值最低的格子，作为当前格；
        对于8个方向，寻找当前格的活节点：
          i.    如果当前点是终点，则返回回溯的路径；
          ii.   如果活节点超出地图边界，则跳过；
          iii.  如果活节点位于closed表中，则跳过；
          iv.   如果它不在开opened表中，则计算其F,G,H值，然后添加进opened表；
          v.    如果它在opened表中，则判断opened表中格的G值是否大于当前活节点，如果大于，则说明当前活节点更优，代价更小，那么将opened表中这一格的父节点改成当前格，同时重新计算G,F值；
    b)  把当前格加入closed表；
6.  将路径结果与地图生成图片，方格像素为30*30px，边界像素为1px；

主要代码：

地图方格定义：

class AreaBlock(object):
    def __init__(self, father, kind, g, row, col):
        self.father = father
        self.kind = kind
        self.coordinate_row = row
        self.coordinate_col = col
        self.g = g
        self.f = 0.0

    def get_coordinate(self):
        return self.coordinate_row, self.coordinate_col

    def __lt__(self, other):
        """
        operator <
        :param other:
        :return:
        """
        return self.f < other.f

地图处理：

def process_map():
    """
    将图片变化为字符矩阵
    :return:
    """
    game_map = [[0] * 41]
    im = Image.open('map.png')
    pix = im.load()
    width = im.size[0]
    height = im.size[1]
    """
    取样点坐标
    """
    start_x = int(math.floor(width / 40)) - 10
    x_step = int(round(width / 40))
    start_y = int(math.floor(height / 20)) - 10
    y_step = int(round(height / 20))
    for i in range(20):
        row = [0]
        y = start_y + i * y_step
        for j in range(40):
            x = start_x + j * x_step
            if pix[x, y] == GRAY:
                row.append('g')
            elif pix[x, y] == BLUE:
                row.append('b')
            elif pix[x, y] == YELLOW:
                row.append('y')
            elif pix[x, y] == WHITE:
                row.append('w')
            else:
                print("error")
        game_map.append(row)
    return game_map

A*寻路：

def search(game_map, start_pos, end_pos):
    """
    寻路算法
    :param game_map:
    :param start_pos:
    :param end_pos:
    :return:
    """
    # 确定边界
    max_row = len(game_map) - 1
    max_col = len(game_map[0]) - 1
    # 创建open表, close表
    opened_table = PriorityQueue()
    closed_table = set()
    # 初始化open表
    opened_table.put(start_pos)
    while not opened_table.empty():
        current_area_block = opened_table.get()
        for direct in direction:
            col_index = current_area_block.coordinate_col + direct[0]
            row_index = current_area_block.coordinate_row + direct[1]
            # 边界检测, 如果它不可通过或者已经在关闭列表中, 跳过
            if (row_index, col_index) in closed_table or bound(row_index, col_index, max_row=max_row, max_col=max_col):
                continue
            if game_map[row_index][col_index] == 'g':
                continue
            # 计算移动代价
            move_cost = 1
            if math.fabs(direct[0]) == 1 and math.fabs(direct[1]) == 1:
                move_cost *= math.sqrt(2)
            # 计算地形代价
            land_cost = get_cost(game_map[row_index][col_index])
            # 创建block
            next_area = AreaBlock(father=current_area_block,
                                  kind=game_map[row_index][col_index],
                                  g=current_area_block.g + move_cost + land_cost,  # 地形代价 + 移动代价
                                  row=row_index,
                                  col=col_index)
            # 如果当前节点是目标节点，则找到路径
            if col_index == end_pos.coordinate_col and row_index == end_pos.coordinate_row:
                # 向父节点开始回溯，输出路径
                return find_path(next_area)
            # 检查该点是否在open表中
            result = None
            tmp_queue = []
            while not opened_table.empty():
                tmp_block = opened_table.get()
                if tmp_block.get_coordinate() == next_area.get_coordinate():
                    result = tmp_block
                    break
                tmp_queue.append(tmp_block)
            while len(tmp_queue) != 0:
                opened_table.put(tmp_queue.pop())
            opened_table.task_done()
            # 检查该点是否在open表中, 如果不在则加入, 同时计算启发值 F = G + H
            next_area.f = heuristic(next_area, end_pos)
            if result is None:
                opened_table.put(next_area)
            else:
                """
                用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。
                """
                if next_area.g < result.g:
                    opened_table.put(next_area)
                else:
                    opened_table.put(result)
        closed_table.add(current_area_block.get_coordinate())
    return None

采用栈实现路径的回溯：

def find_path(target_area_block):
    """
    回溯寻找路径
    :type target_area_block: AreaBlock
    :param target_area_block: 
    :return: 
    """
    print(target_area_block.g)
    # 用栈存储路径
    stack = [target_area_block.get_coordinate()]
    father_area_block = target_area_block.father
    while father_area_block is not None:
        stack.append(father_area_block.get_coordinate())
        father_area_block = father_area_block.father
    return stack

根据回溯的路径生成结果图片：

def save_result(game_map, path):
    """
    将结果保存为图片
    :param game_map:
    :param path:
    :return:
    """
    pix = convert_array_to_pixel(game_map, path)
    array = np.asarray(pix, dtype=np.uint8)
    image = Image.fromarray(array, 'RGBA')
    image.save("result.png")

def convert_array_to_pixel(arr, path):
    """
    将字符数组转化为像素
    :param arr:
    :param path:
    :return:
    """
    width = 20
    height = 20
    pixels = []
    for i in range(1, len(arr)):
        line = []
        for j in range(1, len(arr[i])):
            if arr[i][j] == 'g':
                line.append(GRAY)
            elif arr[i][j] == 'b':
                line.append(BLUE)
            elif arr[i][j] == 'y':
                line.append(YELLOW)
            elif arr[i][j] == 'w':
                line.append(WHITE)
        pixels.append(line)
    # 绘制路径
    for point in path:
        x, y = point
        pixels[x - 1][y - 1] = RED
    # 处理分辨率，放大
    result = [[BORDER] * ((len(pixels[0])) * width + (len(pixels[0]) + 1))]
    for i in range(len(pixels)):
        line = [BORDER]
        for j in range(len(pixels[i])):
            line.extend([pixels[i][j]] * width)
            line.append(BORDER)
        for j in range(height):
            result.append(line)
        result.append([BORDER] * len(line))
    del pixels
    return result

实验结果：

当起点为(11, 5)时，终点为(1, 36)，cost=67.0416结果为(红色为路径)：

当起点为(5, 3)时，终点为(20, 9)，cost=22.0711结果为(红色为路径)：

当起点为(20, 1)时，终点为(1, 15)，cost=27.7279结果为(红色为路径)：

总结

本次实验为了实现可视化，使用了python的第三方库Pillow，该库支持读取图片，并转化为数组的形式存储，每个点为RGBA的颜色值。考虑到给定的图片是等间隔的正方形组成，因此想到了利用等间隔采样来提取每个方格的颜色值，从而判定区域类型。

从我犯的错误中也可以总结出，A算法未必会得到最优解，只有在启发式函数满足一定条件的情况下，得到的解才满足最优解，否则只能得到可行解。由于A算法需要频繁查找活结点是否存在于closed表中，于是利用python封装好的set数据结构进行closed表的存储，set是使用红黑树实现的，因此查询速度很快；由于每次从opened表中读取的是代价最小的结点，因此采用PriorityQueue优先队列来维护一个小顶堆，每次从堆顶取得具有最小值的结点，对其进行扩展。

A算法的启发式函数得到的估计值h是不准确的，设当前区域到达目标区域的代价为n，那么h≤n，这种情况下，导致A算法搜索的区域数多，搜索范围大，效率低。同时，A*算法的启发式函数h如果小于等于真实值n的话，那么算法是能得到最优解的，若h大于等于真实值n，那么就不能保证得到最优解。

在生成路径结果的时候，考虑到了pillow的原理，读取图片-> RGBA字典 ->字符数组的流程，于是猜想通过逆过程来生成图片，首先将路径叠加到字符数组，然后再通过字符数组转为为RGBA的数组，于是来生成实验结果。

Github源码