wordpress自定义,青岛seo招聘,wordpress 导航主题,wordpress网站做成app6作者简介#xff1a;大家好#xff0c;我是smart哥#xff0c;前中兴通讯、美团架构师#xff0c;现某互联网公司CTO 联系qq#xff1a;184480602#xff0c;加我进群#xff0c;大家一起学习#xff0c;一起进步#xff0c;一起对抗互联网寒冬 学习必须往深处挖… 作者简介大家好我是smart哥前中兴通讯、美团架构师现某互联网公司CTO 联系qq184480602加我进群大家一起学习一起进步一起对抗互联网寒冬 学习必须往深处挖挖的越深基础越扎实
阶段1、深入多线程阶段2、深入多线程设计模式阶段3、深入juc源码解析阶段4、深入jdk其余源码解析阶段5、深入jvm源码解析
回溯法
回溯法也叫试探法试探的处事方式比较委婉它先暂时放弃关于问题规模大小的限制并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时则继续扩大当前候选解的规模并继续试探。如果当前候选解满足包括问题规模在内的所有要求时该候选解就是问题的一个解。在试探算法中放弃当前候选解并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模以继续试探的过程称为向前试探。
使用回溯法解题的基本步骤如下所示
(1)针对所给问题定义问题的解空间。 (2)确定易于搜索的解空间结构。 (3)以深度优先方式搜索解空间并在搜索过程中用剪枝函数避免无效搜索。
回溯法为了求得问题的正确解会先委婉地试探某一种可能的情况。在进行试探的过程中一旦发现原来选择的假设情况是不正确的马上会自觉地退回一步重新选择然后继续向前试探如此这般反复进行直至得到解或证明无解时才死心。
效率分析
下面是回溯的3个要素。 (1)解空间表示要解决问题的范围不知道范围的搜索是不可能找到结果的。 (2)约束条件包括隐性的和显性的题目中的要求以及题目描述隐含的约束条件是搜索有解的保证。 (3)状态树是构造深搜过程的依据整个搜索以此树展开。 回溯算法适合解决没有要求求最优解的问题。如果采用一定要注意跳出条件及搜索完成的标志否则会陷入泥潭不可自拔。 下面是影响算法效率的因素
搜索树的结构解的分布约束条件的判断。改进回溯算法的途径。搜索顺序。节点少的分支优先解多的分支优先。让回溯尽量早发生。
回溯法搜索解空间时通常采用两种策略避免无效搜索提高回溯的搜索效率:
用约束函数在扩展结点处剪除不满足约束的子树用限界函数剪去得不到问题解或最优解的子树。 例题 N皇后问题在一个N*N大小的国际象棋棋盘上放置N个皇后棋子使得所有的皇后都是安全的(即任意两个皇后都无法攻击到对方)。 分析
为缩小规模我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则皇后的攻击方式是横竖和斜向。 皇后可以攻击到同一列所有其它棋子因此可推导出每1列只能存在1个皇后即每个皇后分别占据一列。棋盘一共8列刚好放置8个皇后。
为了摆放出满足条件的8个皇后的布局可以按如下方式逐步操作
在第0行找到一个位置放置第1个皇后在第1行找到一个位置放置第2个皇后在第2行找到一个位置放置第3个皇后对第34567行都执行放置操作当执行完“在第7行找到一个放置第8个皇后”这一操作完毕后问题求解完毕。 观察1234 这些操作步骤可以发现是一个重复的动作抽象一下即“在第 n 行放下第 n1 个皇后”n 从0到7。
把规模放大到N行N列也一样下面用回溯法解决N皇后问题 Go语言描述 const N 8func NQueens() {// 开辟一个一维数组保存可能的结果result : make([]int, N)// 从第一行开始试探放置棋子place(result, 0)}// 递归在保证已放置行安全情况下放置下一行棋子func place(result []int, row int) {// 所有行棋子放满后输出if row N {fmt.Println(result) // 输出答案return}// 逐列试探for column : 0; column N; column {// 试探在 column 列 处放下棋子并检验是否安全result[row] columnif safe(result, row) {// 棋子安全放置下一行棋子place(result, row1)}}}// 验证当前棋子是否安全func safe(result []int, row int) bool {// 循环验证是否互相攻击for c : 0; c row; c {if isAttack(result, c, row) {return false}}return true}// 攻击试探如果被攻击则返回truefunc isAttack(result []int, c int, row int) bool {switch {case result[c] result[row]:return truecase result[row]-result[c] c-row:return truecase result[row]-result[c] row-c:return true}return false}执行 func TestNQueens(t *testing.T) {NQueens()} RUN TestNQueens[0 4 7 5 2 6 1 3][0 5 7 2 6 3 1 4][0 6 3 5 7 1 4 2][0 6 4 7 1 3 5 2][1 3 5 7 2 0 6 4][1 4 6 0 2 7 5 3][1 4 6 3 0 7 5 2][1 5 0 6 3 7 2 4][1 5 7 2 0 3 6 4][1 6 2 5 7 4 0 3][1 6 4 7 0 3 5 2][1 7 5 0 2 4 6 3][2 0 6 4 7 1 3 5][2 4 1 7 0 6 3 5][2 4 1 7 5 3 6 0][2 4 6 0 3 1 7 5][2 4 7 3 0 6 1 5][2 5 1 4 7 0 6 3][2 5 1 6 0 3 7 4][2 5 1 6 4 0 7 3][2 5 3 0 7 4 6 1][2 5 3 1 7 4 6 0][2 5 7 0 3 6 4 1][2 5 7 0 4 6 1 3][2 5 7 1 3 0 6 4][2 6 1 7 4 0 3 5][2 6 1 7 5 3 0 4][2 7 3 6 0 5 1 4][3 0 4 7 1 6 2 5][3 0 4 7 5 2 6 1][3 1 4 7 5 0 2 6][3 1 6 2 5 7 0 4][3 1 6 2 5 7 4 0][3 1 6 4 0 7 5 2][3 1 7 4 6 0 2 5][3 1 7 5 0 2 4 6][3 5 0 4 1 7 2 6][3 5 7 1 6 0 2 4][3 5 7 2 0 6 4 1][3 6 0 7 4 1 5 2][3 6 2 7 1 4 0 5][3 6 4 1 5 0 2 7][3 6 4 2 0 5 7 1][3 7 0 2 5 1 6 4][3 7 0 4 6 1 5 2][3 7 4 2 0 6 1 5][4 0 3 5 7 1 6 2][4 0 7 3 1 6 2 5][4 0 7 5 2 6 1 3][4 1 3 5 7 2 0 6][4 1 3 6 2 7 5 0][4 1 5 0 6 3 7 2][4 1 7 0 3 6 2 5][4 2 0 5 7 1 3 6][4 2 0 6 1 7 5 3][4 2 7 3 6 0 5 1][4 6 0 2 7 5 3 1][4 6 0 3 1 7 5 2][4 6 1 3 7 0 2 5][4 6 1 5 2 0 3 7][4 6 1 5 2 0 7 3][4 6 3 0 2 7 5 1][4 7 3 0 2 5 1 6][4 7 3 0 6 1 5 2][5 0 4 1 7 2 6 3][5 1 6 0 2 4 7 3][5 1 6 0 3 7 4 2][5 2 0 6 4 7 1 3][5 2 0 7 3 1 6 4][5 2 0 7 4 1 3 6][5 2 4 6 0 3 1 7][5 2 4 7 0 3 1 6][5 2 6 1 3 7 0 4][5 2 6 1 7 4 0 3][5 2 6 3 0 7 1 4][5 3 0 4 7 1 6 2][5 3 1 7 4 6 0 2][5 3 6 0 2 4 1 7][5 3 6 0 7 1 4 2][5 7 1 3 0 6 4 2][6 0 2 7 5 3 1 4][6 1 3 0 7 4 2 5][6 1 5 2 0 3 7 4][6 2 0 5 7 4 1 3][6 2 7 1 4 0 5 3][6 3 1 4 7 0 2 5][6 3 1 7 5 0 2 4][6 4 2 0 5 7 1 3][7 1 3 0 6 4 2 5][7 1 4 2 0 6 3 5][7 2 0 5 1 4 6 3][7 3 0 2 5 1 6 4]--- PASS: TestNQueens (0.00s)PASS
