A*搜索算法

目录

简述

算法流程

 算法实现与求解

求解过程

算法实现

数据结构

代码实现

---

简述

A搜索算法是一种启发式搜索的算法，通过估价函数f(x)=g(x)+h(x)对节点进行排序

g(x)为起点到该节点的到代价估计，h(x)为启发值(受对实际问题的理解而不同)，为估计该节点到目标节点的代价估计

当g(x)与h(x)足够保守为最小代价估计，就变为了A*算法

算法流程

 算法实现与求解

求解过程

以下面的图为例，讲解一下具体过程

其中

括号内的数值为该节点到目标节点E的估计代价h

边上的数值为起点A到该节点的估计代价g

 首先从起点A出发,其代价估计值为

f(A)=g(A)+h(A)=0+20=20(自己到自己的代价为0)

将A送入OPEN表里，OPEN表非空，将表里f最小的点进行后继节点BC拓展，同时移入CLOSED表

计算B,C的代价估计值

f(B)=g(AB)+h(B)=1+14=15

f(C)=g(AC)+h(C)=6+8=14

f(D)=g(AD)+h(D)=9+4=13

此时OPEN表非空,将表里f最小的点D进行后继节点E拓展，同时将其移入CLOSED表

f(E)=g(ADE)=(9+20)+0=29

此时OPEN表非空,将OPEN表里f最小的点C进行后继节点D拓展，同时将其移入CLOSED表

f(D)'=g(ACD)+h(D)=(6+1)+4=11<f(D)更新f(D)的取值

此时OPEN表非空,将OPEN表里f最小的点D进行后继节点E拓展，同时将其移入CLOSED表

f(E)'=g(ACDE)+h(E)=(6+1+20)=27<f(E)更新f(E)

此时OPEN表非空,将OPEN表里f最小的点B进行后继节点CD拓展，同时将其移入CLOSED表

f(C)'=g(ABC)+h(B)=(1+1)+8=10<14更新C

f(D)'=g(ABD)+h(D)=(1+4)+4=9<f(D)=11更新D

此时OPEN表非空,将OPEN表里f最小的点D进行后继节点E拓展，同时将其移入CLOSED表

f(E)=f(ABDE)+h(E)=25

此时OPEN表非空,将OPEN表里f最小的点C进行后继节点D拓展，同时将其移入CLOSED表

f(D)'=g(ABCD)+h(D)=(1+1+1)+4=7<9更新D

此时OPEN表非空,将OPEN表里f最小的点D进行后继节点E拓展，同时将其移入CLOSED表

f(E)'=g(ABCDE)+h(E)=(1+1+1+1+20)+0=23<27，更新E

此时OPEN表非空,将OPEN表里f最小的点E移入CLOSED表

此时OPEN表为空算法结束

路径为A->B->C->D->E,代价为23

算法实现

分为数据结构以及功能类的编写，要实现这个算法就要实现

数据结构

class node():
    def __init__(self,node:int,parent:int,g,h):
        '''node等于parent时说明该节点为起点\n
        node:节点序号\n
        parent:父亲节点\n
        g:路径代价\n
        h:启发式信息,该点到终点希望更大h越小'''
        self.node=node
        self.parent=parent
        if node==parent:self.g=0
        else:self.g=g
        self.h=h
        self.f=g+h

代码实现

import os
nodenum=26
#0号下标不用,下方的测试数据也是
letter=['']+[chr(ord('A')+i)for i in range(nodenum-1)]
class node():
    def __init__(self,node:int,parent:int,g,h):
        '''node等于parent时说明该节点为起点\nnode:节点序号\nparent:父亲节点\ng:起点到目标节点代价\nh:终点到目标节点代价'''
        self.node=node
        self.parent=parent
        if node==parent:self.g=0
        else:self.g=g
        self.h=h
        self.f=g+h
def sortkey(nodes:node):
    '''将node节点的f(n)作为sort排序函数比较点key,返回节点的f(n)'''
    return nodes.f
class AS():
    '''data格式如(1,0,3),(0,2,5)表示为[[[2,5]],[[0,3]],[]]'''
    def __init__(self,data:list,hlist,target,o):
        '''data:数据集合\nhlist:节点启发式信息集合\ntarget:终点\no:起点'''
        #OPEN,CLOSED表初始化
        self.OPEN:list[node]=[]
        self.CLOSED:list[node]=[]
        self.data=data
        self.hlist=hlist
        self.target=target
        self.o=o
    def findnodC(self,nod):
        '''CLOSED表中查找有无节点nod\n有返回节点在CLOSED表中的下标,否则返回-1'''
        for i in range(len(self.CLOSED)):
            if self.CLOSED[i].node==nod:
                return i
        return -1
    def findnodO(self,nodei:node):
        '''OPEN表中查找有无节点nodei,如果有则比较nodei的f(n)与表中节点的f(n)谁小,保留小的那个\n若没有,则直接添加'''
        x=-1
        #查找OPEN表有无nodei节点名相同的点
        for i in range(len(self.OPEN)):
            if self.OPEN[i].node==nodei.node:
                x=i
                break
        if x==-1:
            #OPEN表中没有nodei.node节点
            self.OPEN.append(nodei)
        else:
            #OPEN表中有nodei.node节点,比较这两个节点的f(n)值
            if self.OPEN[x].f>nodei.f:
                del self.OPEN[x]
                self.OPEN.append(nodei)   
    def findmin(self):
        '''返回OPEN表中f(n)最小的节点'''
        #由于OPEN经过重排,-1下标的节点f(n)最小
        minnode=node(self.OPEN[-1].node,self.OPEN[-1].parent,self.OPEN[-1].g,self.OPEN[-1].h)
        #查看CLOSED表中有没有这个节点
        x:int=self.findnodC(minnode.node)
        if x==-1:
            #CLOSED表,没有则添加
            self.CLOSED.append(minnode)
        else:
            #CLOSED有,则比较f(n)值
            if self.CLOSED[x].f>minnode.f:
                del self.CLOSED[x]
                self.CLOSED.append(minnode)
        del self.OPEN[-1]
        return minnode.node
    def sortOPEN(self):
        '''重排OPEN表'''
        def sortkey(nodes:node):return nodes.f
        #''重排OPEN表'''
        self.OPEN.sort(key=sortkey)
        self.OPEN=self.OPEN[::-1]
    def Tuozhang_Sort(self,n):
        '''拓展OPEN表中的节点n,将其移入CLOSED并重排OPEN表'''
        #当节点没有后继节点,return空
        length=len(self.data[n])
        if length==0:return
        #当节点有后继节点
        for m in range(length):
            i=self.data[n][m]
            nod=i[0]
            #后继节点g(n)=父亲节点的g(n)值加上两点间的权重
            g=self.CLOSED[-1].g+i[1]
            #启发式信息
            h=self.hlist[nod]
            #查找OPEN表中有无此节点,如果有则比较nodei的f(n)与表中节点的f(n)谁小,保留小的那个\n若没有,则直接添加
            self.findnodO(node(nod,n,g,h))
        self.sortOPEN()
    def findparent(self,nod):
        '''返回nod节点的父亲节点,如果没有则返回-1'''
        for i in self.CLOSED:
            if i.node==nod:
                #当找到起点(parent=node)则停止
                if i.parent==nod:
                    return -1
                return i.parent
        return -1
    def AS(self):
        '''返回代价以及路径'''
        #按算法流程实现
        #首先初始化S
        S=node(node=self.o,parent=self.o,g=0,h=self.hlist[self.o])
        #将S放入OPEN表
        self.OPEN.append(S)
        while True:
            #如果OPEN表为空则失败
            if len(self.OPEN)==0:break
            #查找OPEN表中最小f(n)的节点
            i=self.findmin()
            #如果i是目标则停止
            if i==self.target:break
            #拓展OPEN表中的节点i,将其移入CLOSED并重排OPEN表
            self.Tuozhang_Sort(i)
            #显示模块,在下一行的'''前加#即可
            '''
            print('##############\nClosed')
            for i in self.CLOSED:
                print('({},{})'.format(l[i.node],i.f))
            print('##############\nOpen')
            for i in self.OPEN:
                print('({},{})'.format(l[i.node],i.f))
            input('回车继续')
            os.system('clear')
            #'''
        #self.CLOSED[-1]为目标节点
        cost=self.CLOSED[-1].g
        path0=[]
        #逆推通过parent找到路径
        while 1:
            path0.append(i)
            i=self.findparent(i)
            if i==-1:break
        #由于一直往后插入节点,因此需要一次翻转
        path0=path0[::-1]
        #将节点转化为用字母表示
        path=''
        for i in path0:
            path+=(letter[i]+'->')
        path=path[:-2]
        return cost,path
'''测试数据1
initnode=1
endnode=5
datas=[ [],
        [[2,1],[3,6],[4,9]],
        [[3,1],[4,4]],
        [[4,1]],
        [[5,20]],
        []]
h=[0,20,14,8,4,0]
#'''
 
#'''测试数据2
datas=[
    [],
    [[2,2]],
    [],
    [[1,1],[4,2]],
    [],
    [[1,4],[3,1]],
    [[7,1]],
    [[8,2],[5,1]],
    []
]
initnode=6
endnode=2
# [0,1,2,3,4,5,6,7,8]
# [0,a,b,c,d,e,f,g,h]
h=[0,2,0,3,3,4,6,5,3]
#'''
 
solution=AS(datas,h,target=endnode,o=initnode)
cost,path=solution.AS()
 
print('##############\nClosed\n--------------')
for i in solution.CLOSED:
    print('({},{})'.format(letter[i.node],i.f))
print('##############\nOpen  \n--------------')
for i in solution.OPEN:
    print('({},{})'.format(letter[i.node],i.f))
print('##############')
print('cost:',cost)
print('path:',path)