DP.ppt

Last Section
动态规划应用举例
资源分配问题
生产与存储问题
复合系统工作可靠性问题
排序问题
设备更新问题
可基于动态规划思想求解的问题与算法
计算二项式系数
最长公共子序列
L[i, j] = 0 若i=0或j=0
=L[i-1, j-1] + 1 若i>0, j>0 和ai= bj
=max{ L[i, j-1], L[i-1, j]} 若i>0, j>0 和ai≠ bj
矩阵链相乘
可基于动态规划思想求解的问题与算法
所有点对的最短路径问题
做n次迭代,使在第k次迭代后,Dk [i,j]含有从顶点i到顶点j,且不经过编号大于k的任何顶点的最短路径的长度。
dki,j=l[i, j] 若k = 0
=min{dk-1i,j, dk-1i,k+ dk-1k,j} 若1≤k≤n
0/1 背包问题
设V[i,j] 表示从前i项{u1,u2,…,ui}中取出来的装入体积为j的背包的物品的最大价值
V[i,j] = 0 若i=0或j=0
=V[i-1,j] 若j<si
=Max{V[i-1,j],V[i-1,j-si]+vi} 若j≥si
可基于动态规划思想求解的问题与算法
计算有向图的传递闭包
Warshall 算法:
rij(k)置为1意味着存在一条从第i个顶点到第j个顶点的路径,路径中每一个中间顶点的编号都不大于k
rij(k)= rij(k-1) or rik(k-1) and rkj(k-1)
最优二叉查找树:
C[i,j]是在这棵树中成功查找的最小的平均查找次数
考虑从键ai,…,aj (sorted)中选择一个根ak的所有可能的方法
贪心算法
主要思想(可行、局部最优、不可取消)
分数背包问题
最短路径问题
Dijkstra’s Algorithm
Prim’s
Kruskal’s
Huffman 算法与决策树
回溯
回溯法
任何难问题,均可通过穷尽搜索数量巨大但有限多个可能性而获得一个解。
大多数难问题都不存在用穷尽搜索之外的方法来解决问题的算法。
产生了开发系统化的搜索技术的需要,并且希望能够将搜索空间减少到尽可能的小。
组织搜索的一般技术之一是回溯法。这种算法设计技术可以被描述为有组织的穷尽搜索,它常常可以避免搜索所有的可能性。
回溯法的基本思想
针对所要做的选择构造一棵所谓的状态空间树,树的每一层节点代表了对解的每一个分量所做的选择。
用深度优先法搜索状态空间树。
在状态空间树中的任一节点,满足一定条件的情况下,搜索回溯。
3 着色问题
给出一个无向图G=(V,E),需要用三种颜色之一为V中的每个顶点着色,三种颜色分别为1,2 和3,使得没有两个邻接的顶点有同样的颜色。我们把这样的着色称为合法的;否则,如果两个邻接的顶点有同一种颜色就是非法的。
一种着色可以用n元组{c1,c2,…, cn}来表示,使ci∈{1,2,3}, 1≤i≤n。
例如,(1,2,2,3,1)表示一个有5个顶点的图的着色。