小孩分油问题python解决

1.问题描述原问题：两个小孩去打油，一个人带了一个一斤的空瓶，另一个带了一个七两一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，可是又没有其它工具，试仅用三个瓶子（一斤、七两、三两）精确地分成两个半斤油来。2.算法设计把三个油瓶中的油量作为一个状态，经过一个合法动作后得到下一个状态（合法动作是把A瓶中的油全部倒入B瓶或者把A瓶中的油部分倒入B瓶使B瓶充满油），递归搜索所有的可能状态，如果到达最终状态则递归停止。油瓶中油的变化规则：（S表示3两油瓶，T表示7两油瓶）序号规则解释1(S,T)andS7-(7,T)7两瓶不满时装满2(S,T)andT3-(S,3)3两瓶不满时装满3(S,T)andS0-(0,T)7两瓶不空时倒空4(S,T)andT0-(S,0)3两瓶不空时倒空5(S,T)andS0andS+T=3-(0,S+T)7两瓶中的油全倒入3两瓶6(S,T)andT0andS+T=7-(S+T,0)3两瓶中的油全倒入7两瓶7(S,T)andS0andS+T=3-(S+T-3,3)7两瓶中的油倒满3两瓶8(S,T)andT0andS+T=7-(7,S+T-7)3两瓶中的油倒满7两瓶3.代码（穷搜索）广度优先搜索：（文本输出）importosinitial_oil_state=[10,0,0]#油瓶的初始状态oil_volume=[10,7,3]#每个油瓶的对应容积fromcollectionsimportdeque#导入collections标准库中的队列对象和方法#利用python的deque队列记录状态转移情况，初始化时加入油瓶初始状态。deque是可以从头尾插入和删除的队列record=deque()record.append(initial_oil_state)#删除文件，因为文件以追加模式打开ifos.path.exists('oil_half_width_answer.txt'):os.remove('oil_half_width_answer.txt')defNextStateLegal(current_state,oil_volume):next_action=[(from_,to_)#列表推导#例如[x*xforxinrange(10)ifx%3==0]得出10以内能被3整除的数的平方构成的列表forfrom_inrange(3)forto_inrange(3)iffrom_!=to_andcurrent_state[from_]0andcurrent_state[to_]oil_volume[to_]]#通过列表推导式获得下一动作的二元组构成的列表，由（倒出油瓶编号，倒入油瓶编号）组成。#二重循环得到下一步的所有可能动作，然后通过#1.倒入倒出不能为同一个2.倒出的油瓶中必须有油3.已经满了的油瓶不能再倒入的条件判断是否合法forfrom_,to_innext_action:#next_state=current_state,浅复制造成错误,不该这样,或者可以导入copy使用deepcopy方法next_state=list(current_state)ifcurrent_state[from_]+current_state[to_]oil_volume[to_]:next_state[from_]-=(oil_volume[to_]-current_state[to_])next_state[to_]=oil_volume[to_]else:next_state[from_]=0next_state[to_]=current_state[to_]+current_state[from_]yieldnext_state#再由所有可能的合法动作得出所有的下一个状态，通过yield产生供其它函数调用#记录调试的变量：num表示总共实现方法数，record_list记录所有实现路径num=0record_list=[]defsearchResult(record,oil_volume=[10,7,3],final_state=[5,5,0]):globalnum,record_list#由record的末尾元素得到当前油瓶状态current_state=record[-1]#得到关于当前状态的下一状态的可迭代生成器，供下一步循环使用next_state=NextStateLegal(current_state,oil_volume)#遍历所有可能的下一个状态forstateinnext_state:#保证当前状态没在之前出现过。如果状态已经出现还进行搜索就会形成状态环路，陷入死循环。ifstatenotinrecord:#添加到新的状态到列表中record.append(state)#判断是否达到最终状态ifstate==final_state:#记录当前是第几种方案numm=num+1s_numm=str(numm)str_record=''#将队列转换为相对美观的字符串foriinrecord:str_record+=str(i)ifi!=[5,5,0]:str_record+='-'#console打印可执行方案print(str_record)#连接字符串以便保存queue_='第'+s_numm+'种方案'+str_record+'\n\n'#文件存入方案，a表示文件以追加模式打开f=open('oil_half_width_answer.txt','a')f.write(queue_)f.close()#record_list.append(record)这样使用错误，导致加入列表的是record的引用#应该使用下面的式子来进行深复制，得到一个新的队列再加入列表。record_list.append(deque(record))num+=1else:#如不是最终状态则递归搜索searchResult(record,oil_volume,final_state)#去除当前循环中添加的状态，进入下一个循环，关键步！record.pop()if__name__=='__main__':#开始searchResult(record)#保存方案数以及最短路径输出字符串number=用广度优先搜索共有%d种方案。%numshortest=路径最短的方案中状态总数为%d。%min([len(i)foriinrecord_list])#数字转换字符串，为了方便保存在文件中s_num=str(num)s_min=str(min([len(i)foriinrecord_list]))#保存需要存放的字符串，将用于write函数中ss_num=用广度优先搜索共有+s_num+种方案。\nss_min=路径最短的方案中状态总数为+s_min+。\n#文件存入方案数以及最短路径f=open('oil_half_width_answer.txt','a')f.write(ss_num)f.write(ss_min)f.close()#console打印所有方案的数量和最短路径print(number)print(shortest)深度优先搜索（未加文本输出）：importcopy#scr=from,dest=in,water=水量globalnumclassOil(object):def__init__(self,capacity,water=0):self.capacity=capacityself.water=waterdef__eq__(self,other):#不论发生什么，只要有==做比较，就返回Truereturnself.capacity==other.capacityandself.water==other.waterdef__ne__(self,other):returnnotself.__eq__(other)defis_empty(self):returnself.water==0defis_full(self):returnself.capacity==self.waterdefdump_in(self,water):assertself.water+water=self.capacityself.water+=waterdefdump_out(self,water):assertself.water=waterself.water-=waterdef__str__(self):returnstr(self.water)__repr__=__str__classAction(object):def__init__(self,from_,to_,water):self.from_=from_self.to_=to_self.water=waterclassState(object):def__init__(self,oil_list,action):self.oil_list=copy.deepcopy(oil_list)self.action=copy.deepcopy(action)defdo_dump(self):self.oil_list[self.action.from_].dump_out(self.action.water)self.oil_list[self.action.to_].dump_in(self.action.water)def__eq__(self,other):forbt_now,bt_endinzip(self.oil_list,other.oil_list):ifbt_now!=bt_end:returnFalsereturnTruedef__ne__(self,other):returnnotself.__eq__(other)classAlgorithm(object):def__init__(self,start,end):self.start=startself.end=endassertlen(start)==len(end)self.oil_count=len(start)defsearch(self,stack=None):ifstackisNone:stack=[State(self.start,None)]curr=stack[-1]ifself.is_finished(curr):self.print_result(stack)returnforiinrange(self.oil_count):forjinrange(self.oil_count):self.do_action(stack,curr,i,j)defdo_action(self,stack,current,i,j):new_state=self.dump_water(current.oil_list,i,j)ifnew_state:ifnotself.is_processed_state(stack,new_state):stack.append(new_state)self.search(stack)stack.pop()defdump_water(self,oil_list,i,j):ifi!=j:from_,to_=oil_list[i],oil_list[j]iffrom_.is_empty()orto_.is_full():returnNonewater=to_.capacity-to_.waterifwaterfrom_.water:water=from_.waternew_state=State(oil_list,Action(i,j,water))new_state.do_dump()returnnew_statereturnNonedefis_finished(self,current):forbt_1,bt_2inzip(self.end,current.oil_li