赞
踩
如果使一般搜索过程满足如下限制,则它就成为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的,到达目标节点的代价和最小的路径。
- 欧几里得距离 ( Euclidean distance)也称欧式距离,它是一个通常采用的距离定义,它是在m维空间中两个点之间的真实距离(直线距离)。
- 出租车几何或曼哈顿距离(Manhattan Distance)是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ,是种使用在几何度量空间的几何学用语,用以标明两个点在标准坐标系上的绝对轴距总和。
- 切比雪夫距离(Chebyshev distance)或是L∞度量,是向量空间中的一种度量,二个点之间的距离定义是其各坐标数值差绝对值的最大值。
八数码问题是否有解
解释如下:
与其他算法的比较
利用A*算法进行路径规划
状态空间搜索策略
#结点
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*算法的区别。
这一次先到这里,先准备下一场答辩,我还会再回来继续探索的!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。