当前位置：文档之家› 实验1用盲目搜索解决小孩分油问题

实验1用盲目搜索解决小孩分油问题

【实验目的】

1，掌握盲目搜索中深度优先搜索与广度优先搜索算法；

2，掌握对小孩分油问题的建模、编程，解决该问题。

【问题描述】

练习编写一个程序，求解下列小孩分油问题：两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两、一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，在回家的路上，两人想平分这一斤油，可是又没有其它工具。试仅用三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。

【算法选择】

通过分析题目并结合深度优先、广度优先和迭代加深搜索的算法的特点以及有缺点，这里选择广度优先算法来求解该分油问题。如果采用深度优先算法搜索，由于其盲目性导致搜索陷入局部陷阱，并不一定能求得解即使得到解也不一定是最优解，因此并不采用此算法。迭代加深搜索则是在固定的深度上进行深度和广度搜索结合的策略来进行搜索，这样避免了单一的深度搜索无法得到解的缺点，但是找到的解并不一定是最优解。广度优先以牺牲空间代价和时间代价来换取保证取得最优解。由于该问题并不复杂，即使使用广度优先算法也不会占有太多的空间和时间，因此为了取得最优解这里选择广度优先算法来求解。

【实验步骤】

1，问题状态表示

用向量（T，S，R）表示状态，其中T表示10两瓶中的油量，S表示7两瓶中的油量，R表示3两瓶中的油量。

问题的起始状态：(10，0，0)；

问题的目标状态：(5，X,X)，（x,y,z）表示状态空间，x只能属于0至10,y 只能属于0至7,z只能属于0至3。

2，确定智能算子，用以确定智能算子，用以表示变化状态的规则。由于总共油量为10两，而10两的瓶可以装满所有的油，因此可以把10两的瓶当作一个大油桶，这样此题就化为8/6类似的问题了。

规则号规则规则解释

1 （S，R）and S<7->(7,R) 7两瓶不满时装满

2 （S，R）and R<3->(S,3) 3两瓶不满时装满

3 （S，R）and S>0->(0,R) 7两瓶不空时倒空

4 （S，R）and R>0->(S,0) 3两瓶不空时倒空

5 （S，R）and S>0 and S+R≤3 ->(0,S+R) 7两瓶中的油全倒入3两瓶

6 （S，R）and R>0 and S+R≤

7 ->(S+R,0) 3两瓶中的油全导入7两瓶

7 （S，R）and S<7and S+R≥7 ->(7,S+R-7) 用3两瓶中的油装满7两瓶

8 （S，R）and R<3 and S+R≥3->(S+R-3,3) 用7两瓶中的油装满3两瓶

3，程序设计

盲目搜索算法中常用的搜索策略有两种：深度优先搜索(Depth First Search,DFS)和广度优先搜索(Breadth First Search,BFS)，这里我的程序以广度优先搜索来实现。

【实验结果】

实验结果如下(实验平台:Microsoft Visual Studio 2012)。

【实验总结】

1，由于是盲目搜索，要检查到每一个状态，因此，实验的时空复杂度比较大，不适合解决大规模问题目；

2，实验没有其它任何信息，因此，必须对实验过程的每一个操作及其规则能详尽列出，这样，才能使程序检查到每一个状态；

3，由于不同问题有不同的操作要求和操作规则，比如，这里的分油问题，如果不是3个瓶或什么的，那么所有的程序就都得重新根据问题来编写，可见，盲目搜索算法通用性不强，但是，作为我们面对一个具体问题时，盲目搜索的思想是首当其冲能够想到的，在无法找到有效方法时，盲目搜索算法是比较实用的。

搜索策略实验报告

学生实验报告实验课名称：人工智能实验项目名称：八数码实验专业名称：计算机科学与技术班级： 2012240201 学号： 201224020102 学生姓名：张璐教师姓名：陈亮亮 2014年12 月13 日

实验日期：2014 年12 月9 日实验室名称：明远2202

最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s[3][3]中所处行号，j_0：0在s[3][3]中所处列号)也存储在DATA中。五．源程序： struct array { int id; int depth; int Wx; //错位个数 int moveNum;//计算移动距离 int a[MAX_X][MAX_Y]; int x; //0的横坐标（在数组里的） int y; //0的纵坐标 }; class EightDigital { public: EightDigital(int a[MAX_X][MAX_Y],int b[MAX_X][MAX_Y]); ~EightDigital(); bool safe(int x,int y); //判断与0相邻的位置能否交换，防止数组越界bool compare(); //判断是否到达目标 void search(int x,int y); //搜索目标 void addOpenTable(int x0,int y0,int x1,int y1);//x0,y0是交换前0的坐标，x1,y1是交换后0的坐标,加入open表 void addCloseTable(); //create close table void deleteOpenTable(); void insertSort(); void exchange(int x0,int y0,int x1,int y1); //交换数组值，移动0 int Wx(); //计算错位个数 void print(); //打印数组 bool haveSolution(); int moveNum();

盲目搜索

盲目搜索搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造盲目搜索也叫无信息搜索，只适合用于求解比较简单的问题。我们没有指定问题的任何推理信息，例如要搜索这一部分而不是另一部分，就像到目前为止的只要发现一条到目标的路径即可。这种过程被称为是盲目的。盲目搜索过程只把算子应用到节点，它没有使用问题领域的任何特殊知识（除了关于什么动作是合法的知识外）。最简单的盲目搜索过程就是广度优先搜索。该过程把所有的算子应用到开始节点以产生一个显式的状态空间图，再把所有可能的算子应用到开始节点的所有直接后继，再到后继的后继，等等。搜索过程一律从开始节点向外扩展。由于每一步将所有可能的算子应用到一个节点，因此可把它们组成一个叫后继函数的函数。当把后继函数应用到一个节点时，产生一个节点集，该节点集就是把所有能应用到那个节点的算子应用到该节点而产生的。一个节点的后继函数的每一次应用称为节点的扩展相同代价搜索是广度优先搜索的一种变体，在该方法中，节点从开始节点顺着代价等高点向外扩展，而不是顺着相同深度等高线。如果图中所有弧的代价相同，那么相同代价搜索就和广度优先搜索一致。反过来，相同代价搜索可以看作是下一章要讲的启发式搜索的一个特殊情况。广度优先和相同代价搜索方法的简要描述只给出了它们的主要思想，但是要解决其他复杂的情况则需要技术改进

密立根油滴实验报告

密立根油滴实验——电子电荷的测量【实验目的】 1. 通过对带电油滴在重力场和静电场中运动的测量，验证电荷的不连续性，并测定电荷的电荷值e 。 2. 通过实验过程中，对仪器的调整、油滴的选择、耐心地跟踪和测量以及数据的处理等，培养学生严肃认真和一丝不苟的科学实验方法和态度。 3. 学习和理解密立根利用宏观量测量微观量的巧妙设想和构思。【实验原理】 1. 静态（平衡）测量法用喷雾器将油滴喷入两块相距为d 的平行极板之间。油在喷射撕裂成油滴时，一般都是带电的。设油滴的质量为m ，所带的电量为q ，两极板间的电压为V ，如图 1 所示。如果调节两极板间的电压V ，可使两力达到平衡，这时： d V q qE mg == (1) 为了测出油滴所带的电量q ，除了需测定平衡电压V 和极板间距离d 外，还需要测量油滴的质量m 。因m 很小，需用如下特殊方法测定：平行极板不加电压时，油滴受重力

作用而加速下降，由于空气阻力的作用，下降一段距离达到某一速度g ν后，阻力r f 与重力mg 平衡，如图 2 所示（空气浮力忽略不计），油滴将匀速下降。此时有： mg v a f g r ==ηπ6 (2) 其中η是空气的粘滞系数，是a 油滴的半径。经过变换及修正，可得斯托克斯定律： pa b v a f g r + = 16ηπ (3) 其中b 是修正常数， b=6.17×10-6m ·cmHg,p 为大气压强，单位为厘米汞高。至于油滴匀速下降的速度g v ，可用下法测出：当两极板间的电压V 为零时,设油滴匀速下降的距离为l ，时间为t ，则 g g t l v = (4) 最后得到理论公式： V d pa b t l g q g 2 3 )1(218????? ? ??????+= ηρπ (5) 2. 动态（非平衡）测量法非平衡测量法则是在平行极板上加以适当的电压V ，但并不调节V 使静电力和重力达到平衡，而是使油滴受静电力作用加速上升。由于空气阻力的作

二分搜索实验报告

竭诚为您提供优质文档/双击可除二分搜索实验报告篇一：算法设计与分析二分查找实验报告课程设计说明书设计题目：二分查找程序的实现专业：班级：设计人：山东科技大学年月日课程设计任务书学院：信息科学与工程学院专业：班级：姓名：一、课程设计题目：二分查找程序的实现二、课程设计主要参考资料（1）计算机算法设计与分析（第三版）王晓东著（2）三、课程设计应解决的主要问题（1）二分查找程序的实现（2）（3）四、课程设计相关附件（如：图纸、软件等）：（1）（2）五、任务发出日期：20XX-11-21课程设计完成日期：

20XX-11-24 指导教师签字：系主任签字：指导教师对课程设计的评语成绩：指导教师签字：年月日二分查找程序的实现一、设计目的算法设计与分析是计算机科学与技术专业的软件方向的必修课。同时，算法设计与分析既有较强的理论性，也有较强的实践性。算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。用分治法，设计解决二分查找程序的实现问题的一个简捷的算法。通过解决二分查找程序的实现问题，初步学习分治策略。二、设计要求给定已按升序排好序的n个元素a[0:n-1]，现要在这n 个元素中找出一特定元素x。实现二分搜索的递归程序并进行跟踪分析其执行过程。用顺序搜索方法时，逐个比较a[0:n-1]中的元素，直至找出元素x，或搜索遍整个数组后确定x不在其中。这个方

法没有很好的利用n个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要o(n)次比较。要求二分法的时间复杂度小于o(n)。三、设计说明（一）、需求分析二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用o(logn)时间完成搜索任务。该算法的流程图如下：（二）、概要设计二分查(:二分搜索实验报告)找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果 x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部分继续搜索x。由于二分查找的数组不一定是一个整数数组，所以我采用了c++中的模板函数，将排序函数sort和二分查找函数binarysort写为了模板函数，这样不尽可以查找整数数组，也可以查找小数数组。由于查找的数组的长度不固定，所以我用了c语言中的malloc和realloc函数，首先定义一个数组指针，用malloc 函数该它分配空间，然后向数组中存数，当数组空间满时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以篇二：二分搜索实验报告

检索策略

汽车尾气的排放控制新技术第二部分：检索策略部分 1.课题分析交通系统消耗了全球约1/3 的能源，以石油产品为燃料的汽车是最主要的现代交通运输工具，它给人们带来方便和快捷的同时，也带来了无法回避的问题。根据上个世纪七八十年代美国、日本对城市空气污染源的调查，城市空气中90%以上的一氧化碳、60%以上的碳氢化合物和30%以上的氮氧化物都来自汽车尾气的排放，这些污浊的气体使人类的生存环境受到极大威胁。汽车污染已成为世界性公害，其对于温室气体浓度增加的“贡献”不容忽视。随着世界各国汽车保有量的增加，汽车已成为城市大气质量恶化的主要污染源，其排放的CO、NOx、HC、SO2、Pb 等污染物不仅危害人体健康，还是造成酸雨和光化学烟雾的主要成分，汽车尾气污染已受到全球广泛的注视。截止2006年底，我国民用汽车保有量已接近3700万辆，并仍保持着快速增长的趋势。虽与发达国家相比，其总量不多，但由于主要集中在大城市，而且车况差，燃油质量低，单车的排污量往往高出国外同类车的几倍，汽车尾气对我国城市空气质量造成巨大的威胁。因此，研究汽车尾气的排放控制的新技术，减少有害气体的排放量，对提高城市空气的质量，保障人类生存环境，具有重大意义。本作业利用自己这学期所学的文献检索课的知识，检索了国内有关汽车尾气的排放、控制、净化方面的文献，经初步整理给出一篇肤浅的文献综述，有望老师给予指正。 2. 制定检索策略 2.1 选择检索工具

2.2 选择检索词 2.3 拟定检索式由于不同检索工具的字段不同，因此将检索式（亦称提问式）在“检索步骤及检索结果”的各个具体检索工具中给出。 3. 检索步骤及检索结果 3.1 谷歌搜索引擎 3.1.1 检索式 A．篇名＝汽车 and 尾气 and 排放and 控制 3.1.2 检索步骤与结果打开谷歌高级搜索：在第一行检索框内输入检索式A，“and”用空格形式表示。限定在“简体中文”和“网页标题”内检索。得到212条检索结果。经过筛选，选择其中2条： [1] 【篇名】申城推广燃油清净剂控制汽车尾气排放【摘要】有关研究及开发证明，在燃油中添加合格的清净剂，能明显降低一氧化碳、碳氢化合物、氮氧化物和颗粒物等污染的排放量，而且能使节油率达到15％左右，燃油清净剂技术已成为我国在治理汽车尾气污染的一项高新技术。据了解，目前日本有80％的车用汽油使用汽油清净剂，欧美19个国家普遍使用汽油清净剂。上海目前机动车尾气污染仍十分严重，改善废气排放迫在眉睫。为此许多专家认为，上海应当大力推广燃油清净剂。【出处】解放日报2002年3月27日 [2] 【篇名】控制尾气排放新方法－汽车试“喝”纳米燃油【摘要】普通汽车上通过加装一套EPS纳米燃油装置，就可以节省燃油10%-30%，降低尾气排放约50%-90%，同时还能使动力增加10%-30%。日前，一种可将普通燃油变成纳米燃油

密立根油滴实验报告

近代物理实验报告密立根油滴实验学院数理与信息工程学院班级物理姓名学号时间 2013年12月9日

密立根油滴实验【摘要】本实验我们根据密立根油滴实验原理，引进了CCD摄像技术，从监视器上观察油滴运动，测定了油滴带电量q，并运用差值法处理了相应数据，得出了元电荷e的值，验证了电荷的量子性，同时也了解了密立根巧妙的设计思想，进一步提高了实验技能。【关键词】油滴；平衡态；非平衡态；电荷大小【引言】 1917年密立根设计并完成了密立根油滴实验，其重要意义在于它直接地显示出了电量的量子化，并最早测定了电量的最小单位——基本电荷电量e，即电子所带电量。这一成就大大促进了人们对电和物质结构的研究和认识。油滴实验中将微观量测量转化为宏观量测量的巧妙设想和精确构思，以及用比较简单的仪器，测得比较精确而稳定的结果等都是富有创造性的。由于上述工作，密立根获得了1923年度诺贝尔物理学奖。密立根的实验装置随着技术的进步而得到了不断的改进，但其实验原理至今仍在当代物理科学研究的前沿发挥着作用，例如，科学界用类似的方法测定出基本粒子——夸克的电量。【实验方案】一、实验原理 1、静态（平衡）测量法用喷雾器将油滴喷入两块相距为d的平行极板之间。油在喷射撕裂成油滴时，一般都是带电的。设油滴的质量为m，所带的电量为q，两极板间的电压为V ，如图1 所示。

图1 如果调节两极板间的电压V ，可使两力达到平衡，这时： d V q qE mg == (1) 为了测出油滴所带的电量q ，除了需测定平衡电压V 和极板间距离d 外，还需要测量油滴的质量m 。因m 很小，需用如下特殊方法测定：平行极板不加电压时，油滴受重力作用而加速下降，由于空气阻力的作用，下降一段距离达到某一速度g ν后，阻力r f 与重力mg 平衡，如图 2 所示（空气浮力忽略不计），油滴将匀速下降。此时有： mg v a f g r ==ηπ6 (2) 其中η是空气的粘滞系数，是a 油滴的半径。经过变换及修正，可得斯托克斯定律： pa b v a f g r + = 16ηπ (3) 其中b 是修正常数， b=6.17×10-6m ·cmHg,p 为大气压强，单位为厘米汞高。图2

搜索引擎-第二次实验报告

实验二：实验一、实验目的：根据网络爬虫的基本原理，实现一个简易网络爬虫，需要达到以下指标： 1、种子URL为https://www.doczj.com/doc/b91140917.html,； 2、至少抓取10000个页面； 3、至少完成3轮抓取，每轮给出更新的URL及其数量； 4、实现ＵＲＬ判重，列出每轮爬去时重复的URL数量； 5、数据存放到数据库中，能抽取出网页中的标题、页面生成日期（http协议中的时间），至少包含标题、时间、url、抓取时间、网页正文这几个字段。二、实验方案： 1.爬虫分析与设计我们组应用的是java来写爬虫，我们应用SSM框架将数据库和应用程序连接起来，可以在程序中更简单的进行数据库插入、查询等操作。在对url处理的时候我们用的是Java的URL类，通过这个类可以获得请求头的一些信息，例如编码方式。如何获取url，我们一开始遇到了一些问题，直接解析网页中的ref 标签的时候得到的不全是网页链接，所以转换思路，我们先得到页面中的标签，然后再得到标签里边href中的url，然后再对url进行处理。在处理url的时候，因为网页中的url并不是全部以http开头的，所以在url获取部分，对url的格式进行判断，如果通常格式就进行修改，例如，有的链接是”#”，我们就把开始搜索的url加到它的前边，形成一个正确的url。

图1：应用URL类获取网页内容图2：利用url请求头获取编码信息图3：获取a标签

图4-1：获取url 图4-2：获取url

图5：url判重 2.数据库分析与设计我们设计了两个表，一个是未爬取url表，两一个是已经爬取url表。未爬取的表中村的是搜索判重之后，还没有爬取的url，已爬取的存储爬取到的信息。图6：判重后需要爬取的url表图7：爬取后url信息存储表