三个水桶等分8升水问题python实现--穷举、简单状态转移与递
2016-08-05 本文已影响532人
treelake
最近在看算法的乐趣，其中有个很简单的三个水桶等分8升水的问题。
题目：有三个容积分别是3升、5升、8升的水桶，其中容积为8升的水桶中装满了水，容积为3升和5升的水桶中是空的。三个水桶都没有体积刻度，现在需要将水桶中的8升水等分成两份，每份都是4升水，附加条件是只能使用另外两个空桶，不能借用其他辅助容器。
- 题目是个经典的简单问题，书中说人脑算很简单，通过倒水凑出1升水空间就行。但是用计算机求解的话就要利用经典的状态转移和穷举搜索算法。
简单题解:
- 把三个水桶中的水量作为一个状态，经过一个合法动作后得到下一个状态（合法动作是把A桶中的水全部倒入B桶 或者 把A桶中的水部分倒入B桶使B桶充满水），递归搜索所有的可能状态，如果到达最终状态则递归停止。
状态图 引用自http://blog.csdn.net/orbit/article/details/6596521
题目的关键：
- 由当前状态得到所有可能的合法动作
- 由合法动作得到下一个状态
- 建立一个状态队列来实现状态记录以及检查新状态是否在队列中已经出现，避免形成死循环
- 递归搜索，在达到final状态时终止
- 书里只给出了C++的实现，在这里用python实现试试
主要使用的python知识点：
-
deque队列
例如deque.append()#右端插入
deque.pop()#右端删除 -
列表推导
例如[x*x for x in range(10) if x % 3 == 0]得出10以内能被3整除的数的平方构成的列表 -
yield生成器
例如经典的斐波那契数列的生成
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
踩过的坑：
- python的引用机制，即浅复制机制，a=b并没有创建一个新的对象而是建立了对于b对象的一个引用，对于a的修改同样会改变b。犯过错误的地方在代码中有说明。可以使用
new_list = list(old_list)和new_deque = deque(old_deque)来生成新的对象，实现深复制。或者使用copy也行。 - 在同级的循环中，即所有下一个状态的同级遍历中，进入的时候对队列末尾添加了新状态，退出的时候一定不要忘记删除该新状态。虽然很简单的逻辑，但是第一次实现时确实忽略了，汗。
initial_bucket_state = [0,0,8]
#水桶的初始状态
bucket_volume = [3,5,8]
#每个水桶的对应的容积
from collections import deque
record = deque()
record.append(initial_bucket_state)
#利用python的deque队列记录状态转移情况，初始化时加入水桶初始状态。deque是可以从头尾插入和删除的队列，在不指定大小时，为一个无边界的队列
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_]
]
#通过列表推导式获得下一动作的二元组构成的列表，由（倒出水的容器编号，倒入水的容器编号）组成。
#二重循环得到下一步的所有可能动作，然后通过
##1.倒入倒出不能为同一个2.倒出的捅中必须有水3.倒入的桶中不能为满 的条件判断是否合法
for from_, to_ in next_action:
#next_state = current_state #浅复制造成错误
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
#再由所有可能的合法动作得出所有的下一个状态，通过yield产生供其它函数调用。
num = 0
record_list = []
#记录调试的变量：num表示总共实现方法数，record_list记录所有实现路径
def searchResult(record, bucket_volume=[3,5,8], final_bucket_state=[0,4,4]):
global num，record_list
current_state = record[-1]
#由record的末尾元素得到当前水桶状态
next_state = nextStateLawful(current_state, bucket_volume)
#得到关于当前状态的下一状态的可迭代生成器，供下一步循环使用
for state in next_state:
#遍历所有可能的下一状态
if state not in record:
#保证当前状态没在以前出现过。如果状态已经出现还进行搜索就会形成状态环路，陷入死循环。
record.append(state)
#添加新的状态到列表中
if state == final_bucket_state:
print(record)
#打印出可行方案
#record_list.append(record)这样使用错误，导致加入列表的是record的引用，应该使用下面的式子来进行深复制，得到一个新的队列再加入列表。
record_list.append(deque(record))
num += 1
else:
searchResult(record, bucket_volume, final_bucket_state)
#不是最终状态则递归搜索
record.pop()
#去除当前循环中添加的状态，进入下一个循环，关键步，第一次实现的时候遗漏了
if __name__=='__main__':
searchResult(record)
#开始
print(num)
#打印所有方案的数量
print(min([len(i) for i in record_list]))
#打印最短路径方案中的状态总数
