位置: IT常识 - 正文

python A*算法是什么(python apriori算法)

编辑：rootadmin

推荐整理分享python A*算法是什么(python apriori算法)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:python的a+,python计算a+aa+aaa,python计算a+aa+aaa,python apriori算法,a*算法代码 python,python的a+,pythonai算法,python的a+,内容如对您有帮助，希望把文章链接给更多的朋友！

说明

1、A*算法是静态路网中解决最短路径最有效的直接搜索方法。

2、A*算法是启发式算法，采用最佳优先搜索策略(Best-first)，基于评估函数对每个搜索位置的评估结果，猜测最佳优先搜索位置。

A*算法大大降低了低质量的搜索路径，因此搜索效率高，比传统的路径规划算法更实时、更灵活。但A*算法找到的是相对最优的路径，而不是绝对最短的路径，适合大规模、实时性高的问题。

实例

importheapqimportcopyimportreimportdatetimeBLOCK=[]#给定状态GOAL=[]#目标状态#4个方向direction=[[0,1],[0,-1],[1,0],[-1,0]]#OPEN表OPEN=[]#节点的总数SUM_NODE_NUM=0#状态节点classState(object):def__init__(self,gn=0,hn=0,state=None,hash_value=None,par=None):'''初始化:paramgn:gn是初始化到现在的距离:paramhn:启发距离:paramstate:节点存储的状态:paramhash_value:哈希值，用于判重:parampar:父节点指针'''self.gn=gnself.hn=hnself.fn=self.gn+self.hnself.child=[]#孩子节点self.par=par#父节点self.state=state#局面状态self.hash_value=hash_value#哈希值def__lt__(self,other):#用于堆的比较，返回距离最小的returnself.fn<other.fndef__eq__(self,other):#相等的判断returnself.hash_value==other.hash_valuedef__ne__(self,other):#不等的判断returnnotself.__eq__(other)defmanhattan_dis(cur_node,end_node):'''计算曼哈顿距离:paramcur_state:当前状态:return:到目的状态的曼哈顿距离'''cur_state=cur_node.stateend_state=end_node.statedist=0N=len(cur_state)foriinrange(N):forjinrange(N):ifcur_state[i][j]==end_state[i][j]:continuenum=cur_state[i][j]ifnum==0:x=N-1y=N-1else:x=num/N#理论横坐标y=num-N*x-1#理论的纵坐标dist+=(abs(x-i)+abs(y-j))returndistdeftest_fn(cur_node,end_node):return0defgenerate_child(cur_node,end_node,hash_set,open_table,dis_fn):'''生成子节点函数:paramcur_node:当前节点:paramend_node:最终状态节点:paramhash_set:哈希表，用于判重:paramopen_table:OPEN表:paramdis_fn:距离函数:return:None'''ifcur_node==end_node:heapq.heappush(open_table,end_node)returnnum=len(cur_node.state)foriinrange(0,num):forjinrange(0,num):ifcur_node.state[i][j]!=0:continuefordindirection:#四个偏移方向x=i+d[0]y=j+d[1]ifx<0orx>=numory<0ory>=num:#越界了continue#记录扩展节点的个数globalSUM_NODE_NUMSUM_NODE_NUM+=1state=copy.deepcopy(cur_node.state)#复制父节点的状态state[i][j],state[x][y]=state[x][y],state[i][j]#交换位置h=hash(str(state))#哈希时要先转换成字符串ifhinhash_set:#重复了continuehash_set.add(h)#加入哈希表gn=cur_node.gn+1#已经走的距离函数hn=dis_fn(cur_node,end_node)#启发的距离函数node=State(gn,hn,state,h,cur_node)#新建节点cur_node.child.append(node)#加入到孩子队列heapq.heappush(open_table,node)#加入到堆中defprint_path(node):'''输出路径:paramnode:最终的节点:return:None'''num=node.gndefshow_block(block):print("---------------")forbinblock:print(b)stack=[]#模拟栈whilenode.parisnotNone:stack.append(node.state)node=node.parstack.append(node.state)whilelen(stack)!=0:t=stack.pop()show_block(t)returnnumdefA_start(start,end,distance_fn,generate_child_fn,time_limit=10):'''A*算法:paramstart:起始状态:paramend:终止状态:paramdistance_fn:距离函数，可以使用自定义的:paramgenerate_child_fn:产生孩子节点的函数:paramtime_limit:时间限制，默认10秒:return:None'''root=State(0,0,start,hash(str(BLOCK)),None)#根节点end_state=State(0,0,end,hash(str(GOAL)),None)#最后的节点ifroot==end_state:print("start==end!")OPEN.append(root)heapq.heapify(OPEN)node_hash_set=set()#存储节点的哈希值node_hash_set.add(root.hash_value)start_time=datetime.datetime.now()whilelen(OPEN)!=0:top=heapq.heappop(OPEN)iftop==end_state:#结束后直接输出路径returnprint_path(top)#产生孩子节点，孩子节点加入OPEN表generate_child_fn(cur_node=top,end_node=end_state,hash_set=node_hash_set,open_table=OPEN,dis_fn=distance_fn)cur_time=datetime.datetime.now()#超时处理if(cur_time-start_time).seconds>time_limit:print("Timerunningout,break!")print("Numberofnodes:",SUM_NODE_NUM)return-1print("Noroad!")#没有路径return-1defread_block(block,line,N):'''读取一行数据作为原始状态:paramblock:原始状态:paramline:一行数据:paramN:数据的总数:return:None'''pattern=re.compile(r'\d+')#正则表达式提取数据res=re.findall(pattern,line)t=0tmp=[]foriinres:t+=1tmp.append(int(i))ift==N:t=0block.append(tmp)tmp=[]if__name__=='__main__':try:file=open("./infile.txt","r")exceptIOError:print("cannotopenfileinfile.txt!")exit(1)f=open("./infile.txt")NUMBER=int(f.readline()[-2])n=1foriinrange(NUMBER):l=[]forjinrange(NUMBER):l.append(n)n+=1GOAL.append(l)GOAL[NUMBER-1][NUMBER-1]=0forlineinf:#读取每一行数据OPEN=[]#这里别忘了清空BLOCK=[]read_block(BLOCK,line,NUMBER)SUM_NODE_NUM=0start_t=datetime.datetime.now()#这里添加5秒超时处理，可以根据实际情况选择启发函数length=A_start(BLOCK,GOAL,manhattan_dis,generate_child,time_limit=10)end_t=datetime.datetime.now()iflength!=-1:print("length=",length)print("time=",(end_t-start_t).total_seconds(),"s")print("Nodes=",SUM_NODE_NUM)