位置: 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+,内容如对您有帮助,希望把文章链接给更多的朋友!

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

说明

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)

以上就是python A*算法的介绍,希望对大家有所帮助。更多Python学习指路:Python基础教程

本文链接地址:https://www.jiuchutong.com/zhishi/313077.html 转载请保留说明!

上一篇:🎉使用JSONP解决跨域(jsoncpp使用)

下一篇:Nginx 防盗链(nginx防盗链的作用)

  • 纳税申报操作视频
  • 员工报销没有发票怎么入账
  • 增值税加计递减额,这个科目如何使用
  • 桐木板芯销售
  • 建造普通标准住宅出售,增值税超过扣除金额的
  • 发生销售折让可以不开具
  • 低值易耗品费用包括哪些
  • 无票销售纳税后怎么处理
  • 以前年度固定资产入账错误怎么办?
  • 个人应纳税所得额 税率
  • 公司给离职员工个税零申报
  • 虚开发票对所得税的影响是怎样的?
  • 开具红字发票无蓝字发票如何网上申报?
  • 施工工人个税怎么计算?
  • 银行利息增值税发票
  • 海关特许权使用费 公告
  • 外购固定资产如何入账
  • 固定资产残值率一般是多少
  • 筹建期的收入要交企业所得税吗
  • 折旧计算所得税吗
  • Windows10如何切换中英文输入法
  • 投标保证金利息规定
  • 单位交水费会计分录
  • 水电费无发票如何做账
  • win7系统鼠标键盘
  • apache24启动不了错误代码1
  • Mysql的GROUP_CONCAT()函数使用方法
  • 出租商品计入什么科目
  • window10自带商店下载位置
  • win11dev预览版可以升级正式版吗
  • php常用时间函数
  • 使用二氧化碳灭火器时人应该站在什么位置
  • php 截断
  • 人均劳效的意义
  • vite 配置
  • hypergraph learning
  • javascriptz
  • 造孽啊啥意思
  • 办公费用的核算方法
  • 医院会计医保怎么做账
  • 存货非正常损失可以所得税前扣除吗
  • 工程项目发票几个点
  • 接待客户的住宿费计入什么科目
  • 不应确认增值税销项税额的
  • 哪些费用计入管理费用
  • 用友u8财务报表打印设置在哪
  • 汽车修理厂会计账务处理
  • 海关缴款通知书怎么查看
  • 普通发票记账联丢了怎么解决
  • 异地成立分公司的流程和要求
  • 交通运输服务包括程租
  • 存货跌价准备如何影响利润
  • 大家怎么看理想这个牌子
  • 我国居民企业判断标准
  • 招待费的增值税怎么算
  • 其他综合收益属于什么科目借贷
  • 票折费用是什么意思
  • 营业收入大于资产怎么办
  • 投入产出比的计算依据
  • 凭证导致账簿错误
  • 微软6月24发布
  • linux的问题
  • hotkey在哪
  • Win7旗舰版系统文件名称
  • win10开机提示xwz
  • win10系统自带虚拟机无法启
  • ubuntu操作
  • 360安全卫士检测出来高危漏洞需要修复吗
  • IE6/IE7/IE8/IE9中tbody的innerHTML不能赋值的完美解决方案
  • androidstudio ui
  • 深入浅出python中文第二版pdf
  • shell脚本随机数
  • 基于javascript的毕业设计
  • 四川国税局普通发票查询?
  • 网上申报成功怎么查询
  • 小规模纳税人怎么申报纳税
  • 宁波出租车购买
  • 成效显著的近义词和反义词
  • 苏州税务系统
  • 车辆购置税查询官网
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设