位置: 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防盗链的作用)

  • 免税肉类主要品种目录
  • 风险纳税人是指个人还是单位
  • 公司购入的财务怎么做账
  • 预缴增值税需要预缴附加税吗
  • 所得税分支机构分配表怎么填
  • 运输费增值税专用发票几个点
  • 失控发票补税可以抵扣吗
  • 成本和费用的区别在于()
  • 金税盘全额抵扣分录
  • 小规模给一般纳税人开专票能抵扣吗
  • 托管物资账务处理流程
  • 贷款应计利息会计分录
  • 必须开具增值税专用发票
  • 广告费可以预提吗
  • 挂靠被查出来后挂靠费怎么处理?
  • 财务报表层次重大错报风险增大了认定层次
  • 企业外购的房屋建筑物是否属于非房地产企业
  • 自然人独资属于个体工商户吗?
  • 房地产公司缴纳契税的会计分录
  • 收了公司的款项不拿回公司属于什么行为
  • 跨区域经营增值税所得税预缴多少
  • 增值税专用发票几个点
  • 关于不动产进项税额分期抵扣的新政策,以下不属于
  • 开错的发票正常入账吗
  • 办公室购买绿植违规吗
  • 收到多开的发票会计上怎么入成本?
  • 金税服务费会计分录
  • 核销单怎么做
  • 支出税费
  • 计算应纳税所得额时可以扣除的项目有
  • linux进程管理器
  • 出口关税的税率
  • 小企业原材料包括
  • 总承包简易计税
  • 对数据文件操作,进行数据记录的交换都要经过
  • php常见面试问题
  • php随机ua
  • PHP:pg_send_query_params()的用法_PostgreSQL函数
  • keyemain.exe是什么
  • php assign
  • 子公司财务管理策略有哪些
  • 办理房屋租赁需要的材料
  • token登录器
  • 软件是无形的,可见的物理实体
  • php获取年月日
  • 小规模纳税人购入货物收到增值税专用发票
  • 增值税发票认证期限是多久
  • mysql的字符串
  • 请问资产负债表中净资产怎么算
  • 银行存款日记账电子表格模板
  • 员工出差报销的餐费怎么下账
  • 公司的房租发票怎么开
  • 以前年度损益调整结转到本年利润吗
  • 未达起征点可以申请一次性创业补贴吗
  • 其他应付款贷方表示什么意思
  • 购进中央空调可以抵税吗
  • 会计应该怎么做职业规划
  • 支票填写的规范与常识
  • mysql基本sql语句大全(基础用语篇)
  • MySQL使用select语句查询指定表中指定列(字段)的数据
  • windows10的设置在哪里
  • xp安装声卡驱动
  • 深度隐藏root
  • ssd安装centos7
  • linux 文件执行
  • win7手动更新在哪里设置
  • win7任务管理器怎么调回原来样子
  • 有道词典手机
  • shell字符串操作命令
  • 删除默认共享的文件夹
  • 深入python3
  • node和javascript
  • 安卓实时屏幕
  • python开发的程序怎么运行
  • 国家税务局级别排名
  • 河南普通发票查询真伪查询系统
  • 专项附加扣除当月填报何时生效
  • 土地出让金入账后就摊销吗
  • 国家税务局令第16号文
  • 税务实名认证如何操作
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设