python小练习（066）：回溯法（深度优先搜索）实现全排列
本帖最后由 jerryxjr1220 于 2017-2-7 11:21 编辑之前几个小练习介绍了探索法（又称“广度优先搜索”算法 -- BFS算法）的几个应用。
后面的几个小练习我想分享一下回溯法（又称“深度优先搜索”算法 -- DFS算法）。
这样，掌握了BFS和DFS这两种经典的算法以后，大部分的求解最优解的题目就都可以用计算机求解了。（但是需要灵活判断，到底哪种题目适用于哪种方法，因为这2种方法是截然不同的思路。）
这样，最优算法方面的介绍算是完整了。{:10_248:}
先来看一下“深度优先搜索”算法 -- 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算法，开动脑筋吧，我会把解答和注释贴在下面。
源代码：
**** Hidden Message ***** 利用回溯法求解八皇后（N皇后）问题也是非常经典的运用。
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
#coding:utf-8
#Define 'N' queens problem:
n = 8
#initiate:
chest = [ * n for i in range(n)] #define the matrix
result = [] #put all the results in the list.
tmp = [] #put the queens' position in tmp as "1-D" list.
queen = 0 #check the queens has been put.
c = 0 #calculate the solutions.
#define reset function:
def reset():
global chest, tmp, queen
chest = [ * n for i in range(n)]
tmp = []
queen = 0
#define the position (x,y) can put the queen or not:
def check(x,y):
if max(chest) == 1:
return False
if max( for i in range(n)]) == 1:
return False
for i in range(n):
for j in range(n):
if i+j == x+y or i-j == x-y:
if chest == 1:
return False
return True
#define the main loop to put the queens:
def main():
global c
if len(tmp) == n:
result.append(tmp)
c += 1
print ('Solution %d:' % c)
show = [ * n for i in range(n)]
for i in range(n):
show] = 1
print (show)
print ()
reset()
for i in range(n):
y = i
x = len(tmp)
if check(x,y) and tmp+ not in result:
tmp.append(y)
chest = 1
main()
try:
chest = 0
tmp.remove(y)
except:
print ('Total Solution %d, done!' % len(result))
exit()
if __name__ == "__main__":
main()
当n=8时（八皇后），输出：
Solution 1:
Solution 2:
中间省略N个解
Solution 91:
Solution 92:
Total Solution 92, done! 学习学习
学习一下 jerryxjr1220 发表于 2017-2-6 14:15
利用回溯法求解八皇后（N皇后）问题也是非常经典的运用。
八皇后问题，是一个古老而著名的问题，是回溯 ...
有点下复杂 我觉的还是先了解回溯 总觉得理解BFS和DFS了，但就是解决不了题目……很伤心啊 WelanceLee 发表于 2017-6-14 10:06
总觉得理解BFS和DFS了，但就是解决不了题目……很伤心啊
DFS和BFS其实算法的结构是相同的，无非是处理序列的顺序不同，一个优先广度，一个优先深度。
一般利用递归法（回溯法）的，写深度优先比较容易。循环迭代法的，写广度优先比较容易（写深度优先其实也容易，换个顺序而已）。
落实到全排列问题，其实可以利用迭代插入法。
举个例子：如果abc需要全排列。
字符串 排列组合
step1：abc []
step2: bc
step3: c
step4: ''
每次从字符串中取出第一个字母，依次插入到列表中的每个元素中，直到字符串为空。
是不是很简单？ jerryxjr1220 发表于 2017-6-14 10:28
DFS和BFS其实算法的结构是相同的，无非是处理序列的顺序不同，一个优先广度，一个优先深度。
一般利用递 ...
这个确实帅啊~ WelanceLee 发表于 2017-6-14 10:34
这个确实帅啊~
看懂了，就写个迭代插入法的程序练练手啊{:10_256:} 本帖最后由 WelanceLee 于 2017-6-14 13:00 编辑
jerryxjr1220 发表于 2017-6-14 10:39
看懂了，就写个迭代插入法的程序练练手啊
## 迭代插入法
n = 5
a =
b = []
a.pop()
while a:
x = a.pop()
n = len(b)# 当前排列个数
m = len(b) + 1 # 可插入的位置
i = 0 # 计录完成更新的次数（个数增加1）
while i < n:
for j in range(m):
y = b[:]
y.insert(j, x)
b.append(y)
b.pop(0)
i += 1
for each in b:
print(each)
搞了好久，感觉不像我看的那样简单啊{:5_107:} 看看 WelanceLee 发表于 2017-6-14 12:59
搞了好久，感觉不像我看的那样简单啊
用递归写了一个，也是插入法
def permutations(strings, lst=['']):
if strings == '':
return lst
else:
new = set()
for i in lst:
for j in range(len(i) + 1):
new.add(i[:j] + strings + i)
return permutations(strings, list(new)) jerryxjr1220 发表于 2017-6-14 14:05
用递归写了一个，也是插入法
果然看着更舒服些{:5_106:} 来看看
{:5_102:}
class P():
def __init__(self,n):
self.len = n
self.lst =
self.visit = []
self.sign = []
def pai(self,lst,sign):
for i,j in enumerate(lst):
sign1 = sign[:]
lst1 = lst[:]
sign1.append(j)
lst1.remove(j)
if len(sign1) == self.len:
print(sign1)
return True
self.pai(lst1,sign1)
P1 = P(5)
P1.pai(P1.lst,P1.sign) 看看 {:5_92:} 学习学习
页:
[1]
2