分油问题
-、问题描述
分油问题:两个小孩去打油,一人带了一个一斤的空瓶,另一个带了一个七两和一个三两的空瓶。原计划各打一斤油,可是由于所带的钱不够,只好合打了一斤油,在回家的路上,二人想平分这一斤油,可是又没有其它工具。现只用这三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。
二、算法描述
F 算法选择
通过分析题目并结合深度优先、广度优先和迭代加深搜索的算法的特点以及有缺点,这里选择广度优先算法来求解该分油问题。如果采用深度优先算法搜索,由于其盲目性导致搜索陷入局部陷阱,并不一定能求得解即使得到解也不一定是最优解,因此并不采用此算法。迭代加深搜索则是在固定的深度上进行深度和广度搜索结合的策略来进行搜索,这样避免了单一的深度搜索无法得到解的缺点,但是找到的解并不一定是最优解。广度优先以牺牲空间代价和时间代价来换取保证取得最优解。由于该问题并不复杂,即使使用广度优先算法也不会占有太多的空间和时间,因此为了取得最优解这里选择广度优先算法来求解。
F 算法描述
1. 用unVisitedBttsArr表示初始节点列表(待扩展,此为一个动态数组)
2. 如果unVisitedBttsArr为空集,则退出并给出失败信号
3. n取为unVisitedBttsArr的第一个节点,并在 unVisitedBttsArr中删除节点n,放入已访问节点列表haveVisitedBttsArr
4. 如果n为目标节点,则退出并给出成功信号
5. 否则,将n的子节点加到N的末尾,并返回2)步
F 问题分析
l 选择合适的数据结构表示问题状态
F 用向量(T,S,R)表示状态——T表示10两瓶中的油量,S表示7两瓶中的油量,R表示3两瓶中的油量。
F 问题的起始状态:(10,0,0)。
F 问题的目标状态:(5,2,3)或者(5,3,2)或者(5,5,0)。
l 确定智能算子,用以表示变化状态的规则。由于总共油量为10两,而10两的瓶可以装满所有的油,因此可以把10两的瓶当作一个大油桶,这样此题就化为和上一题8/6类似的问题了。因此在描述变化状态的时候只需给出7、3瓶的状态即可,10瓶的状态即为10-S-R的油量。可是由于在程序处理上的一致性,在程序的实现上我还是把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<7 and 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斤瓶子
三、程序设计
算法使用C#语言来实现的。程序主要根据上面提供的广度优先算法的描述来对算法进行实现的。程序共有四个类:
Bottle类,用来描述瓶子的状态以及一些行为动作和属性。
WidthSearch类,是广度优先搜索算法的实现类
DepthSearch类,是深度优先搜索算法的实现类
MainForm类,是界面设计的类。
这里提供两个算法的实现主要是为了做个对比。
以下主要对几个核心算法的程序实现进行说明介绍。
//瓶子类
public class Bottle
{
int Capability = 0 ;//瓶子的总容量
int Current = 0 ;//当前瓶子中的油量
int Remain = 0 ;//瓶子中剩余的量
//倒入油的行为动作
public void Add(int val)
{
Current += val;
Remain -= val;
}
//倒出油的行为动作
public void Sub(int val)
{
Current -= val;
Remain += val;
}
//深度优先算法实现类
public class DepthSearch
public void Searching()
{
Random r = new Random();
while(bottle_10.CurrentVal != 5) //判断是否达到目标状态
{
int random = r.Next(1,7);//用随机产生的数来随机确定下一个子状态
switch(random)
{
case 1 :
FlowTo(bottle_03,bottle_07);
break;
case 2 :
FlowTo(bottle_10,bottle_03);
break;
case 3 :
FlowTo(bottle_07,bottle_03);
break;
case 4 :
FlowTo(bottle_10,bottle_07);
break;
case 5 :
FlowTo(bottle_03,bottle_10);
break;
case 6 :
FlowTo(bottle_07,bottle_10);
break;
default :
break;
}
if(!stateArr.Contains(BottlesState()))
{
stateArr.Add(BottlesState());
}
else
{
ReturnToPreState();
}
}
}
//倒油的动作。这里是从bottle1倒到bottle2
private void FlowTo(Bottle bottle1,Bottle bottle2)
{
if(bottle1.CurrentVal>bottle2.RemainVal)
{
bottle1.Sub(bottle2.RemainVal);
bottle2.CurrentVal = bottle2.CapabilityVal;
}
else
{
bottle2.Add(bottle1.CurrentVal);
bottle1.CurrentVal = 0;
}
}
//广度优先搜索实现类
public class WidthSearch
public void S(TreeNode node)
{
while(unVisitedBttsArr.Count>=0) //未访问表中如果有结点继续循环搜索否则跳出
{
TreeNode n = (TreeNode)unVisitedBttsArr[0];
bool flag = true;
//检查是否已经访问过
foreach(TreeNode i in haveVisitedBttsArr)
{
if(i.Text.Equals(n.Text))
{
haveVisitedBttsArr.Add(unVisitedBttsArr[0]);
unVisitedBttsArr.RemoveAt(0);
flag = false;
break;
}
}
//若已经遍历过的不需要继续遍历 跳到下一个
if(flag)
{
if(Search(n))
{
return;
}
}
}
}
//创建子结点并加入到unVisitedBttsArr中。
private bool CreateNode(TreeNode node)
{
TreeNode n = new TreeNode(BottlesState());
unVisitedBttsArr.Add(n);
if(bottle_10.CurrentVal == 5)
{
node.Nodes.Add(n);
SetPath(n);
return true;
}
node.Nodes.Add(n);
return false;
}
//回溯取得最佳路径
private void SetPath(TreeNode n)
{
while(n.Parent!=null)
{
path = n.Text + " -> " + path;
n.ForeColor = System.Drawing.Color.Blue;
n = n.Parent;
}
}
四、试验结果
如下是试验结果:
1)深度优先随机产生子结点的搜索路径
2)广度优先算法实现图
从以上两个结果来看,如果存在解则广度优先总能找到最优解,但是从时间上来看深度优先更快而广度优先需要遍历每个结点造成时间空间都开销比较大,所以时间上肯定花的比较多。但是可以保证找到最优解。此问题由于比较简单,复杂度不高,只需在第九步就可以找到最优解了,因此深度优先是可取的,但是如果是在某些复杂的问题中,此算法就可能导致组合爆炸,占用空间过大导致算法的不可行。
分享到:
相关推荐
通过广度优先遍历、深度优先遍历实现 开发工具:C#
BFS #DFS C#上的广度优先搜索和深度优先搜索算法
深度优先搜索(亦称深度优先遍历,Deep First Search,简称DFS),广度优先搜索(亦称广度优先遍历,Breadth First Search,简称BFS)都是很基础的算法,也是大家很熟悉的。算法,又叫宽度优先遍历,或横向优先遍历...
这是一个关于八数码问题的广度和深度优先搜索方法 希望能给你大家学习数据结构时带来帮助!!!
C#,图论与图算法,有向图(Direct Graph)广度优先遍历(BFS,Breadth First Search)算法与源程序 图的广度优先遍历(或搜索)类似于树的广度优先遍历(参见本文的方法2)。这里唯一需要注意的是,与树不同,图...
用C#做的程序,用两种不同的算法解八数码问题,现与大家分享
八数码问题,用广度优先和深度优先算法实现。并且用mfc实现界面,让结果算法运行过程以动画显示。并附上实验报告.zip
常用的树(或图)遍历算法是两种: 广度优先搜索算法(BFS) 和 深度优先搜索算法(DFS)。然而在遇到巨大高度和宽度的树(或图)时,BFS 和 DFS 都不是非常有效。因为: (1)DFS首先遍历通过根的一个相邻节点,然后...
八数码问题(使用c#编写),使用了深度与广度优先搜索,没有使用A*算法,这个小程序可以帮助大家学习。特别是刚接触人工智能的。
这是C#版的数据结构与算法的代码实现,包括:顺序表,单链表,双链表;...用邻接矩阵解决图的编程问题,用邻接表解决图的编程问题,图的遍历(深度优先,广度优先),Dijkstra最短路径算法;冒泡排序,快速排序
uPath 在2D环境中使用深度优先搜索,广度优先搜索和启发式搜索(A *)进行Unity的寻路。
校园导游系统的设计与实现 关于数据结构 图的应用,实现图的深度优先遍历,广度优先遍历,最小生成树,最短路径等功能的完整C#源代码 有注释,帮助理解。
使用Unity3D和C#开发的迷宫生成和寻路“玩具”。 实现生成算法和寻路算法的可视化过程。 生成算法:1.深度优先 2.随机Prim 3.四叉树(递归分割) 寻路算法:1.深度优先 2.广度优先 3.双向广度优先 4.A*算法
在抓取网页的时候,网络爬虫一般有两种策略(即两种搜索方法),广度优先和深度优先。 广度优先:是指网络爬虫会先抓取起始网页中链接的所有网页,然后再选择其中的一个链接网页,继续抓取在此页面中链接的所有页面...
本程序是用C#语言编写需要.netframework支持 没.net环境的,只需安装 /可执行文件2005Maze/dotnetfx.exe 即可 ...1.广度优先搜索 2.深度优先搜索 3.A*搜索 第三菜单项: 1.退出程序; 2.关于作者
手写网络爬虫 能抓取网页 广度优先 可设置深度 vs2008测试 能进行网页提取 内容提取 标题提取 meta提取 server数据入库 欢迎参考 有好的建议请发送邮件blackjunes@sina.com
分别使用广度优先搜索、深度优先搜索和 A*算法实现重排九宫格问题; 使用的搜索方式可在程序内修改; 可以自行输入初始状态和目标状态 可以选择是否展示具体搜索步骤; 程序输出在该搜索方法下的最佳路径以及使用该...
Python实作有向图(邻接表) 加权图(邻接表)遍历广度优先搜索深度优先搜索最短路径广度优先搜索最短路径(有向图) Dikstra的最短路径(加权图) 贝尔曼·福特的最短路径(加权图) 优化的Bellman Ford的最短路径...