基本算法设计策略搜索策略-2016

1、1V.搜索策略搜索策略 GPS: General Problem Solving Prolog: logical language 基本搜索方法 Bread First Serach 宽度优先搜索 Depth First Search 深度优先搜索 Hill Climbing 爬山法 回溯 启发式 251 DFS和BFS DFS：首先访问指定起始点，然后取与之相临的任一未被访问的顶点，依DFS模式访问之。给定图G=(V,E)，有n个顶点(|V|=n)，设置全局的visitedn:节点是否被访问过的标志，初始赋为false,该算法访问所有自v出发可达的点。void dfs (int v ) in

2、t w;visitedv = true;for each vertex w adjacent to v do if ( !visitedw) dfs(w) 3DFSDFS搜索路径搜索路径穷尽下面搜索路径，浪费时间多。 V1V3V2V7V5V4V6V84BFSBFS：从访问起始顶点出发，访问该顶点的全部邻接顶点，在对起始点的全部邻接点的邻接点进行访问。 图G=(V,E)，访问标志visitedn，Queue队列 5BFS算法void bfs(int v) int w; Queue q; visitedv=ture; q.initialize(); q.add(v); /初始化访问结点：根层 wh

3、ile (!q.isEmpty() /若干处理v = q.delete();for all vertices w adjacent to v doif(!visitedw) q.add(w);visitedw = true; /of while 注意其处理过程利用STL：q.empty()cur=q.front(); q.pop_front();q.push_back()68-迷问题 华容道，移动白块成目标模式752 爬山法 若有某种方法能对每一个结点下面的分支进行排序，使最有希望的分支首先被探索。爬山法爬山法：深度优先+对每一决策点可能路径进行排序。 可能问题：1） Foothill Pro

4、blem 山脚问题（小丘问题） 局部极小点。2） Ridge Problem 山脊问题3）Plateau Problem 高原问题 在山下穿行 最速下降法Steepest Descent 求函数的极小化值 Taylor展开 令 得 即 故得到修正公式8nRXXf),(min)(21)()()(2XfXfXfXfTT0)(Xf0)()(2XfXf)()(12XfXf)()(12XfXfXX9共轭梯度法（1）考虑A：nn对称正定, X，BEn, C常数。共轭：X，Y关于A共轭（A为nn正定阵）共轭为正交的推广：取A=I时即正交。共轭梯度法为共轭向量法的一种，用当前极小点的梯度CXBAXXxfTT2

5、1)(min0AYXT10共轭梯度法（2）方法：（1）给定X(0)，给出误差0（2）计算 ， 用下式计算)(0)0(XfP)1(X)0(0)0()1(PXX)0()0(0)0(0)()(APPPXfTT11共轭梯度法（3）（3）假定已得出 和 第k+1次近似 （4）若 停止计算；否则，若k n-1，则计算转至（3）。 )(kX)(kP)()()1(kkkkPXX)(min:)()(kkkPXf2)1()(kXf)()()()()()()1()1(kTkkTkkXfXfXfXf)()1()1()(kkkkPXfP)()()()()()(kTkkTkkAPPPXf1253 回溯法Backtrack

6、ing GPS求解不是根据固定规则，而是采用试错法(trail and error)(或：“摸着石头过河”)。将整个过程分为多个部分任务，每个部分的任务一般可递归的表达。包含多个子任务。整个求解（搜索）过程是建立树，扫描树（剪枝）的过程。 一般是指数的，通过启发式规则改进。 13皇后问题(1)例5.3.1.8皇后问题首先考虑四皇后问题S0 1 2 3 1 2 3 0 2 3 2 3 1 3 1 2 2 3 0 3 2 03 2 3 1 2 1 3 2 3 0 0 2X1X2X4X314皇后问题(2)对于不成功的点，返回上层。 01230 Q 1 Q2Q 3 Q 15皇后问题(3)模式：void

7、 try (int i ) initialize selection of positionsfor i+h queen;do make next selection;if(safe) setqueen;if(i(n-1) /n皇后try(i+1);if (!successful)remove queen; /回溯 while (!successful & more - positions);16皇后问题(4)int xN;bool aN ,b2*N-1 , c2*N-1 ；xi：第i列皇后位置aj：无皇后在第j行时为真bk：第k条 / 对角线上无皇后 ck：第k条 对角线上无皇后 位

8、于对角线 / 上：（i,j）,(i+1,j-1), 即i+j一定位于对角线 上：（i,j）,(i+1,j+1), 即i-j一定根据Wirth Pascal 程序改！17皇后问题(5)bool try (int row) int col=-1;bool q=false;docol+; q=false;if (acol&brow+col&crow-col+(N-1) acol=brow+col=crow-col+N-1=false;xrow=col;if (rowN-1) if (!try(row+1)acol=brow+col=crow-col+N-1=true; else q=

9、false;else q=true;while(!q&col340,故需对R3继续分解：R6： R7： R6 R7故最优解： ， ， max12x22x000. 1444. 576.30721xxz无可行解41x22x340z26例 5.4.1 求解整数规划 （4）分支界限法对解纯整数和混合整数问题都是使用的。仅要求是整数时： max R1：R2：R3：R4：R5：R6：R7：无可行解890.355817. 1809. 421zxx0 .349100. 2000. 421zxx390.341571. 100. 521zxx340000. 2000. 421zxx12.327000. 3

10、428. 121zxx76.307000. 1444. 521zxx41x1 . 22x0 .349z27例 5.4.2 背包问题 (1)n=6，M=18，权重 6 ， 10 ， 3 ，8 ， 5 ， 4 利润（profit） 20 ， 31 ， 9 ，21 ， 13 ， 10注意 ：20/6 ，31/10 ，9/3 ，21/8 ，13/5 ，10/4递减WPi28剪枝DFS 29剪枝DFS元组：（Weights, Profits, Lower Bound, Upper Bound）其中：下界：所给填充之下的可行最大填充。 上界：利用贪婪法计算出连续填充的最大值 比如节点5：下界：上界：200

11、0000206000006pw)0 , 0 , 1 , 1 , 0 , 1 (ex500021902017008306eepw)0 ,51, 1 , 1 , 0 , 1 (ux6 .5251132190201805158306uupw)0 , 0 , 0 , 0 , 0 , 1 (x30最优最先剪枝（Best-First Search with Pruning） 0, 0, 51, 576, 20, 51, 570, 0, 52, 53.12516, 51, 51, 576, 20, 50, 52.610, 31, 52, 53.1250, 0, 43, 4816, 51, 51, 56.25

12、16, 51, 51, 56.216, 51, 51, 5616 , 5113, 40, 52, 53.12510, 31, 52, 5213, 40, 53, 5310, 31, 52, 53.12518, 53, 53, 53 18 , 53 31求解TSP问题 (1)首先得到一条初始的路径：比如：A-E-C-G-F-D-B-H-A长度：28 ABCDEFGHA-47641089B8-1493462C79-1110957D16 68-5779E1325-867F128532-1013G957963-4H3968579-32求解TSP问题 (2)定义启发式界限函数依据局部信息，给出一个不足的

13、下界已知每一个节点到相邻点的最小值，所以，最小值还会小于25)()()(xgxaxh源点目的地距离AB4BH2CG5DE5EA1FE2GF3HA3 2533求解TSP问题 步骤（1）步骤：1 从A出发计算其它点的路径长；2 最小的路径长为25-4=21（去掉A的路径）；3 根据实际路径计算A至BCDEFG各点的下界值；4.由于已经找到一条侯选路径长为28，故大于28各点补剪去，只有BDE为有希望节点（PROMISING NODE）； 34求解TSP问题 步骤（2）5. 继续展开有希望的节点（E1，B1，D1） 35求解TSP问题 步骤（3）6. 将节点E完全展开，再进行剪枝。当两个节点有相同 的界限值时，选择与当前解更近的点。活动节点列表（C2，B1，B2，D1） 36求解TSP问题 步骤（4）7. 去C2加入G3（G3，B1，B2，D1） 37求解TSP问题 步骤（5）8展开节点G给出更有希望的F4和H4，则活动节点表变为：（F4，B1，H4，B2，D1） 9节点的值均大于25，故B1被移到前面，活动列表（B1，D5，H4，B2，D1） 38求解TSP问题 步骤（6）10活动列表（H2，D5，H4，B2，D1），子节点均剪掉11活动列表（D5，H4，B2，D1），子节点均剪掉 39求解TSP问题 步骤（7）13将H4展开后