算法分析复习总结

《算法分析复习总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)else{a[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示要该物品search(m+1);//递归搜索：继续确定下一个物品}}用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i<=n;i++){swap(m,i)

2、;//交换a[m]和a[i]if(canplace(m))//如果m处可放置search(m+1);//搜索下一层swap(m,i);//交换a[m]和a[i](换回来)}}分支限界法的一般模式voidsearch(){open表初始化为空;起点加入到open表;while(open表非空){取open表中的一个结点u;从open表中删除u;for(对扩展结点u得到的每个新结点vi){if(vi是目标结点)输出结果并返回;If(notused(vi))vi进入open表;}}}递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复

3、计算多次。这种性质称为子问题的重叠性质。