Python 回溯算法

回溯算法（试探法）

在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法解决问题的

• 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
• 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
• 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

实例：

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
每一次只能向左，右，上，下四个方向移动一格，
但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

class Solution:def movingCount(self, threshold, rows, cols):"产生 0 矩阵 "board=[[0 for i in range(cols)] for j in range(rows)]global accacc = 0"下标之和,若大于threshold则TRUE,否则Folse"def block(r,c):s=sum(map(int,str(r)+str(c)))return s>thresholddef traverse(r,c):global accif not (0<=r<rows and 0<=c<cols): # 超出角标范围挑出returnif board[r][c]!=0: # 不等于0 跳出returnif board[r][c]==-1 or block(r,c):board[r][c]=-1 #超出门限的点记录-1returnboard[r][c]=1 #符合规定的点记录1，并计数加一acc+=1traverse(r+1,c)traverse(r-1,c)traverse(r,c+1)traverse(r,c-1)traverse(0,0)return acco = Solution() print(o.movingCount(4 ,3 ,3))# 输出结果： 9

转载于:https://www.cnblogs.com/spmt/p/10607027.html

总结

以上是生活随笔为你收集整理的Python 回溯算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。