三个杯子的倒水问题(BFS)
'''已知容积为160 119 77的空桶和无限多的水想要得到76升的水问需要多少次操作?'''import numpy as np##################################visited = np.zeros((200,200,200))#对被访问过的进行记录,取决于空桶的最大容积##################################class cup(object):'''定义量杯类'''def __init__(self,name,volume,MaxV):self.name = nameself.MaxV = MaxVself.volume = volumeA = 160#三个杯子的最大容量B = 119C = 77#默认 杯中为空Result = 76 # 目标cupA = cup('A', 0, A)cupB = cup('B', 0, B)cupC = cup('C', 0, C)def XpourWaterToY(cupX,cupY):'''把X中的水倒入Y中:param CupX: :param cupY: :return: surplusX:X中的剩余量surplusY:Y中的剩余量'''if cupX.volume >= cupY.MaxV-cupY.volume:#如果X中的液体容量,比Y的最大容量-现有溶液体积的话cupX.volume = cupX.volume - (cupY.MaxV-cupY.volume)#此时X中剩余水的体积cupY.volume = cupY.MaxV # 那么Y被倒满水else:cupY.volume = cupY.volume + cupX.volume # X中的水全部倒入YcupX.volume = 0 #X中的水被倒光了return cupX.volume,cupY.volumedef emptyWater(cupX):'''把X中的水清空,倒入水池中(不倒入任何容器):param cupX::return:'''cupX.volume = 0return 0def fillWater(cupX):'''将X倒满水:param cupX::return:'''cupX.volume = cupX.MaxVreturn cupX.volumedef show():'''当前三个水杯的状态:return:'''return cupA.volume,cupB.volume,cupC.volumeclass State:def __init__(self,a,b,c,prev=None,step=0):self.a = aself.b = bself.c = cself .prev = prevself.step = stepdef bfs(cupA,cupB,cupC,Result):queue = []s = State(cupA.volume,cupB.volume,cupC.volume)queue.append(s)visited[0][0][0]=1while queue:statu = queue.pop(0)flag = 1 #计数 , 因为有三个水杯且无限的水 所以有12种生成新节点的方式while flag < 13:#让每个节点对每种情况都生成新的节点,并进行判断cupA.volume = statu.acupB.volume = statu.bcupC.volume = statu.c#在每次生成新节点时,让杯中的状态回到父节点状态a,b,c = 0,0,0if flag == 1 :emptyWater(cupA)a,b,c = show()if flag == 2:emptyWater(cupB)a,b,c = show()if flag == 3:emptyWater(cupC)a,b,c = show()if flag == 4:fillWater(cupA)a,b,c = show()if flag == 5:fillWater(cupB)a,b,c = show()if flag == 6 :fillWater(cupC)a,b,c = show()if flag == 7:#把A倒入BXpourWaterToY(cupA,cupB)a,b,c = show()if flag == 8:#把B倒入AXpourWaterToY(cupB,cupA)a,b,c = show()if flag == 9:#把A倒入CXpourWaterToY(cupA,cupC)a,b,c = show()if flag == 10:#把C倒入AXpourWaterToY(cupC,cupA)a,b,c = show()if flag == 11:#把C倒入BXpourWaterToY(cupC,cupB)a,b,c = show()if flag == 12:#把B倒入CXpourWaterToY(cupB,cupC)a,b,c = show()if not visited[a][b][c]:#判断是否生成过new_state = State(a,b,c,prev=statu,step=statu.step+1)visited[a][b][c] = 1queue.append(new_state)if a == Result or b == Result or c == Result:#判断是否满足目标条件print("Find!")return new_stateflag += 1return Nonedef getPath(state):#获取路径 由目标节点向其父节点回溯path = []while state.prev :path.append(str(state.step)+' '+str((state.a,state.b,state.c)))state = state.prevreturn path[::-1]#逆序def main():'''主函数'''reslut = bfs(cupA, cupB, cupC, Result)path = getPath(reslut)print('三个量杯最大容积为' + str((cupA.MaxV, cupB.MaxV, cupC.MaxV)))print('目标水体积' + str(Result))print('Path:' + '\n' + '共用了' + str(len(path)) + '步')for i in path:print(i)if __name__ == '__main__':main()
