回溯( Backtracking)基本原理 2007年9月26日 张铭
回溯算法 1 回溯(Backtracking)基本原理 2007年9月26日 张铭
认识“回溯” 感性认识——皇后问题 解空间树 ■搜索过程 直观分析 原理描述 总体步骤 ■搜索过程 ■实现方式 方式一:递归回溯 方式二:迭代回溯 效率分析 回溯算法
回溯算法 2 认识“回溯” 感性认识——皇后问题 解空间树 搜索过程 直观分析 原理描述 总体步骤 搜索过程 实现方式 方式一：递归回溯 方式二：迭代回溯 效率分析
八皇后问题 问题描述:在国际象棋的8*8格棋盘上放置8 个皇后,使任意两个皇后不在同一行上,不在 同一列上,不在同一条斜角线上 设第1个皇后放在第一行的x1位置,第个皇后 放在第行的x位置,则八皇后问题的一个解可 以表示为一个向量(x1x2…yxg)显然 x1xy…xg是(12…8)的一个排列;所有可 能的向量(可能解)有8!个 回溯算法
回溯算法 3 八皇后问题 问题描述：在国际象棋的8*8格棋盘上放置8 个皇后，使任意两个皇后不在同一行上，不在 同一列上，不在同一条斜角线上。 设第1个皇后放在第一行的x1位置，第i个皇后 放在第i行的xi位置，则八皇后问题的一个解可 以表示为一个向量(x1,x2,...,x8);显然 x1,x2,...x8是(1,2,...,8)的一个排列；所有可 能的向量（可能解）有8!个
八皇后问题的一个解图示 Q Q对应的向量 Q (4,6,8,2,71,35) Q Q 回溯算法
回溯算法 4 八皇后问题的一个解图示 Q Q Q Q Q Q Q Q 对应的向量： (4,6,8,2,7,1,3,5)
四皇后问题及其解空间树 解表示成一个4维向量,<M1,2,8,A4> (放置列号) Q 搜索空间:4叉树(排列树)
回溯算法 5 四皇后问题及其解空间树 1 2 4 3 5 6 7 4 3 9 8 10 11 12 2 4 4 2 3 14 13 15 16 17 2 3 3 2 4 X1=1 18 20 19 21 22 23 3 4 4 3 1 25 24 26 27 28 1 4 4 1 3 30 29 31 32 33 1 3 3 1 4 2 34 36 35 37 38 39 2 4 4 2 1 41 40 42 43 44 1 4 4 1 2 46 45 47 48 49 1 2 2 1 4 3 50 52 51 53 54 55 2 3 3 2 1 57 56 58 59 60 1 3 3 1 2 62 61 63 64 65 1 2 2 1 3 4 X2=2 X3=3 X4=4 Q Q Q Q 解表示成一个4维向量，<x1,x2,x3,x4> （放置列号） 搜索空间：4叉树（排列树）