python写的一个经典“过河程序”

liweioop

1. 
   
2. # 老虎过河问题的求解
   
3. # 老虎分别有三只大老虎和三只小的老虎,是三对母子
   
4. # 大老虎都会划船,而小老虎中只有x会划船
   
5. # 河边只有一只船,船每次最多只能过两只老虎
   
6. # 当小老虎的妈妈不在身边是,会被其他的大老虎吃掉
   
7. # 要求是:这三对老虎能安全的过河
   
8. 
   
9. ###############算法描述###################
   
10. # 假设从河的左边移动到右边
    
11. # 用a,b,c,x,y,z表示三只大老虎和小老虎
    
12. # 其中a,b,c,x会划船
    
13. #
    
14. #程序用state来记录过河过程中的每个状态
    
15. # 如：起始状态为state.left=[a,b,c,x,y,z],state.right=[],state.boat_position='left'
    
16. # 从起始状态开始，寻找所有可能过河的组合，并将过河后的状态记录下来
    
17. # 例如:
    
18. # 从起始状态开始，可以过河的组合有(x,y),当(x,y)过河之后，新状态是
    
19. # state.left=[a,b,c,z], state.right=[x,y],state.boat_position='right'
    
20. #
    
21. # 然后不断的移动，如果找到了一个状态是
    
22. # state.left=[], state.right=[a,b,c,x,y,z], state.boat_position='right'
    
23. # 此时过河成功，打印出过河的步骤
    
24. 
    
25. #########################################
    
26. 
    
27. #分别代表三对老虎               
    
28. a='a'
    
29. b='b'
    
30. c='c'
    
31. x='x'
    
32. y='y'
    
33. z='z'
    
34. 
    
35. # 所有可能过河的组合
    
36. psb=[       (a,),(b,),(c,),(x,),
    
37.         (a,b),(a,c),(a,x),        (b,a),(c,a),(x,a),
    
38.         (b,c),(b,y),        (c,b),(y,b),
    
39.                 (c,z),                        (z,c),
    
40.         (x,y),(x,z),        (y,x),(x,z) ]
    
41. def f(x):
    
42.         if x in psb:
    
43.                 return True
    
44.         else:
    
45.                 return False
    
46. def findPossible(llist): #找出列表中由一个或两个元素的组合(可以过河的组合),并过虑
    
47.         steps=[]
    
48.         length=len(llist)
    
49.         for item in llist:
    
50.                 steps.append( (item,))
    
51.         for i in range(0,length-1):
    
52.                 for j in range(i+1,length):
    
53.                         steps.append((llist[i],llist[j]))
    
54.         return filter(f,steps)       
    
55. class state:
    
56.         def __init__(self):
    
57.                 self.left=[]
    
58.                 self.right=[]
    
59.                 self.boat_position=''
    
60.                 self.steps=[]
    
61.                 self.current_step=()
    
62.         def setState(self,left,right,boat_pos):
    
63.                 self.left=left
    
64.                 self.right=right
    
65.                 self.boat_position=boat_pos
    
66.                 self.left.sort()
    
67.                 self.right.sort()
    
68.                 self.findAllSteps()
    
69.         def findAllSteps(self):
    
70.                 if self.boat_position=='left':
    
71.                         self.steps=findPossible(self.left)
    
72.                 else:
    
73.                         self.steps=findPossible(self.right)
    
74.         def setCurrentStep(self):
    
75.                 if self.steps==[]:
    
76.                         self.current_step=()
    
77.                 else:
    
78.                         self.current_step=( self.steps.pop() )
    
79.         def isLegal(self): #判断当前状态是否合法 0不合法 1合法 10找到了出口               
    
80.                 if(self.left==[]) and (self.right==[a,b,c,x,y,z]):
    
81.                         return 10
    
82.                 if (a in self.left or b in self.left or c in self.left ): #左边有大老虎
    
83.                         if ( (x in self.left) and (a not in self.left) ):
    
84.                                 return 0
    
85.                         if ( (y in self.left) and (b not in self.left) ):
    
86.                                 return 0
    
87.                         if ( (z in self.left) and (c not in self.left) ):
    
88.                                 return 0
    
89.                 左边没有大老虎,那么右边一定有大老虎
    
90.                 if ( (x in self.right) and (a not in self.right) ):
    
91.                         return 0
    
92.                 f ( (y in self.right) and (b not in self.right) ):
    
93.                         return 0
    
94.                 if ( (z in self.right) and (c not in self.right) ):
    
95.                         return 0
    
96.                 return 1
    
97.         def printState(self):
    
98.                 print self.left,self.right,self.boat_position
    
99.                 print self.steps
    
100.                 print self.current_step
     
101.         def move(self):
     
102.                 self.setCurrentStep()
     
103.                 if self.current_step==():
     
104.                         print "No step ,but still to move"
     
105.                         print "This infomation is for debug"
     
106.                 new_state=state()
     
107.                 if self.boat_position=='left':
     
108.                         new_state.left=[item for item in self.left if(not item in self.current_step)]
     
109.                         new_state.right=[item for item in self.right]
     
110.                         for i in self.current_step:
     
111.                                 new_state.right.append(i)               
     
112.                         new_state.boat_position='right'
     
113.                 else: #boat position is right
     
114.                         new_state.right=[item for item in self.right if(not item in self.current_step)]
     
115.                         new_state.left=[item for item in self.left ]
     
116.                         for i in self.current_step:
     
117.                                 new_state.left.append(i)
     
118.                         new_state.boat_position='left'
     
119.                 new_state.left.sort()
     
120.                 new_state.right.sort()
     
121.                 new_state.findAllSteps()
     
122.                 return new_state
     
123.                
     
124. state_list=[] #过河的状态表,表中的每一个无素都是一个状态
     
125. state_stack=[] #表示所有的已经经历过的状态
     
126. def isOldState(sstate):
     
127.         for item in state_list:
     
128.                 if item.left==sstate.left and item.right==item.right and \
     
129.                                 item.boat_position==item.boat_position:
     
130.                         return True
     
131.         return False
     
132. def print_steps():
     
133.         for item in state_stack:
     
134.                 print item.left, item.right
     
135.                 print item.left,
     
136.                 if item.boat_position=='left':
     
137.                         print str(item.current_step)+"-->",
     
138.                 else:
     
139.                         print "<--"+str(item.current_step),
     
140.                 print item.right
     
141.                 print
     
142. 
     
143. # 主程序
     
144. 
     
145. sstate=state()
     
146. sstate.setState([a,b,c,x,y,z],[],'left')
     
147. state_stack.append(sstate)
     
148. state_list.append(sstate)
     
149. c_state=sstate #栈顶初始值
     
150. while(True) :
     
151.         if c_state.steps==[]: #当前无路可走       
     
152.                 state_stack.pop()
     
153.                 if state_stack==[]:
     
154.                         break
     
155.                 c_state=state_stack[ len(state_stack)-1 ]
     
156.                 continue
     
157.         else: # 有路可走了
     
158.                 next_state=c_state.move()
     
159.                 if isOldState(next_state):
     
160.                         continue
     
161.                 if next_state.isLegal()==0:
     
162.                         continue
     
163.                 elif next_state.isLegal()==10:
     
164.                         print "成功"
     
165.                         state_stack.append(c_state)
     
166.                         print_steps()
     
167.                         break
     
168.                 else: #下一个状态为合法
     
169.                         state_stack.append(next_state)
     
170.                         state_list.append(next_state)
     
171.                         c_state=next_state
     
172. 
     
173.                                
     
174.                        
     
175.                
     
176.        
     
177. 
     
178. 
     

复制代码

liweioop

算法简单的描述是：
假设从河左边向右边过河

从起始状态开始，找出所有能过河的组合，并尝试过河，过河后得到新的状态.

得到新的状态之后，然后再尝试所有可能过河的状态，这样反复不断的尝试，一直找到一个状态是
左边没有一只老虎，而右边有6 只老虎，此时则表示过河成功


算法中，判断一个状态的合法性的算法，感觉很不好，但一时又找不到更好的算法.



程序最后的结果显示，无法安全过河！经过仔细检查，栈最多时达到了9

monogatari

没学过phthon,但是感觉好象是有解的,请指教.

0 在此岸,1 在彼岸,前三个位置是大老虎,后三个位置是小老虎.
abc xyz     操作,                       船最后的位置.
000000     初试状态,                船在此岸       
010010         b 和 y 去彼岸      船在彼岸
000010         b 回来,                  船在此岸       
000111         x 和 z 去彼岸,        船在彼岸       
000011         x 回去 ,                 船在此岸       
011011         b,c 去彼岸,             船在彼岸       
001001        b,y 回来,                船在此岸       
101101    a,x 去彼岸,             船在彼岸
100100        c,z回来,                 船在此岸
111100        b号大老虎和c号大老虎到对岸  此岸留 y z 两个小老虎
111000        x号小老虎自己回到此岸,         彼岸留 abc 三个大老虎
111110        x号小老虎和y号小老虎到彼岸  此岸留 z 小老虎
110110        c号大老虎回此岸
111111    c号大老虎和z号小老虎到彼岸,完毕.

liweioop

算法经过修改，测试成功！

能够找到一个过河方案