分享
 
 
 

深度和广度优先分油问题(C#实现)

王朝c#·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

分油问题

-、问题描述

分油问题:两个小孩去打油,一人带了一个一斤的空瓶,另一个带了一个七两和一个三两的空瓶。原计划各打一斤油,可是由于所带的钱不够,只好合打了一斤油,在回家的路上,二人想平分这一斤油,可是又没有其它工具。现只用这三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。

二、算法描述

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)广度优先算法实现图

从以上两个结果来看,如果存在解则广度优先总能找到最优解,但是从时间上来看深度优先更快而广度优先需要遍历每个结点造成时间空间都开销比较大,所以时间上肯定花的比较多。但是可以保证找到最优解。此问题由于比较简单,复杂度不高,只需在第九步就可以找到最优解了,因此深度优先是可取的,但是如果是在某些复杂的问题中,此算法就可能导致组合爆炸,占用空间过大导致算法的不可行。

请指点。要源程序的可email给我,代码没有优化。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有