该篇学习笔记来自于《你也能看得懂的python算法书》
什么是回溯?简单来说,回溯采用试错的方法解决问题,一旦发现当前步骤失败,回溯方法就返回上一个步骤,选择另外一种方案继续试错。
回溯算法针对的大多数问题有如下特色:问题的答案有多个元素(可想象成走迷宫是有多个决定)、答案须要一些约束(好比数独)、寻找答案的方式在每个步骤相同。回溯算法逐步构建答案,并在肯定候选元素不知足约束后马上放弃候选元素(一旦碰墙就返回),直到找到答案的全部元素。
python
问题描述:
你玩过报纸上那种查找单词的游戏吗?就是那种在一堆字母中横向或竖向找出单词的游戏。小明在玩一个和那个很像的游戏,只不过如今不只能够上下左右链接字母,还能够拐弯。如图所示,输入world,将会输出"找到了"
。程序员
a | e | r | y | l |
---|---|---|---|---|
l | w |
o |
r |
r |
a | f | d |
l |
e |
k | e | e | w | e |
o | d | r | o | s |
class solution(): def wordresearch(self,board,word): for i in range(len(board)):#遍历盘面 for j in range(len(board[0])): if self.helper(board,word,i,j): return True print("没有找到此单词") return False def helper(self,board,current,row,column): if len(current)==0:#结束条件 print("找到了")#以此输出做为标志,不然没法辨别True和False return True if row>=0 and row<len(board) and column>=0 and column<len(board[0]) :#前提条件 if board[row][column]==current[0]: board[row][column]="" if self.helper(board,current[1:],row+1,column):#上下左右检查剩余字母 return True if self.helper(board,current[1:],row-1,column): return True if self.helper(board,current[1:],row,column+1): return True if self.helper(board,current[1:],row,column-1): return True board[row][column]=current[0]#若初次搜寻后没找到该单词,复原首字母,防止影响之后查找 return False board=[["a","c","r","y","l"],["l","w","o","r","i"],["a","f","d","l","c"],["k","e","e","w","e"], ["o","d","r","o","s"]] solution().wordresearch(board,"world")
问题描述:
小明最近有4本想读的书:《红色的巴黎》、《黄色的梧桐树》、《蓝色的夏天》、《绿色的天空》,若是小明每次只能从图书馆借一本书,他一共有多少种借书的顺序呢?web
class solution: def solvepermutation(self,array): self.helper(array,[]) def helper(self,array,solution): if len(array)==0: print(solution) return for i in range (len(array)): newarray=array[:i]+array[i+1:]#删除书本 newsolution=solution+[array[i]]#加入新书 self.helper(newarray,newsolution)#寻找剩余对象的排列组合 solution().solvepermutation(["红","黄","蓝","绿"])
问题描述:
小明想上两门选修课,他有四种选择:A微积分,B音乐,C烹饪,D设计,小明一共有多少种不一样的选课组合呢?算法
class solution(): def solvecombination(self,array,n): self.helper(array,n,[]) def helper(self,array,n,solution): if len(solution)==n: print(solution) return for i in range(len(array)): newarray=array[i+1:]#建立新的课程列表,更新列表,即选过的课程不能再选 newsolution=solution+[array[i]]#将科目加入新的列表组合 self.helper(newarray,n,newsolution) solution().solvecombination(["A","B","C","D"],2)
问题描述:
保安负责人小安面临一个难题,他须要在一个8x8千米的区域里修建8个保安站点,并确保每一行、每一列和每一条斜线上都只有一个保安站点。苦恼的小安试着尝试布置了不少遍,但每一次都不符合要求。小安求助程序员小明,没过多久小明就把好几个布置方案(实际上,这个问题有92种答案)发给了小安,其中包括下面执行结果截图,试问小明是怎么作到的。svg
class solution(object): def solvequeens(self,n): self.helper([-1]*n,0,n)#初始化当前行数为0 def helper(self,columnpositions,rowindex,n): if rowindex==n: self.printsolution(columnpositions,n) return#单独的return出现表示结束该层函数 for column in range(n): columnpositions[rowindex]=column if self.isValid(columnpositions,rowindex): self.helper(columnpositions,rowindex+1,n)#继续假设剩余保安位置 def isValid(self,columnpositions,rowindex): for i in range(rowindex): if columnpositions[i]==columnpositions[rowindex]:#检查同列是否有保安 return False elif abs(columnpositions[i]-columnpositions[rowindex])==rowindex-i:#检查两条斜线上是否有保安 return False return True def printsolution(self,columnpositions,n): for i in range(n): line="" for j in range(n): if columnpositions[i]==j: line+='Q ' else: line+='. ' print(line) print("\n") solution().solvequeens(8)
代码执行结果:Q表明保安站点,共有92种方案,如下为部分截图
函数
问题描述:
在玩数独的时候,计算机程序可以马上得出答案,它是怎么得出结果的呢?填数独就像在走迷宫,没有地图,每个岔路口都只能以探索的方式前进,一旦发现路线不对就返回岔路口,选择另外一个分支,并且每个岔路口都有9种选择,但咱们确定末端有一个出口。学习
class solution(): def solvesudoku(self,board): self.helper(board,0) def helper(self,board,index): if index>=81: self.printsolution(board) return if board[index]==0: for i in range(1,10): if self.isValid(board,index,i): board[index]=i#填入数字 self.helper(board,index+1) board[index]=0#若不知足条件,恢复原0值,防止影响以后数字的填写 else:#若是当前格有已知数,跳出此格 self.helper(board,index+1) def printsolution(self,board): for i in range(0,81,9): print(board[i:i+9])#注意输出格式 def isValid(self,board,index,num): row=index//9#当前格子行数 column=index%9#当前格子列数 for i in range(index+9,81,9):#检查和同列(下方)的格子是否合理 if board[i]==num: return False for i in range(index-9,-1,-9):#检查和同列(上方)的格子是否合理 if board[i]==num: return False for i in range(row*9,(row+1)*9):#检查和同行的格子是否矛盾 if board[i]==num: return False for i in range(row-row%3,3+row-row%3):#检查和同粗线的格子是否有矛盾 for j in range(column-column%3,3+column-column%3): if board[i*9+j]==num: return False return True board=[4,1,0,0,0,7,8,5,0, 8,0,6,0,0,0,0,0,9, 0,2,0,0,9,0,6,0,0, 0,0,4,0,0,0,0,1,2, 2,0,0,5,8,0,0,7,0, 0,0,0,0,0,0,5,0,0, 0,0,0,7,0,2,0,0,0, 0,0,8,0,1,0,0,0,0, 0,7,0,0,6,0,0,0,0] solution().solvesudoku(board)
代码执行结果:
ui