深度和广度优先分油问题（C＃实现）

显示全部楼层 · 2011-4-11 10:37:51

分油问题<?xml:namespace prefix = o ns = \"urn:schemas-microsoft-com:office:office\" /><o:p></o:p>
－、问题描述<o:p></o:p>
分油问题：两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两和一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好合打了一斤油，在回家的路上，二人想平分这一斤油，可是又没有其它工具。现只用这三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。<o:p></o:p>
二、算法描述<o:p></o:p>
F 算法选择<o:p></o:p>
通过分析题目并结合深度优先、广度优先和迭代加深搜索的算法的特点以及有缺点，这里选择广度优先算法来求解该分油问题。如果采用深度优先算法搜索，由于其盲目性导致搜索陷入局部陷阱，并不一定能求得解即使得到解也不一定是最优解，因此并不采用此算法。迭代加深搜索则是在固定的深度上进行深度和广度搜索结合的策略来进行搜索，这样避免了单一的深度搜索无法得到解的缺点，但是找到的解并不一定是最优解。广度优先以牺牲空间代价和时间代价来换取保证取得最优解。由于该问题并不复杂，即使使用广度优先算法也不会占有太多的空间和时间，因此为了取得最优解这里选择广度优先算法来求解。<o:p></o:p>
F 算法描述<o:p></o:p>
1. 用unVisitedBttsArr表示初始节点列表(待扩展，此为一个动态数组)<o:p></o:p>
2. 如果unVisitedBttsArr为空集，则退出并给出失败信号<o:p></o:p>
3. n取为unVisitedBttsArr的第一个节点，并在 unVisitedBttsArr中删除节点n，放入已访问节点列表haveVisitedBttsArr<o:p></o:p>
4. 如果n为目标节点，则退出并给出成功信号<o:p></o:p>
5. 否则，将n的子节点加到N的末尾，并返回2)步<o:p></o:p>
F 问题分析<o:p></o:p>
l 选择合适的数据结构表示问题状态<o:p></o:p>
F 用向量(T，S，R)表示状态T表示10两瓶中的油量，S表示7两瓶中的油量，R表示3两瓶中的油量。<o:p></o:p>
F 问题的起始状态：(10，0，0)。<o:p></o:p>
F 问题的目标状态：(5，2，3)或者(5，3，2)或者(5，5，0)。<o:p></o:p>
l 确定智能算子，用以表示变化状态的规则。由于总共油量为10两，而10两的瓶可以装满所有的油，因此可以把10两的瓶当作一个大油桶，这样此题就化为和上一题8/6类似的问题了。因此在描述变化状态的时候只需给出7、3瓶的状态即可，10瓶的状态即为10－S－R的油量。可是由于在程序处理上的一致性，在程序的实现上我还是把10、8、6的瓶子统一处理，而不是用两个状态表示。<o:p></o:p>
号<o:p></o:p>
规则<o:p></o:p>
解释<o:p></o:p>
1<o:p></o:p>
(S,R) and S7 (7,R)<o:p></o:p>
7斤瓶不满时装满<o:p></o:p>
2<o:p></o:p>
(S,R) and R 3 (S,3)<o:p></o:p>
3斤瓶不满时装满<o:p></o:p>
3<o:p></o:p>
(S,R) and S 0 (0,R)<o:p></o:p>
7斤瓶不空时倒空<o:p></o:p>
4<o:p></o:p>
(S,R) and R 0 (S,0)<o:p></o:p>
3斤瓶不空时倒空<o:p></o:p>
5<o:p></o:p>
(S,R) and S0 and S R≤3 (0,S R)<o:p></o:p>
7斤瓶中油全倒入3斤瓶<o:p></o:p>
6<o:p></o:p>
(S,R) and R 0 and S R≤7 (S R,0)<o:p></o:p>
3斤瓶中油全倒入7斤瓶<o:p></o:p>
7<o:p></o:p>
(S,R) and S7 and S R≥7 (7, S R -7)<o:p></o:p>
用3斤瓶油装满7斤瓶子<o:p></o:p>
8<o:p></o:p>
(S,R) and R 3 and S R≥3 (S R -3,3)<o:p></o:p>
用7斤瓶油装满3斤瓶子<o:p></o:p>
三、程序设计<o:p></o:p>
算法使用C＃语言来实现的。程序主要根据上面提供的广度优先算法的描述来对算法进行实现的。程序共有四个类：<o:p></o:p>
Bottle类，用来描述瓶子的状态以及一些行为动作和属性。<o:p></o:p>
WidthSearch类，是广度优先搜索算法的实现类<o:p></o:p>
DepthSearch类，是深度优先搜索算法的实现类<o:p></o:p>
MainForm类，是界面设计的类。<o:p></o:p>
这里提供两个算法的实现主要是为了做个对比。<o:p></o:p>
以下主要对几个核心算法的程序实现进行说明介绍。<o:p></o:p>
 //瓶子类<o:p></o:p>
public class Bottle<o:p></o:p>
 {<o:p></o:p>
 int Capability = 0 ;//瓶子的总容量<o:p></o:p>
 int Current = 0 ;//当前瓶子中的油量<o:p></o:p>
 int Remain = 0 ;//瓶子中剩余的量<o:p></o:p>
 <o:p></o:p>
 //倒入油的行为动作<o:p></o:p>
 public void Add(int val)<o:p></o:p>
 {<o:p></o:p>
 Current= val;<o:p></o:p>
 Remain -= val;<o:p></o:p>
 }<o:p></o:p>
 //倒出油的行为动作<o:p></o:p>
 public void Sub(int val)<o:p></o:p>
 {<o:p></o:p>
 Current -= val;<o:p></o:p>
 Remain= val;<o:p></o:p>
 }<o:p></o:p>
<o:p></o:p>
 //深度优先算法实现类<o:p></o:p>
 public class DepthSearch<o:p></o:p>
 public void Searching()<o:p></o:p>
 {<o:p></o:p>
 Random r = new Random(); <o:p></o:p>
<o:p></o:p>
 while(bottle_10.CurrentVal != 5) //判断是否达到目标状态<o:p></o:p>
 { <o:p></o:p>
 int random = r.Next(1,7);//用随机产生的数来随机确定下一个子状态<o:p></o:p>
<o:p></o:p>
 switch(random)<o:p></o:p>
 {<o:p></o:p>
 case 1 : <o:p></o:p>
 FlowTo(bottle_03,bottle_07);<o:p></o:p>
 break;<o:p></o:p>
 case 2 :<o:p></o:p>
 FlowTo(bottle_10,bottle_03);<o:p></o:p>
 break;<o:p></o:p>
 case 3 :<o:p></o:p>
 FlowTo(bottle_07,bottle_03);<o:p></o:p>
 break;<o:p></o:p>
 case 4 :<o:p></o:p>
 FlowTo(bottle_10,bottle_07);<o:p></o:p>
 break;<o:p></o:p>
 case 5 :<o:p></o:p>
 FlowTo(bottle_03,bottle_10);<o:p></o:p>
 break;<o:p></o:p>
 case 6 :<o:p></o:p>
 FlowTo(bottle_07,bottle_10);<o:p></o:p>
 break; <o:p></o:p>
 default :<o:p></o:p>
 break;<o:p></o:p>
 }<o:p></o:p>
 if(!stateArr.Contains(BottlesState()))<o:p></o:p>
 {<o:p></o:p>
 stateArr.Add(BottlesState());<o:p></o:p>
 }<o:p></o:p>
 else<o:p></o:p>
 {<o:p></o:p>
 ReturnToPreState();<o:p></o:p>
 }<o:p></o:p>
<o:p></o:p>
 }<o:p></o:p>
 }<o:p></o:p>
<o:p></o:p>
 //倒油的动作。这里是从bottle1倒到bottle2<o:p></o:p>
 private void FlowTo(Bottle bottle1,Bottle bottle2)<o:p></o:p>
 {<o:p></o:p>
 if(bottle1.CurrentValbottle2.RemainVal)<o:p></o:p>
 {<o:p></o:p>
 bottle1.Sub(bottle2.RemainVal);<o:p></o:p>
 bottle2.CurrentVal = bottle2.CapabilityVal;<o:p></o:p>
 }<o:p></o:p>
 else<o:p></o:p>
 {<o:p></o:p>
 bottle2.Add(bottle1.CurrentVal);<o:p></o:p>
 bottle1.CurrentVal = 0;<o:p></o:p>
 } <o:p></o:p>
 }<o:p></o:p>
<o:p></o:p>
 //广度优先搜索实现类<o:p></o:p>
 public class WidthSearch<o:p></o:p>
 public void S(TreeNode node)<o:p></o:p>
 { <o:p></o:p>
 while(unVisitedBttsArr.Count=0) //未访问表中如果有结点继续循环搜索否则跳出<o:p></o:p>
 {<o:p></o:p>
<o:p></o:p>
 TreeNode n = (TreeNode)unVisitedBttsArr[0];<o:p></o:p>
<o:p></o:p>
 bool flag = true;<o:p></o:p>
<o:p></o:p>
 //检查是否已经访问过<o:p></o:p>
 foreach(TreeNode i in haveVisitedBttsArr)<o:p></o:p>
 {<o:p></o:p>
 if(i.Text.Equals(n.Text))<o:p></o:p>
 {<o:p></o:p>
 haveVisitedBttsArr.Add(unVisitedBttsArr[0]);<o:p></o:p>
<o:p></o:p>
 unVisitedBttsArr.RemoveAt(0);<o:p></o:p>
<o:p></o:p>
 flag = false;<o:p></o:p>
 break;<o:p></o:p>
 }<o:p></o:p>
 }<o:p></o:p>
<o:p></o:p>
 //若已经遍历过的不需要继续遍历跳到下一个<o:p></o:p>
 if(flag)<o:p></o:p>
 {<o:p></o:p>
 if(Search(n))<o:p></o:p>
 {<o:p></o:p>
 return; <o:p></o:p>
 } <o:p></o:p>
 }<o:p></o:p>
 <o:p></o:p>
 }<o:p></o:p>
 }<o:p></o:p>
 //创建子结点并加入到unVisitedBttsArr中。<o:p></o:p>
 private bool CreateNode(TreeNode node)<o:p></o:p>
 {<o:p></o:p>
 TreeNode n = new TreeNode(BottlesState());<o:p></o:p>
<o:p></o:p>
 unVisitedBttsArr.Add(n);<o:p></o:p>
<o:p></o:p>
 if(bottle_10.CurrentVal == 5)<o:p></o:p>
 {<o:p></o:p>
 node.Nodes.Add(n);<o:p></o:p>
 <o:p></o:p>
 SetPath(n);<o:p></o:p>
<o:p></o:p>
 return true;<o:p></o:p>
 } <o:p></o:p>
<o:p></o:p>
 node.Nodes.Add(n);<o:p></o:p>
<o:p></o:p>
 return false;<o:p></o:p>
 }<o:p></o:p>
 //回溯取得最佳路径<o:p></o:p>
 private void SetPath(TreeNode n)<o:p></o:p>
 {<o:p></o:p>
 while(n.Parent!=null)<o:p></o:p>
 {<o:p></o:p>
 path = n.Text \" - \" path;<o:p></o:p>
 n.ForeColor = System.Drawing.Color.Blue;<o:p></o:p>
 n = n.Parent;<o:p></o:p>
 }<o:p></o:p>
 }<o:p></o:p>
<o:p></o:p>
<o:p></o:p>
四、试验结果<o:p></o:p>
如下是试验结果：<o:p></o:p>
1）深度优先随机产生子结点的搜索路径<o:p></o:p>
<?xml:namespace prefix = v ns = \"urn:schemas-microsoft-com:vml\" /><v:shapetype id=_x0000_t75 stroked=\"f\" filled=\"f\" path=\"m@4@5l@4@11@9@11@9@5xe\" o:preferrelative=\"t\" o:spt=\"75\" coordsize=\"21600,21600\"><v:stroke joinstyle=\"miter\"></v:stroke><v:formulas><v:f eqn=\"if lineDrawn pixelLineWidth 0\"></v:f><v:f eqn=\"sum @0 1 0\"></v:f><v:f eqn=\"sum 0 0 @1\"></v:f><v:f eqn=\"prod @2 1 2\"></v:f><v:f eqn=\"prod @3 21600 pixelWidth\"></v:f><v:f eqn=\"prod @3 21600 pixelHeight\"></v:f><v:f eqn=\"sum @0 0 1\"></v:f><v:f eqn=\"prod @6 1 2\"></v:f><v:f eqn=\"prod @7 21600 pixelWidth\"></v:f><v:f eqn=\"sum @8 21600 0\"></v:f><v:f eqn=\"prod @7 21600 pixelHeight\"></v:f><v:f eqn=\"sum @10 21600 0\"></v:f></v:formulas><v:path o:connecttype=\"rect\" gradientshapeok=\"t\" o:extrusionok=\"f\"></v:path><o:lock aspectratio=\"t\" v:ext=\"edit\"></o:lock></v:shapetype><o:p></o:p>
<o:p><img height=551 src=\"http://www.newasp.net/tech/UploadPic/2005-6/20051126173037208.jpg\" width=616 border=0 onload=\"return imgzoom(this,550);\" onclick=\"javascript:window.open(this.src);\" style=\"cursor:pointer;\"/></o:p>
<o:p></o:p>
2）广度优先算法实现图 <o:p></o:p>
<o:p></o:p>
<o:p><img height=551 src=\"http://www.newasp.net/tech/UploadPic/2005-6/20051126173038373.jpg\" width=616 border=0 onload=\"return imgzoom(this,550);\" onclick=\"javascript:window.open(this.src);\" style=\"cursor:pointer;\"/></o:p>
从以上两个结果来看，如果存在解则广度优先总能找到最优解，但是从时间上来看深度优先更快而广度优先需要遍历每个结点造成时间空间都开销比较大，所以时间上肯定花的比较多。但是可以保证找到最优解。此问题由于比较简单，复杂度不高，只需在第九步就可以找到最优解了，因此深度优先是可取的，但是如果是在某些复杂的问题中，此算法就可能导致组合爆炸，占用空间过大导致算法的不可行。 <o:p> 请指点。要源程序的可email给我，代码没有优化。 </o:p>