题目内容:
有一个容积为8升的水桶里装满了水，另外还有一个容积为3升的空桶和一个容积为5升的空桶，如何利用这两个空桶等分8升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。
解决思路:
用计算机解决这个问题，通常会选择使用“穷举法”。
建立状态模型是整个算法的关键，这个状态模型不仅要能够描述静止状态，还要能够描述并记录状态转换动作，尤其是对状态转换的描述，因为这会影响到状态树搜索算法的设计。所谓的静止状态，就是某一时刻三个水桶中存水的容积，我们采用长度为3的一维向量描述这个状态。这组向量的三个值分别是容积为8升的桶中的水量、容积为5升的桶中的水量和容积为3升的桶中的水量。因此算法的初始状态就可以描述为[8 ,0, 0]，则终止状态为[4, 4, 0]。
对状态转换的描述就是在两个状态之间建立关联，在本算法中这个关联就是一个合法的倒水动作。某一时刻三个水桶中的存水状态，经过某个倒水动作后演变到一个新的存水状态，这是对状态转换的文字描述，对算法来讲，倒水状态描述就是“静止状态”＋“倒水动作”。应用本模型对前面提到的第一种解决方法进行状态转换描述，整个过程如图
Python穷举法三只水桶等分水
确定了状态模型后，就需要解决算法面临的第二个问题：状态树的搜索算法。一个静止状态结合不同的倒水动作会迁移到不同的状态，所有状态转换所展示的就是一棵以状态[8, 0, 0]为根的状态搜索树，其中一个用不同颜色标识出来的状态转换过程（状态树的一个分支）就是本问题的一个解：
Python穷举法三只水桶等分水
对于三个水桶这样小规模的题目，其整个状态树的规模也是相当大的，更何况是复杂一点的情况，因此类似本文这样对搜索整个状态树求解问题的算法都不得不面对一个算法效率的问题，必须要考虑如何进行优化，减少一些明显不必要的搜索，加快求解的过程。
分析完结构，发点福利来段代码吧，利用Python写的代码:
# -*- coding:utf-8 -*-
# -*- author:yingyagongzuoshi -*-
from collections import deque
class WaterStatus(object):
def __init__(self, limit, water):
self.limit = limit
self.water = water
def ChangeWater(src, dst):
if src.water == 0 or dst.water == dst.limit:
water = 0
if src.water >= dst.limit - dst.water:
water = dst.limit - dst.water
else:
water = src.water
src.water -= water
dst.water += water
if __name__ == '__main__':
a = WaterStatus(8, 8)
b = WaterStatus(5, 0)
c = WaterStatus(3, 0)
water_list = [a, b, c]
water_queue = deque()
water_queue.append([8,0,0])
cur_status = []
cnt = 1
while(1):
print u'***第 %d 次循环***' % cnt
cnt += 1
if [4, 4, 0] == cur_status:
print 'find it!'
break
for water1 in water_list:
for water2 in water_list:
# 记录当前状态，深拷贝deepcopy，创建新的对象
cur_status = list(water_queue[-1])
water_list[0].water = cur_status[0]
water_list[1].water = cur_status[1]
water_list[2].water = cur_status[2]
# print water_list[0].water, water_list[1].water, water_list[2].water
# 计算一次迁移
if water1.limit != water2.limit:
ChangeWater(water1, water2)
next_status = [water_list[0].water, water_list[1].water, water_list[2].water]
# print 'next_status' , next_status
if next_status in water_queue:
# print '迁移后的状态在记录中存在，将当前状态转到迁移之前的状态'
pass
else:
# print '记录迁移后的状态,一定要用list()来新建一个对象'
cur_status = next_status
water_queue.append(list(next_status))
# print water1.limit , water2.limit, cur_status
print '---', water_queue
运行结果如下:
Python穷举法三只水桶等分水
网友评论