'''三商人三仆人过河问题，有一条船，最多只允许乘2人，要求商人数不少于仆人数， 设计过河方案''' '''基于状态空间搜索，深度优先搜索''' test=[[True,True,True,True],##### 状态允许，作为检验下一步的依据 [True,True,False,False], [True,True,True,False], [True,True,True,True]] ###有效的操作 dirs=[[1,1],[0,2],[0,1],[1,0],[2,0]] start=[3,3,1]###开始状态 end=[0,0,0]###结束状态 list2=[start] ###mark函数用于标记已经存在的状态，如果这个状态可行，加入list2中。 def mark(nextp): list2.append(nextp) return True #######判断解的可行性，如果可行，加入栈中 def passable(nextp): k=[] a=[3-nextp[0],3-nextp[1]] for i in a: if i<0 or i>3: return False if test[a[0]][a[1]] and test[nextp[0]][nextp[1]]: if nextp not in list2: return True else: return False #####主函数 def solver(start,end): if start==end: print(start) return stack=[] #建立栈 stack.append((start,0)) #放入初始状态 while stack: n=len(stack) #nxt 记录记录方向 pos,nxt=stack.pop() #### 5表示操作数 for i in range(nxt,5): '''计算下一步，n是栈的长度，n为奇数，表示过河，n为偶数，表示将船返回''' nextp=[pos[0]+pow(-1,n)*dirs[i][0],pos[1]+pow(-1,n)*dirs[i][1],(n+1)%2] ####搜索结束的条件 if nextp==end: stack.append((nextp,0)) print('问题解决') return stack ####判断解是否可行 if passable(nextp): ###如果可行，将原状态先放入栈中，并将 方向+1 stack.append((pos,i+1)) ###标记解，防止无限循环 mark(nextp) ###将下一状态放入栈中 stack.append((nextp,0)) ###结束循环 break st=solver(start,end) for i in st: print('左岸商人数: %d'%i[0][0],'左岸仆人数: %d'%i[0][1])
print('全部过河,共%d步'%len(st))
运行结果：
问题解决 左岸商人数: 3 左岸仆人数: 3 左岸商人数: 2 左岸仆人数: 2 左岸商人数: 3 左岸仆人数: 2 左岸商人数: 3 左岸仆人数: 0 左岸商人数: 3 左岸仆人数: 1 左岸商人数: 1 左岸仆人数: 1 左岸商人数: 2 左岸仆人数: 2 左岸商人数: 0 左岸仆人数: 2 左岸商人数: 0 左岸仆人数: 3 左岸商人数: 0 左岸仆人数: 1 左岸商人数: 0 左岸仆人数: 0 全部过河,共11步
转载请注明原文地址: https://www.6miu.com/read-55552.html
