数句结构——深(广)度搜索

《数句结构——深(广)度搜索》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1•“根”入栈.2.Repeat:TryTheTop(1)死节点：“出栈操作”(即”回溯”).(2)叶结点：得到了一个完整的解向量，“输出路径”；“出栈操作”(即”回溯”).(3)活结点(还有未展开处理的子节点):”展开”,即下一个未展开处理的子节点”入栈”•(即对子节点进行求解，也称展开它•)Until栈空.NOTE:(1)路径所历经的分枝上的值构成一个完整的解向量，一个完整的解向量产生原问题的一个解.(2)”回溯”即舍弃了当前解向量(不一定是完整的)的最后一个分量,因此对所保存的解的有关信息要进行修正，即使解变回到没有展开该节点之前的状态.(3)”入栈”既展开了一个节点，当前解向

2、量(不一定是完整的)的最后增加了一个分量，因此也要对所保存的解的有关信息要进行修正.1.“根”入队2.Repeat:队首节点”出队”并且TryIT(1)死节点：“无操作”•(2)叶结点：得到了一个完整的解向量，“输出路径”(用回溯的方式)；(3)活结点(还有未展开处理的子节点):”展开它”,即ALL未展开处理的可行的子节点”入队”.对每个子节点附加它的父节点的位置信息，便于用回溯的方式输出路径.Until队空.Voidsearch(float&best_cwjntn,floatc,FloatW[],intbest_in[]){struct{intr;intm;}node;Nodest

3、ack[l00];inttop二1;Floatbest_cw=0;cw=0;Nodecurrent_node;Top++；stack[top].r—1;stack[top].m=0;//根入栈DO{current_node.r=stack[top].r;current_node.m=stack[top].m;//Try栈顶if(top==n)//得到了完整的解向量(路径){讦(cw>best_cw)〃保存当前的最优解{best_cw=cw;〃最优载重For(intj=0;j

4、-=current_node.r*w[top-l];//回溯，解得还原Top-;//出栈操作，其不再是解的分量break;If（current_node.m==2）〃（死节点）两个子结点测试完了！{Cw-=current_node.r*w[top-1];〃回溯，解得还原！Top--;〃出栈操作，其不再是解的分量break;}If（current_node.m==0&&cw+W[top]

5、即对子节点进行求解，也称展开它•）stack[top-l].m=l;//计录解的变化cw+=w[top-l];〃计录解的当前状态}Elseif（current_node.m==1）//（活节点）两个子结点中测试了第一个，还有一个子结点待测试可行{top++；stack[top].r=0;（其分枝值为0,表示物品不装入）stack[top].m=0;（其子结点还未测试）〃该子节点”入栈”.（即对子节点进行求解,也称展开它.）stack[top-l].m=2;〃计录解的变化（CW不变）}}while（top!=-l）;）题目：对迷宫问题进行改进：1•修改函数mgpath使得可以找出所有路

6、径并最终找出最短路径；2.改成用递归形式来实现（用回溯法）。♦算法:一、算法设计思想：对用堆栈组织数据的深度优先解决迷宫问题进行修改，找出所有路径和最优路径：1.修改找到第一条路径后，要继续寻找新路径2.回溯，让top-0-以及mg[xe][ye]二0,并结束找到路径的该次循环(continue)3.返回值为路径数4.为找出最佳路径，只需比较每条路径的长度(top),找出最小值5.用文件保存路径源代码及相应注释:ftinclude〃stdafx・h〃ftdefineM8^defineN8#defineMaxSize100intmg[M+2][N+2]={1,1,1,1,1,1,1,1

7、,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};intmgpath(intxi,intyi,int