夫妻过河问题---图论算法的应用(Python实现)

小灰灰 2022-05-08 13:04 78阅读 0赞

class Graph(object):
“””docstring for Graph”””
def __init__(self, mat):
super(Graph, self).__init__()
self.n = len(mat[0])
self.edge = 0
self.mat = mat
self.vertex = []
self.visited = [0 for i in range(n)]
self.found = 0
self.path = []
self.solution = []
def DFS(self):
for i in range(self.n):
if not self.visited[i]:
self.dfs(i)
def dfs(self,i):
self.visited[i] = 1
print(i)
for j in range(self.n):
if not self.visited[j] and self.mat[i][j]:
self.dfs(j)
def CrossRiver(self):
self.vertex = []
for i in range(2):
for j in range(2):
for k in range(2):
for p in range(2):
for q in range(2):
for r in range(2):
self.vertex.append([i,j,k,p,q,r])
self.n = 64
self.mat = mat = [[0 for j in range(self.n)] for i in range(self.n)]
self.visited = [0 for i in range(self.n)]
self.initialize()
self.DFS_()
def DFS_(self):
for i in range(self.n):
if not self.visited[i] and not self.found:
self.dfs_(i)
def dfs_(self,i):
self.visited[i] = 1
#print(i,self.mat[i][63],self.vertex[i])
self.path.append(self.vertex[i])
if self.mat[i][63]:
#print(63,self.vertex[63])
print(“found!”)
self.path.append(self.vertex[63])
self.found = 1
for j in range(self.n):
if not self.visited[j] and self.mat[i][j] and self.isSafe(G.vertex[j]):
if not self.found:
self.dfs_(j)
def isSafe(self,state):
a1,a2,b1,b2,c1,c2 = state[0],state[1],state[2],state[3],state[4],state[5]
if [a1,a2,b1,b2,c1,c2] == [1,1,1,1,1,1]:
return True
if a2 != a1 and (a2 == b1 or a2 == c1):
return False
if b2 != b1 and (b2 == a1 or b2 == c1):
return False
if c2 != c1 and (c2 == a1 or c2 == b1):
return False
return True
def initialize(self):
for i in range(self.n):
for j in range(self.n):
if self.isConnected(self.vertex[i],self.vertex[j]):
self.mat[i][j] = 1
def isConnected(self,state1,state2):
changes = []
for i in range(len(state1)):
if state1[i] != state2[i]:
changes.append([state1[i],state2[i]])
if changes == []:
return False
if len(changes) == 1:
return True
if len(changes) == 2:
if changes[0][0] != changes[1][0]:
return False
else:
return True
else:
return False

  1. def showMoves(self):
  2. n = len(self.path)
  3. solution = \[\]
  4. m1 = "Move man 1 to the other side; "
  5. m2 = "Move lady 1 to the other side; "
  6. m3 = "Move man 2 to the other side; "
  7. m4 = "Move lady 2 to the other side; "
  8. m5 = "Move man 3 to the other side; "
  9. m6 = "Move lady 3 to the other side; "
  10. n1 = "Move man 1 back from the other side; "
  11. n2 = "Move lady 1 back from the other side; "
  12. n3 = "Move man 2 back from the other side; "
  13. n4 = "Move lady 2 back from the other side; "
  14. n5 = "Move man 3 back from the other side; "
  15. n6 = "Move lady 3 back from the other side; "
  16. path = G.path
  17. for i in range(n-1):
  18. \#This state
  19. a1,a2,b1,b2,c1,c2 = path\[i\]\[0\],path\[i\]\[1\],path\[i\]\[2\],\\
  20. path\[i\]\[3\],path\[i\]\[4\],path\[i\]\[5\]
  21. \#Next state
  22. a1n,a2n,b1n,b2n,c1n,c2n = path\[i+1\]\[0\],path\[i+1\]\[1\],path\[i+1\]\[2\],\\
  23. path\[i+1\]\[3\],path\[i+1\]\[4\],path\[i+1\]\[5\]
  24. \#Initialize move
  25. move = ''
  26. \#Judge
  27. \#Couple one
  28. if a1 == 0 and a1n == 1:
  29. move += m1
  30. if a1 == 1 and a1n == 0:
  31. move += n1
  32. if a2 == 0 and a2n == 1:
  33. move += m2
  34. if a2 == 1 and a2n == 0:
  35. move += n2
  36. \#Copule two
  37. if b1 == 0 and b1n == 1:
  38. move += m3
  39. if b1 == 1 and b1n == 0:
  40. move += n3
  41. if b2 == 0 and b2n == 1:
  42. move += m4
  43. if b2 == 1 and b2n == 0:
  44. move += n4
  45. \#Couple three
  46. if c1 == 0 and c1n == 1:
  47. move += m5
  48. if c1 == 1 and c1n == 0:
  49. move += n5
  50. if c2 == 0 and c2n == 1:
  51. move += m6
  52. if c2 == 1 and c2n == 0:
  53. move += n6
  54. self.solution.append('Step '+str(i+1)+': '+move)
  55. for step in G.solution:
  56. print(step)

n = 4
mat = [[0 for j in range(n)] for i in range(n)]
G = Graph(mat)
G.CrossRiver()
print(“\n走法如下:”)
for move in G.path:
print(move)
G.showMoves()

发表评论

表情:
评论列表 (有 0 条评论,78人围观)

还没有评论,来说两句吧...

相关阅读