数据结构16.ppt

第16章 回溯学习内容m算法思想m应用q八皇后问题q货箱装船q0/1背包问题q最大完备子图问题q旅行商问题q电路板排列16.1 算法思想m在众多可能解中搜索可行解/最优解m解空间至少包含一个可行解q迷宫老鼠问题：入口出口的所有路径qn个对象的0/1背包问题：所有n位二进制数，每个二进制位表示对象是否放入背包m如何组织解空间？树或图例16.1 迷宫问题m活节点，E节点例16.1 迷宫问题（续）m开始节点为活节点，E节点q若当前E节点可移动到一个新节点，则新节点变为活节点和新的E节点，旧节点仍为活节点q若不能移动到新节点，则当前E节点变为“死节点”，需返回最近考察的活节点（回溯），该节点重新成为E节点例16.2 0/1背包问题mn=3，w=20, 15, 15，p=40, 25, 25且c=30m节点B：r=10, cp=40；移动到D不可行，E可行m节点E，移动到J不可行，K可行可行解m回溯到AC：r=30, cp=0，FL最优解例16.3 旅行商问题m给定n顶点网络，找出包含所有顶点的最小耗费环路商人在城市间旅行，寻找最小花费（时间）的旅行m下图：13241，耗费25例16.3 旅行商问题（续）m钻孔问题、批量生产问题回溯算法框架m子集树、排列树m简单回溯：计算量太大m加速分支限界函数不考察不可能产生最优解的节点回溯算法框架m回溯法基本步骤1.定义一个解空间，它包含问题的解2.用适于搜索的方式组织该空间3.用深度优先搜索该空间，用限界函数加速m搜索同时产生解空间m内存需求：开始节点起最长路径长度16.2 应用m八皇后问题q在国际象棋棋盘上放置8个皇后q任何两个皇后之间都不能相互攻击解决方法m随机放置显然不行，也不存在某种规则m无遗漏地找出所有解，非常困难solve_from(Queens configuration)solve_from(Queens configuration)if configuration if configuration 已包含已包含8 8个皇后个皇后打印结果打印结果elseelsefor configurationfor configuration中每个未被攻击的位置中每个未被攻击的位置p p 在在configurationconfiguration中位置中位置p p添加一个皇后添加一个皇后solve_from(configuration);solve_from(configuration);将将configurationconfiguration中位置中位置p p的皇后去掉的皇后去掉 四皇后问题求解示例主函数intint main() main() int int board_size; board_size; print_information(); print_information(); cout What is the size of the board? cout What is the size of the board? board_size; board_size;if (board_size max_board)if (board_size max_board) cout The number must be between 0 and cout The number must be between 0 and max_board endlmax_board endl; ; else else Queens configuration(board_size); / Queens configuration(board_size); / 初始化空棋局初始化空棋局 solve_from(configuration); / solve_from(configuration); / 搜索所有解搜索所有解 回溯函数void solve_from(Queens &configuration)void solve_from(Queens &configuration) if (configuration.is_solved() configuration.print(); if (configuration.is_solved() configuration.print(); else else for (int col = 0; col configuration.board_size; for (int col = 0; col configuration.board_size; colcol+)+) if (configuration.unguarded(col if (configuration.unguarded(col) ) configuration.insert(col configuration.insert(col);); solve_from(configuration); solve_from(configuration); configuration.remove(col configuration.remove(col);); Queens类m应提供的方法q打印棋局q添加皇后（向下一节点移动）q删除皇后（回溯）q判定棋盘格是否受到皇后攻击m添加皇后不必尝试每个棋盘格q每个皇后必定独自占据一行、一列q每行放置一个皇后qcount：已放置皇后数目下一皇后行号Queens类定义const intconst int max_board = 30; max_board = 30;class Queens class Queens public:public: Queens(int size); Queens(int size); bool bool is_solved() const; is_solved() const; void print() const; void print() const; bool unguarded(int col bool unguarded(int col) const;) const; void insert(int col void insert(int col);); void remove(int col); void remove(int col); int int board_size; / board_size; / 棋盘大小棋盘大小要放置的皇后数目要放置的皇后数目private:private: int int count; / count; / 已放置皇后数目，下一个皇后所在行号已放置皇后数目，下一个皇后所在行号 boolbool queen_squaremax_boardmax_board; queen_squaremax_boardmax_board;构造函数和添加函数Queens:Queens(intQueens:Queens(int size) size) board_size = size; board_size = size; count = 0; count = 0; for (int for (int row = 0; row board_size; row+) row = 0; row board_size; row+) for (int col = 0; col board_size; col for (int col = 0; col 0）q终止条件：row i = 0（上边界） col i = 0（左边界）q循环条件row i =0 & col i =0m左下、右下无需检查下方还未放皇后unguarded函数实现bool Queens:unguarded(int colbool Queens:unguarded(int col) const) const int i; int i; bool bool ok = true; / ok = true; / 如果在列和对角线上发现其它皇后，如果在列和对角线上发现其它皇后， 置为置为falsefalse，不再进行检查，不再进行检查 for (i = 0; ok & i count; i+)for (i = 0; ok & i = 0 & colfor (i = 1; ok & count - i = 0 & col - i = 0; i+) - i = 0; i+) ok = !queen_squarecount - icol ok = !queen_squarecount - icol - i; / - i; / 检查左上检查左上 for (i = 1; ok & count - i = 0 & colfor (i = 1; ok & count - i = 0 & col + i board_size; i+) + i board_size; i+) ok = !queen_squarecount - icol ok = !queen_squarecount - icol + i; / + i; / 检查右上检查右上 return ok;return ok; 优化m上述简单算法对8皇后问题已足够m但当棋盘规模增大，运行时间急剧增加棋盘大小棋盘大小8910111213解的数目解的数目9235272426801420073712时间（秒）时间（秒）0.050.211.176.6239.11243.05单个解时间单个解时间（毫秒）（毫秒）0.540.501.622.472.753.30程序瓶颈在哪里？m递归调用和回溯过程，耗费了很多时间，但这是程序的基本算法和框架，没有优化余地munguarded函数，使用了多个循环，耗费很多时间可考虑进行优化unguarded函数的优化思想m关键每列、每行、每条对角线都至多允许放置一个皇后m使用三个bool类型数组qcol_freei：真第i列没有皇后qupward_freei：真第i个左下右上的对角线没有皇后qdownward_freei：真左上右下的对角线没有皇后上对角线的处理m最长的左下右上对角线board_size-10, board_size-21, ., 0board_size-1m行列下标之和为定值qrow + col = (row i) + (col + i)q用此值标识对角线左上角对角线（只含一个棋盘格），此值为0向右下，第二条对角线，1.右下角最后一条对角线，2*board_size-2q棋盘格(i, j)，所在左上对角线为i+j下对角线的处理m行列下标之差为定值row col = (row + i) (col + i)m取值范围-board_size+1board_size-1m调整为02*board_size-1m棋盘格(i, j)所在下对角线为i j + board_size 1m一个棋盘格是否安全三个数组对应元素是否全为真新的Queens类class Queens class Queens public:public: Queens(int size); Queens(int size); bool bool is_solved() const; is_solved() const; void print() const; void print() const; bool unguarded(int col bool unguarded(int col) const;) const; void insert(int col void insert(int col);); void remove(int col); void remove(int col); int int board_size; board_size;private:private: int count; int count; bool col_freemax_board; bool col_freemax_board; bool upward_free2 bool upward_free2 * * max_bo