分油問題
－、問題描述
分油問題：兩個小孩去打油，一人帶了一個一斤的空瓶，另一個帶了一個七兩和一個三兩的空瓶。原計劃各打一斤油，可是由於所帶的錢不夠，只好合打了一斤油，在回家的路上，二人想平分這一斤油，可是又沒有其它工具。現只用這三個瓶子(一斤、七兩、三兩)精確地分出兩個半斤油來。
二、算法描述
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給我，代碼沒有優化。
