最近在看算法的樂(lè)趣揪阿，其中有個(gè)很簡(jiǎn)單的三個(gè)水桶等分8升水的問(wèn)題疗我。
題目：有三個(gè)容積分別是3升、5升南捂、8升的水桶吴裤，其中容積為8升的水桶中裝滿了水，容積為3升和5升的水桶中是空的溺健。三個(gè)水桶都沒有體積刻度麦牺，現(xiàn)在需要將水桶中的8升水等分成兩份，每份都是4升水鞭缭，附加條件是只能使用另外兩個(gè)空桶剖膳，不能借用其他輔助容器。
- 題目是個(gè)經(jīng)典的簡(jiǎn)單問(wèn)題岭辣，書中說(shuō)人腦算很簡(jiǎn)單吱晒，通過(guò)倒水湊出1升水空間就行。但是用計(jì)算機(jī)求解的話就要利用經(jīng)典的狀態(tài)轉(zhuǎn)移和窮舉搜索算法沦童。
簡(jiǎn)單題解:
- 把三個(gè)水桶中的水量作為一個(gè)狀態(tài)仑濒，經(jīng)過(guò)一個(gè)合法動(dòng)作后得到下一個(gè)狀態(tài)（合法動(dòng)作是把A桶中的水全部倒入B桶 或者 把A桶中的水部分倒入B桶使B桶充滿水），遞歸搜索所有的可能狀態(tài)搞动，如果到達(dá)最終狀態(tài)則遞歸停止躏精。
狀態(tài)圖 引用自http://blog.csdn.net/orbit/article/details/6596521
題目的關(guān)鍵：
- 由當(dāng)前狀態(tài)得到所有可能的合法動(dòng)作
- 由合法動(dòng)作得到下一個(gè)狀態(tài)
- 建立一個(gè)狀態(tài)隊(duì)列來(lái)實(shí)現(xiàn)狀態(tài)記錄以及檢查新狀態(tài)是否在隊(duì)列中已經(jīng)出現(xiàn)，避免形成死循環(huán)
- 遞歸搜索鹦肿，在達(dá)到final狀態(tài)時(shí)終止
- 書里只給出了C++的實(shí)現(xiàn)矗烛，在這里用python實(shí)現(xiàn)試試
主要使用的python知識(shí)點(diǎn)：
-
deque隊(duì)列
例如deque.append()#右端插入
deque.pop()#右端刪除 -
列表推導(dǎo)
例如[x*x for x in range(10) if x % 3 == 0]得出10以內(nèi)能被3整除的數(shù)的平方構(gòu)成的列表 -
yield生成器
例如經(jīng)典的斐波那契數(shù)列的生成
def fib(max):
a, b = 1, 1
while a < max:
yield a #generators return an iterator that returns a stream of values.
a, b = b, a+b
for n in fib(15):
print n
踩過(guò)的坑：
- python的引用機(jī)制，即淺復(fù)制機(jī)制，a=b并沒有創(chuàng)建一個(gè)新的對(duì)象而是建立了對(duì)于b對(duì)象的一個(gè)引用瞭吃，對(duì)于a的修改同樣會(huì)改變b碌嘀。犯過(guò)錯(cuò)誤的地方在代碼中有說(shuō)明。可以使用
new_list = list(old_list)和new_deque = deque(old_deque)來(lái)生成新的對(duì)象歪架，實(shí)現(xiàn)深復(fù)制股冗。或者使用copy也行和蚪。 - 在同級(jí)的循環(huán)中止状，即所有下一個(gè)狀態(tài)的同級(jí)遍歷中，進(jìn)入的時(shí)候?qū)﹃?duì)列末尾添加了新狀態(tài)攒霹，退出的時(shí)候一定不要忘記刪除該新狀態(tài)怯疤。雖然很簡(jiǎn)單的邏輯，但是第一次實(shí)現(xiàn)時(shí)確實(shí)忽略了催束，汗集峦。
initial_bucket_state = [0,0,8]
#水桶的初始狀態(tài)
bucket_volume = [3,5,8]
#每個(gè)水桶的對(duì)應(yīng)的容積
from collections import deque
record = deque()
record.append(initial_bucket_state)
#利用python的deque隊(duì)列記錄狀態(tài)轉(zhuǎn)移情況，初始化時(shí)加入水桶初始狀態(tài)抠刺。deque是可以從頭尾插入和刪除的隊(duì)列塔淤，在不指定大小時(shí)，為一個(gè)無(wú)邊界的隊(duì)列
def nextStateLawful(current_state, bucket_volume):
next_action = [
(from_, to_)
for from_ in range(3) for to_ in range(3)
if from_ != to_
and current_state[from_] > 0
and current_state[to_] < bucket_volume[to_]
]
#通過(guò)列表推導(dǎo)式獲得下一動(dòng)作的二元組構(gòu)成的列表速妖，由（倒出水的容器編號(hào)高蜂，倒入水的容器編號(hào)）組成。
#二重循環(huán)得到下一步的所有可能動(dòng)作买优，然后通過(guò)
##1.倒入倒出不能為同一個(gè)2.倒出的捅中必須有水3.倒入的桶中不能為滿 的條件判斷是否合法
for from_, to_ in next_action:
#next_state = current_state #淺復(fù)制造成錯(cuò)誤
next_state = list(current_state)
if current_state[from_] + current_state[to_] > bucket_volume[to_]:
next_state[from_] -= (bucket_volume[to_] - current_state[to_])
next_state[to_] = bucket_volume[to_]
else:
next_state[from_] = 0
next_state[to_] = current_state[to_] + current_state[from_]
yield next_state
#再由所有可能的合法動(dòng)作得出所有的下一個(gè)狀態(tài)妨马，通過(guò)yield產(chǎn)生供其它函數(shù)調(diào)用挺举。
num = 0
record_list = []
#記錄調(diào)試的變量：num表示總共實(shí)現(xiàn)方法數(shù)杀赢，record_list記錄所有實(shí)現(xiàn)路徑
def searchResult(record, bucket_volume=[3,5,8], final_bucket_state=[0,4,4]):
global num，record_list
current_state = record[-1]
#由record的末尾元素得到當(dāng)前水桶狀態(tài)
next_state = nextStateLawful(current_state, bucket_volume)
#得到關(guān)于當(dāng)前狀態(tài)的下一狀態(tài)的可迭代生成器湘纵，供下一步循環(huán)使用
for state in next_state:
#遍歷所有可能的下一狀態(tài)
if state not in record:
#保證當(dāng)前狀態(tài)沒在以前出現(xiàn)過(guò)脂崔。如果狀態(tài)已經(jīng)出現(xiàn)還進(jìn)行搜索就會(huì)形成狀態(tài)環(huán)路，陷入死循環(huán)梧喷。
record.append(state)
#添加新的狀態(tài)到列表中
if state == final_bucket_state:
print(record)
#打印出可行方案
#record_list.append(record)這樣使用錯(cuò)誤砌左，導(dǎo)致加入列表的是record的引用，應(yīng)該使用下面的式子來(lái)進(jìn)行深復(fù)制铺敌，得到一個(gè)新的隊(duì)列再加入列表汇歹。
record_list.append(deque(record))
num += 1
else:
searchResult(record, bucket_volume, final_bucket_state)
#不是最終狀態(tài)則遞歸搜索
record.pop()
#去除當(dāng)前循環(huán)中添加的狀態(tài)，進(jìn)入下一個(gè)循環(huán)偿凭，關(guān)鍵步产弹，第一次實(shí)現(xiàn)的時(shí)候遺漏了
if __name__=='__main__':
searchResult(record)
#開始
print(num)
#打印所有方案的數(shù)量
print(min([len(i) for i in record_list]))
#打印最短路徑方案中的狀態(tài)總數(shù)
