一、A*算法概述

如果使一般搜索过程满足如下限制，则它就成为A*算法：
(1)把OPEN表中的节点按估价函数f(n)=g(n)+h(n)的从小到大进行排序；
(2)代价函数g(n)是对g*(n)的估计， g*(n)>0。 g*(n)是从初始节点S0到节点x的最小代价；
(3)启发函数h(n)是h*(n)的下界，即对所有的n均有：h(n)≤h*(n) 。h*(n)是从节点n到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。 通过n的最佳路径：f*(n)=g*(n)+h*(n)最小的路径，即从S出发，通过节点n的，到达目标节点的代价和最小的路径。

路径规划——A*算法

• 欧几里得距离 ( Euclidean distance)也称欧式距离,它是一个通常采用的距离定义,它是在m维空间中两个点之间的真实距离(直线距离)。
• 出租车几何或曼哈顿距离（Manhattan Distance）是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。
• 切比雪夫距离（Chebyshev distance）或是L∞度量，是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。

说明

• A*寻路算法要解决的问题就是在有障碍物的情况下，如何快速找到一条到达目的节点的最短路径。
• 注意：在寻找F值最小的时候可能会出现不止一个节点的情况，此时处于节省寻路时间的考虑，选择最后放入open list的节点。因为最后放入open list的节点是上一个处理节点的邻居节点，从而保证寻路时的连贯性，不会出现在寻路过程中突然跳到另外的地方重新开辟一条新路径。

K短路算法——A算法
A星算法详解
堪称最好最全的A算法详解（译文）***

疑问

• 但如果h(0)=0，则A*算法退化为Dijkstra算法，虽能保证得到最优路径，但算法效率低?
  一点见解：Dijkstra始终找【从起始点到某结点最短的路径】而未考虑到终点的那一段。

A*算法理解及代码实现 ***
A*算法理解及代码实现

• 将九宫格变成线性后，计算初始状态和目标状态的奇偶性是否一致，一致有解，否则无解？

八数码问题是否有解
解释如下：

二、Dijkstra算法和A*算法比较

Dijkstra算法和A*算法总结

1. Dijkstra算法计算源点到其他所有点的最短路径长度，A*关注点到点的最短路径(包括具体路径)。
2. Dijkstra算法建立在较为抽象的图论层面，A*算法可以更轻松地用在诸如游戏地图寻路中。
3. Dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A*算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。
4. 由第一点，当目标点很多时，A*算法会带入大量重复数据和复杂的估价函数，所以如果不要求获得 #具体路径# 而只比较路径长度时，Dijkstra算法会成为更好的选择。

与其他算法的比较
利用A*算法进行路径规划
状态空间搜索策略

三、解决八数码问题

八数码 A算法
八数码问题-A(AStar)算法实现

#结点
class Node:
    def __init__(self,parent,state,Fn,Gn,Hn):
        self.parent = parent
        self.state = state  #字符串
        self.Fn = Fn
        self.Gn = Gn
        self.Hn = Hn

from operator import attrgetter
from Node import *

#A*算法
class AStar_search:
    def __init__(self,originode,targetnode,length):  #length=3...
        self.originode = originode      #结点对象
        self.targetnode = targetnode    #结点对象
        self.length = length            #存N数码边长 目前只适用于八数码
        self.opened = [self.originode]  #存结点对象
        self.closed = [] #存结点对象

    #获得逆序数
    def reversenum(self,node):
        Sum=0
        for i in range(0,9):#range 左闭右开
            if(node.state[i]=='0'):
                continue
            else:
                for j in range(0,i):
                    if(node.state[j]>node.state[i]):
                        Sum+=1
        return Sum

    #Hn计算
    def hn(self,node):
        hn = 0
        for i in range(0,9):    
            if(self.targetnode.state[i] != node.state[i]): 
                hn += 1
        return hn

    #扩展结点
    def Expand(self,node):
        expand = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5],
                3:[0,4,6], 4:[3,1,5,7], 5:[4,2,8],
                6:[3,7],  7:[6,4,8], 8:[7,5]}
        expandnode=[]#结点对象数组/列表
        index0 = node.state.index('0')
        directions = expand[index0]
        j = index0
        for i in directions:
            j = index0
            if (i>j):  #0的位置和此位置可移动的目标位置比较
                i,j = j,i
            new = Node(None,0,0,0,0) #后几项先初始化为0
            new.state = node.state[:i] + node.state[j] + node.state[i+1:j] + node.state[i] + node.state[j+1:]  #字符串的拼接
            expandnode.append(new)
        return expandnode

    #是否在某表里
    def isInTable(self,node,table):   
        global N     #全局修改
        for i in table:
            if i.state == node.state: #用状态判断更稳妥
                N = i
                return True
        return False

    #输出
    def PRINT(self,node):
        result = []
        while node is not None:#根据parent字典中存储的父结点提取路径中的结点  逆序向上找
            current = node.state
            result.append(current)
            node = node.parent
        result.reverse()#逆序
        for i in range(len(result)):
                print("step--" + str(i+ 1))
                print(result[i][:3])
                print(result[i][3:6])
                print(result[i][6:])
                print()
                
    #求最小Fn
    def MIN(self,opened):
        minFn=min(opened,key=attrgetter("Fn")) #在对象数组里 按Fn找到最小的对象
        return minFn

    #A*算法
    def A_star(self):
        if((self.reversenum(self.originode)%2) != (self.reversenum(self.targetnode)%2)):
            print("该目标状态不可达！")
        else:
            self.opened[0].Hn = self.hn(self.opened[0]) #初始节点初始化 一定要改变opened中的值
            self.opened[0].Fn = self.opened[0].Hn + self.opened[0].Gn

            while self.opened:
                current = self.MIN(self.opened)
                self.opened.remove(current)

                if(current.state == self.targetnode.state):
                    break

                expandnode = self.Expand(current)   
                for node in expandnode:
                    Fn = current.Gn + 1 + self.hn(node)

                    if(self.isInTable(node,self.opened)):  #一定要改变opened表中的node 而不是取出来的node 
                        if(Fn < node.Fn):
                            N.Fn = Fn
                            N.parent = current
                    if(self.isInTable(node,self.closed)):
                        if(Fn < node.Fn):
                            N.Fn = Fn
                            N.parent = current
                            self.opened.append(node)
                    if(not self.isInTable(node,self.opened) and not self.isInTable(node,self.closed)):   
                        node.Gn = current.Gn + 1
                        node.Hn = self.hn(node)
                        node.Fn = node.Gn + node.Hn
                        node.parent = current
                        self.opened.append(node)      
                self.closed.append(current)              
            self.PRINT(current)        

代码说明：
其实写完之后还是似懂非懂的样子，看到网上一些代码并没有对已入closed表的节点再处理并重新放回opened表中的部分，也没有搞懂A算法和A*算法的区别。
这一次先到这里，先准备下一场答辩，我还会再回来继续探索的！

四、应用领域

• 经典的路径规划算法
• 自动驾驶领域
• 游戏中的寻路，比如《星际争霸》、《帝国时代》等