python小练习（066）：回溯法（深度优先搜索）实现全排列

jerryxjr1220

之前几个小练习介绍了探索法（又称“广度优先搜索”算法 -- BFS算法）的几个应用。

后面的几个小练习我想分享一下回溯法（又称“深度优先搜索”算法 -- DFS算法）。

这样，掌握了BFS和DFS这两种经典的算法以后，大部分的求解最优解的题目就都可以用计算机求解了。（但是需要灵活判断，到底哪种题目适用于哪种方法，因为这2种方法是截然不同的思路。）

这样，最优算法方面的介绍算是完整了。

先来看一下“深度优先搜索”算法 -- DFS算法的定义：
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

深度优先算法：
（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。

举个栗子：
求有一个1，2，3，... ，n的数组的全排列。

假设n=3时，输出：
123
132
213
231
312
321

当然，我们可以借助itertools的permutations（）函数，直接完成。 但是，如果让你自己写程序，应该怎么写呢？
利用DFS算法，开动脑筋吧，我会把解答和注释贴在下面。

源代码：

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

利用回溯法求解八皇后（N皇后）问题也是非常经典的运用。

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。

该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

1. #coding:utf-8
   
2. #Define 'N' queens problem:
   
3. n = 8
   
4. #initiate:
   
5. chest = [[0] * n for i in range(n)] #define the matrix
   
6. result = [] #put all the results in the list.
   
7. tmp = [] #put the queens' position in tmp as "1-D" list.
   
8. queen = 0 #check the queens has been put.
   
9. c = 0 #calculate the solutions.
   
10. 
    
11. #define reset function:
    
12. def reset():
    
13.         global chest, tmp, queen
    
14.         chest = [[0] * n for i in range(n)]
    
15.         tmp = []
    
16.         queen = 0
    
17. 
    
18. #define the position (x,y) can put the queen or not:
    
19. def check(x,y):
    
20.         if max(chest[x]) == 1:
    
21.                 return False
    
22.         if max([chest[i][y] for i in range(n)]) == 1:
    
23.                 return False
    
24.         for i in range(n):
    
25.                 for j in range(n):
    
26.                         if i+j == x+y or i-j == x-y:
    
27.                                 if chest[i][j] == 1:
    
28.                                         return False
    
29.         return True
    
30. 
    
31. #define the main loop to put the queens:
    
32. def main():
    
33.         global c
    
34.         if len(tmp) == n:
    
35.                 result.append(tmp)
    
36.                 c += 1
    
37.                 print ('Solution %d:' % c)
    
38.                 show = [[0] * n for i in range(n)]
    
39.                 for i in range(n):
    
40.                         show[i][tmp[i]] = 1
    
41.                         print (show[i])
    
42.                 print ()
    
43.                 reset()
    
44.         for i in range(n):
    
45.                 y = i
    
46.                 x = len(tmp)
    
47.                 if check(x,y) and tmp+[y] not in result:
    
48.                         tmp.append(y)
    
49.                         chest[x][y] = 1
    
50.                         main()
    
51.                         try:
    
52.                                 chest[x][y] = 0
    
53.                                 tmp.remove(y)
    
54.                         except:
    
55.                                 print ('Total Solution %d, done!' % len(result))
    
56.                                 exit()
    
57. 
    
58. if __name__ == "__main__":
    
59.         main()

复制代码

当n=8时（八皇后），输出：
Solution 1:
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 2:
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

中间省略N个解

Solution 91:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 92:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

Total Solution 92, done!

余欲渔

学习学习

易水寒楠

学习一下

H.B.F

jerryxjr1220 发表于 2017-2-6 14:15
利用回溯法求解八皇后（N皇后）问题也是非常经典的运用。

八皇后问题，是一个古老而著名的问题，是回溯 ...

有点下复杂 我觉的还是先了解回溯

WelanceLee

总觉得理解BFS和DFS了，但就是解决不了题目……很伤心啊

jerryxjr1220

WelanceLee 发表于 2017-6-14 10:06
总觉得理解BFS和DFS了，但就是解决不了题目……很伤心啊

DFS和BFS其实算法的结构是相同的，无非是处理序列的顺序不同，一个优先广度，一个优先深度。
一般利用递归法（回溯法）的，写深度优先比较容易。循环迭代法的，写广度优先比较容易（写深度优先其实也容易，换个顺序而已）。
落实到全排列问题，其实可以利用迭代插入法。
举个例子：如果abc需要全排列。
              字符串            排列组合
step1：  abc                []
step2:     bc                  [a]
step3:     c                    [ba, ab]
step4:     ''                    [cba, bca, bac, cab, acb, abc]
每次从字符串中取出第一个字母，依次插入到列表中的每个元素中，直到字符串为空。
是不是很简单？

WelanceLee

jerryxjr1220 发表于 2017-6-14 10:28
DFS和BFS其实算法的结构是相同的，无非是处理序列的顺序不同，一个优先广度，一个优先深度。
一般利用递 ...

这个确实帅啊~

jerryxjr1220

WelanceLee 发表于 2017-6-14 10:34
这个确实帅啊~

看懂了，就写个迭代插入法的程序练练手啊

WelanceLee

jerryxjr1220 发表于 2017-6-14 10:39
看懂了，就写个迭代插入法的程序练练手啊

1. ## 迭代插入法
   
2. n = 5
   
3. a = [i for i in range(n)]
   
4. 
   
5. b = [[n - 1]]
   
6. a.pop()
   
7. while a:
   
8.     x = a.pop()
   
9.     n = len(b)  # 当前排列个数
   
10.     m = len(b[0]) + 1 # 可插入的位置
    
11.     i = 0 # 计录完成更新的次数（个数增加1）
    
12.     while i < n:
    
13.         for j in range(m):
    
14.             y = b[0][:]
    
15.             y.insert(j, x)
    
16.             b.append(y)
    
17.         b.pop(0)
    
18.         i += 1
    
19. 
    
20. for each in b:
    
21.     print(each)

复制代码

搞了好久，感觉不像我看的那样简单啊

小锟

看看

jerryxjr1220

WelanceLee 发表于 2017-6-14 12:59
搞了好久，感觉不像我看的那样简单啊

用递归写了一个，也是插入法

1. def permutations(strings, lst=['']):
   
2.     if strings == '':
   
3.         return lst
   
4.     else:
   
5.         new = set()
   
6.         for i in lst:
   
7.             for j in range(len(i) + 1):
   
8.                 new.add(i[:j] + strings[0] + i[j:])
   
9.         return permutations(strings[1:], list(new))

复制代码

WelanceLee

jerryxjr1220 发表于 2017-6-14 14:05
用递归写了一个，也是插入法

果然看着更舒服些

neilyoone

来看看

sagerzone

JAY饭

1. 
   
2. class P():
   
3.     def __init__(self,n):
   
4.         self.len = n
   
5.         self.lst = [i for i in range(n)]
   
6.         self.visit = []
   
7.         self.sign = []
   
8. 
   
9.     def pai(self,lst,sign):
   
10. 
    
11.         for i,j in enumerate(lst):
    
12.             sign1 = sign[:]
    
13.             lst1 = lst[:]
    
14.             sign1.append(j)
    
15.             lst1.remove(j)
    
16.             if len(sign1) == self.len:
    
17.                 print(sign1)
    
18.                 return True
    
19.             self.pai(lst1,sign1)
    
20. 
    
21. P1 = P(5)
    
22. P1.pai(P1.lst,P1.sign)

复制代码

chakyam

看看

wenweno

wwezer

学习学习