资源预览内容
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
亲，该文档总共8页全部预览完了，如果喜欢就下载吧！
资源描述
算法复杂度回溯法 排列 ：n皇后，旅行商 n！子集 背包 2，迷宫 2，m着色 m贪心算法 Kruskal 宗教问题,活动安排 nlogn动态规划 矩阵连乘 n最长公共子序列 mnprim 最小生成树 n分治法 二路并归 nlogn矩阵连乘当i=j时，Ai:j=Ai，因此，mii=0，i=1,2,n 当ij时，若Ai:j的最优次序在Ak和Ak+1之间断开，i=kj,则：mij=mik+mk+1j+pi-1pkpj。由于在计算是并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。因此，k是这j-i个位置使计算量达到最小的那个位置。 综上，有递推关系如下： 总计算次数=Ai:k+Ak+1:j+Ak*Ak+1顺序不同乘的次序会有不同分治法递归法
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号