1.問題描述
小孩分油問題
兩個小孩去打油，一人帶了一個一斤的空瓶，另一個帶了一個七兩、一個三兩的空瓶。原計劃各打一斤油，可是由于所帶的錢不夠，隻好兩人合打了一斤油，在回家的路上，兩人想平分這一斤油，可是又沒有其它工具。試僅用三個瓶子(一斤、七兩、三兩)精确地分出兩個半斤油來。
2.算法設計
令狀态R、E、S分别表示十兩、七兩和三兩的瓶子中所裝的油量。如問題所述，初始時有（R,E,S）=（10，0，0），問題要求即僅通過這三個瓶子，将油量狀态轉變為（R,E,S）=（5，5，0）。
該問題較為特殊，我們發現七兩的瓶子和三兩的瓶子所能裝的油的總量恰好為十兩。是以，我們可以将十兩的瓶子等同于一個無窮大的油桶，任何時候七兩和三兩的瓶子都可以通過這個油桶裝滿或倒空油。在這個假設下，原問題即被簡化為：初始狀态（E、S）=（0，0），要求僅通過這兩個瓶子，将狀态轉變為（E、S）=（5，0）。在這個目标狀态下，十兩的瓶子中自然裝了五兩油。
将兩個瓶子的狀态轉變以及對應的規則清單如下：
| 規則号 | 規則 | 解釋 |
| 1 | (E,S) and E<7 → (7,S) | 7兩瓶不滿時裝滿 |
| 2 | (E,S) and S<3 → (E,3) | 3兩瓶不滿時裝滿 |
| 3 | (E,S) and E>0 → (0,S) | 7兩瓶不空時倒空 |
| 4 | (E,S) and S>0 → (E,0) | 3兩瓶不空時倒空 |
| 5 | (E,S) and E>0 and E+S≤3 → (0,E+S) | 37兩瓶中油全倒入3兩瓶 |
| 6 | (E,S) and S>0 and E+S≤7 → (E+S,0) | 3兩瓶中油全倒入7兩瓶 |
| 7 | (E,S) and S<3 and E+S≥3 → (E+S-3,3) | 用7兩瓶油裝滿3兩瓶子 |
| 8 | (E,S) and E<7 and E+S≥7 → (7,E+S-7) | 用3兩瓶油裝滿7兩瓶子 |
在每個狀态（E，S）下，我們均可以通過判斷E、S的值來選擇上述若幹條規則進行狀态轉變。整個狀态空間構成了一顆樹，樹根是初始狀态（R，S）=（0，0）,目标狀态（R，S）=（5，0）則可能位于某些節點中。
因為該問題的狀态空間較小，最多不超過（7*3=21）種狀态，是以在實驗中我們采用深度搜尋的方法對問題進行求解。此外，為了避免對已經搜尋過的狀态重複搜尋，程式中定義了一個數組，用于存儲已經搜尋過的狀态，僅有當目前狀态沒有在該數組中出現過時，算法才對其進行搜尋，并将該狀态放入數組中。
3.程式流程
4.核心僞代碼
function isVisited(E, S): 狀态(E, S)是否搜尋過，沒有則将其入棧并标記已搜尋。
初始狀态(E, S) = (0, 0)，并存入棧Stack
while 棧Stack不為空：
取出棧頂元素(E, S)，并輸出
If (E, S) == (5, 0), then
分油成功，break;
if E < 7, then:
(E, S) = (7, S), isVisited(E, S)
if E < 3, then:
(E, S) = (E, 3), isVisited(E, S)
if E > 0, then:
(E, S) = (0, S), isVisited(E, S)
if S > 0, then:
(E, S) = (E, 0), isVisited(E, S)
if E > 0 and E+S <= 3, then:
(E, S) = (0, E+S), isVisited(E, S)
if S > 0 and E+S <= 7, then:
(E, S) = (E+S, 0), isVisited(E, S)
if S < 3 and E+S >= 3, then:
(E, S) = (7, S), isVisited(E+S-3, 3)
if E < 7 and E+S >= 7, then:
(E, S) = (7, S), isVisited(7, E+S-7)
end
5.代碼運作及測試
算法運作結果如下所示，經過10次操作後，準确得将油劃分為兩個五兩。
6.結論
本實驗是對狀态空間采用深搜的方法實作的。程式中設定了輔助數組用于儲存已經搜尋過的狀态，且該問題的狀态空間很小，是以深搜不會出現無窮解的情況。隻要目标狀态設定合理且存在，深搜一定能在有限的步驟裡求得。但是在小孩分油問題中，深搜所得結果不一定為最優，廣搜下得到的結果才是最優結果。但是由于深搜易于實作且速度快，是以實驗中才選擇深搜去實作。
本實驗源碼具有較強的擴充性，隻要初始狀态和目标狀态設定合理，程式均可以成功将其狀态轉換過程輸出。
7.源碼
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
struct State {
int E; // 七兩的瓶子
int S; // 三兩的瓶子
State(int E, int S) {
this->E = E;
this->S = S;
}
};
// 深搜輔助棧
stack<State> Stack;
// 存儲已經出現過的狀态
vector<State> visited;
// 查詢狀态s先前是否出現過
bool isVisited(State s) {
vector<State>::iterator it;
for (it = visited.begin(); it != visited.end(); it++) {
if (it->E == s.E && it->S == s.S) return true;
}
return false;
}
// 倒油行為，狀态轉變
void move(State s) {
// 查詢目前狀态先前是否通路過
if (!isVisited(s)) {
visited.push_back(s);
Stack.push(s);
}
}
int main() {
int E = 0, S = 0;
int fE = 5, fS = 0;
cout<<"Please input the initial oil of bottles："<<endl;
cin>>E>>S;
cout<<"Please input the final oil of bottles："<<endl;
cin>>fE>>fS;
Stack.push(State(E, S));
while(!Stack.empty()) {
State cur = Stack.top(); Stack.pop();
E = cur.E;
S = cur.S;
cout<<10 - E - S<<" "<<E<<" "<<S<<endl;
// 到達目标狀态
if (E == fE && S == fS) {
cout<<"Successfully reach the target state:("<<fE<<", "<<fS<<")!";
return 0;
}
// 将七兩的瓶子裝滿
if (E < 7) move(State(7, S));
// 将三兩的瓶子裝滿
if (S < 3) move(State(E, 3));
// 将七兩的瓶子倒空
if (E > 0) move(State(0, S));
// 将三兩的瓶子倒空
if (S > 0) move(State(E, 0));
// 将七兩的瓶子全部裝到三兩的瓶子上
if (E > 0 && E + S <= 3) move(State(0, E + S));
// 将三兩的瓶子全部裝到七兩的瓶子上
if (S > 0 && E + S <= 7) move(State(E + S, 0));
// 用七兩的瓶子将三兩的瓶子裝滿
if (S < 3 && E + S >= 3) move(State(E + S - 3, 3));
// 用三兩的瓶子将七兩的瓶子裝滿
if (E < 7 && E + S >= 7) move(State(7, E + S - 7));
}
cout<<"Algorithm cannot find a solution!"<<endl;
return 0;
}