数据结构16.ppt

上传人:p** 文档编号:160572 上传时间:2023-03-02 格式:PPT 页数:84 大小:275.50KB
下载 相关 举报
数据结构16.ppt_第1页
第1页 / 共84页
数据结构16.ppt_第2页
第2页 / 共84页
数据结构16.ppt_第3页
第3页 / 共84页
数据结构16.ppt_第4页
第4页 / 共84页
数据结构16.ppt_第5页
第5页 / 共84页
数据结构16.ppt_第6页
第6页 / 共84页
数据结构16.ppt_第7页
第7页 / 共84页
数据结构16.ppt_第8页
第8页 / 共84页
数据结构16.ppt_第9页
第9页 / 共84页
数据结构16.ppt_第10页
第10页 / 共84页
亲,该文档总共84页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构16.ppt》由会员分享,可在线阅读,更多相关《数据结构16.ppt(84页珍藏版)》请在第壹文秘上搜索。

1、第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

2、节点例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、于搜索的方式组织该空间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 configurati

4、on中每个未被攻击的位置中每个未被攻击的位置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 s

5、ize 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 configurati

6、on(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

7、 (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(

8、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_sol

9、ved() 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: i

10、nt 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

11、 = 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;

12、/ 如果在列和对角线上发现其它皇后,如果在列和对角线上发现其它皇后, 置为置为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

13、& 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

14、.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, boa

15、rd_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一个棋盘格是否安全三

16、个数组对应元素是否全为真新的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

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!