筛押 ? 数据统计论文 计算机毕业论文程序 本科论文数据库 硕博士论文数据库 医学论文数据统计 博硕士论文文摘库 国外学位论文 博硕士论文全文数据库 论文投稿程序 web设计论文

金祥彩票注册

星级: ★★★★ 期刊: 著名作者:张晨 王明根 李宇豪 王洁 霍迎秋 浏览量:2070 论文级别:高评本章主题:数据程序原创论文: 5156论文网更新时间:审核稿件编辑:Christ本文版权归属:www.5156chinese.cn 分享次数:4054 评论次数: 9555

导读:此篇文章是数据程序相关的毕业论文文献综述,供需要写此方面相关本科和硕士以及专科生毕业论文的学子们鉴赏

摘要:为了解决泊松分酒的一般性问题,本文结合图论以及广度优先搜索算法,考虑求解的时空复杂度,借助map存放复杂类型数据的特点并根据实际设置剪枝函数,进而设计出该类问题的一般性求解算法.

关键词:泊松分酒问题;广度优先搜索;状态转移;图论

中图分类号:TP3016文献标识码:A文章编号:1007-9416(2018)04-0038-02

1引言

泊松分酒问题是由泊松所提出来的求解三个无刻度酒瓶由12、8、5品脱多次转移为6、6、0品脱的过程的智力问题,一直在中小学奥赛乃至大学的数学类竞赛中频繁出现,引发了广泛关注.对这类问题的一般性问题,即当无刻度的酒瓶个数为n时的状态转移问题,成为研究的热点.

基于图的泊松分酒问题一般解的研究
数据程序毕业论文文献综述

2一般性泊松分酒问题及分析

一般性的分酒问题是指n个没有刻度的酒瓶,n个瓶子的容量表示为,n个瓶子的初始状态表示为,讨论是否存在使n个酒瓶的最终状态为的方法.

一般性分酒问题的求解方法空间复杂度为,每一种瓶子的状态有种可能,故状态数为,随着n的增加,基于邻接矩阵的方法,将会产生很多无用的状态节点,造成空间的浪费.对于一般问题的时间复杂度则是,状态迁移过程直接影响了时间复杂度,状态的每一次转移都有种可能性.并可能出现重复遍历或者循环遍历的情况,增加了时间复杂度.

3BFS算法及其在分酒问题的应用

31广度优先搜索(BFS)

BFS是一种基于图的基础搜索方法,是以一种分层递进的搜索方式进行搜索的过程,如图1所示.对应广度优先搜索算法过程如下:

如何写数据专业学术论文
观看次数:3064 点评人数:530

(1)从顶点①出发,并访问此顶点;(2)从①出发,访问①的各个未曾访问的邻接点②,④,⑤;然后,依次从②,④,⑤出发访问各自未被访问的邻接点;(3)重复(2)直到全部节点被访问或找到结果.

32分酒问题分析

此篇论文原创地址:

对于一般分酒问题,状态遍历过程会造成巨大的时间开销.并且当搜索的过程不断地深入,必存在很多节点重复遍历的情况,将会导致很多无用遍历或者死循环遍历等,故需要对每一个遍过的状态进行标记.据分析可知其状态构成的矩阵为低密度矩阵,存在着大量不可到达的无用状态节点.因此当n很大时,将导致巨大且无用的空间开销,故并不需要专门开辟大量空间去存储,而可通过队列实时动态变化.并采用map容器进行存储,其可通过的方式进行存储数据,用key表示一个具体的状态字符串,value表示上一具体状态迁移变化成key状态过程的字符串.从而可以方便的回溯寻找最小路径.

综上,将状态节点的遍历过程视为广搜遍历一棵满(n*(n-1))叉树的过程(當前状态到下一状态有n*(n-1)种可能).当搜索到结果时,可将map容器存储的内容输出或无结果.

33分酒问题算法设计

根据初始、最终状态及酒瓶容量,利用getResult()函数求初始到最终状态所经历的路径.其中getResult()函数调用了Dochange()得到转移后的结果以及printTrace()函数输出路径.

现给出基本实现流程如图2所示.

其中变量含义如下:

i,j:第一、二次循环的循环变量;A,B:分别代表了倒出瓶和倒入瓶;Av,Bv:分别代表了A,B瓶的状态;AB,BB:分别代表了A,B瓶的容量.

本算法剪枝函数共设置三个,一是剪掉已经遍历过的状态,是剪掉不能到达的状态,三是具体问题具体分析从而限制.通过对倒酒过程所到达的节点状态的分析,存在一些不可能到达的状态,如(0,0,…,0)等,鉴于很多它们的存在,为防止程序在搜索过程中,进入死循环又不知的情况,必须为具体的问题的步数设定一个限度.若超过了这个限度,即认为问题无解.

4实例

41实例分析

运用上述所设计的算法,下面以一个实例来演示问题的解决和进行算法说明的过程.其中n取3,3个瓶子容量为(853),3个瓶子的初始状态为(800),3个瓶子的最终状态为(4,4,0).

依照上述算法,因有3个酒瓶,故当从搜索队列中取出一个状态后,现状态到下一状态的选择有6条路径(2*3),包括0、1、2瓶分别倒入其它非自己的瓶.故搜索树是一个满6叉树,如图3所示.

42搜索过程

“A,B,C”代表酒瓶的状态,若其后跟×表示该状态不符合条件,其下子树被剪.“-1”表示不符合状态转换条件,无返回.“-”表示转换无效,值与之前得到的同.X→Y代表将X瓶中的酒倒入Y瓶中,[(A,B,C),(D,E,F,)-X→Y]表示状态的迁移过程,由状态“D,E,F”是在状态“A,B,C”下将X瓶中的酒倒入Y瓶中得到的.

当从搜索队列中取出状态是“8,0,0”时,队列为空.广搜结果如表1所示.

依次搜索与队列首节点相邻的节点并添加到搜索队列中,直到搜索到要求的状态或者队列为空.本例经过上述过程的13次循环,搜索得到的结果树如图4所示.

搜索到状态“4,4,0”时,根据map中的记录利用栈进行逆序输出,输出结果如路径II所示.

5结语

本文基于图论和广度优先搜索算法解决了分酒问题的一般性问题.其中剪枝函数的设置和存储方式的选择,极大地优化了程序的结构,降低了时间复杂度,有效的提高了算法的效率.该方法对各种无刻度液体的多种状态转换或者特定方式的分配提供了有益的解决方法和思路,具有现实意义.

${11}

本篇浅论基于图的泊松分酒问题一般解的研究论文范文综合参考评定如下
有关论文范文主题研究:关于数据毕业论文文献综述大学生适用:课程毕业论文
相关参考文献下载数量:530写作解决问题:撰写毕业论文文献综述
毕业论文开题报告:学术任务书写作职称论文适用:撰写职称论文,职称专业
所属大学生专业类别:数据专业毕业论文文献综述论文题目推荐度:最新题目
${12}

[ 参考文献 ]

1、基于DRBD的数据热备程序的分析与部署
(厦门市工人文化宫,福建 厦门 361012) 中小企业信息系统的建设日渐完善,对应用程序数据的热备要求也更加强烈,但其信息化资金有限,很难采用大型的集成商的数据热备软件文章采用

2、程序化购买或将“宠冠”广告市场
近年来,越来越多的传统企业感受到互联网的威力,其中尤以互联网营销对传统企业营销方式冲击最大如今,传统企业更加重视网络营销的作用,希望更加精准便利地与用户接触在这样的环境下,程序化购买市场格局会发生

3、大型放样测量工程中的坐标读取程序
(深圳市勘察研究院金祥彩票,广东 深圳 518000)在测量放样工作中,获取待放样点坐标数据是最重要的基础工作文章提出一种方法,即在获得CAD文档的基础上,利用AutoLisp自动读取坐标数据

计算机毕业论文程序本科论文数据库硕博士论文数据库


本篇论文阅读总结:为有关撰写数据程序方向的毕业论文文献综述与课程研究的学生们在完成学术毕业论文数据论文开题报告范文以及相关论文格式模版起到一定的帮助

本篇有关数据程序毕业论文范文免费供大学生阅读参考-点击更多753240篇数据程序相关论文开题报告格式范文模版供阅读下载
延伸阅读: 硕士论文答辩程序外文学位论文数据库自考论文程序毕业论文答辩的程序哪里找毕业论文国外学位论文数据库数据库论文摘要论文资料库硕士博士论文数据库财务报表审计论文
生物技术论文题目 水利渠道管理论文 月季组织培养论文 有关投资的论文题目 关于安全用电的论文 水泥包装机论文 雾霾的成因与防治论文 职称论文杂志黑名单 文化生活论文 论文课题计划