算法设计与分析.pptx

《算法设计与分析.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.1定义9.4定义的流和，满足流的三个性质吗？如果满足，请证明，如果不满足，哪一个性质最有可能被违背。9.3在图9.2(a)中，通过割的流是多少？该割的容量是多少？9.4证明引理9.2。引理9.2给定一个网络G=(V,E)，令为G的流。令为G中关于流f的剩余网络，令p为中从s到t的一条增广路径。定义函数如下则是的流，且满足容量约束性质<=反对称性质==流守恒性质且p为中从s到t的一条增广路径所以有9.6给定一个网络G=(V,E)，证明G的最大流总可以被至多由条增广路径所组成的序列找到。（提示：找出最大流后再确定路径。）最大流：（引理9.2证明了是的流

2、）在剩余网络构造的层次图中寻找增广路径，每次有一条边在层次图中消失，因此层次图中最多可能有条增广路径。9.19在东方，男女相爱讲究的是缘分。只要月下老人做媒，就能千里姻缘一线牵，无论他们身处何地。而在西方，只能借助爱神丘比特之箭，射中的两个男女才能相爱。假定丘比特之箭的射程为d，给定n对男女，已知每个男女的位置(x,y)，以及男女之间的缘分值，请设计一个算法，使得每对男女射中一次，且每一对被射中的男女之间的缘分值的和最大。注意箭的轨迹只能是一条直线。每一条连接左边顶点和右边顶点的边都有一个对应的权值代表他们的缘分值（用二维数组w[i][j]来表示），如

3、果某一对男女因为射程或中间有人的限制而不可能成为一对，那么相当于把他们之间的边的权值设为负无穷。最大权完全匹配Kuhn－Munkras(KM)算法如果所有满足A[i]+B[j]=w[i][j](A[i]和B[i]分别为左边节点i和右边节点j的顶标值)的边组成的导出子图中存在一个完全匹配，那么这个完全匹配肯定就是原图中的最大权匹配。算法步骤：(1)初始化可行顶标的值初始满足每条边A[i]+B[j]>=w[i,j](2)用匈牙利算法寻找完全匹配(3)若未找到完全匹配则修改可行顶标的值根据最后一次不成功的寻找交错路径，取所有i被访问到而j没被访问到的边(i,

4、j)的A[i]+B[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d，右端点的顶标增加d。a）两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。b）两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。b）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。d）X端在交错树中，Y端不在交错树中的边(i,j)，它的A

5、[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。(4)重复(2)(3)直到找到相等子图的完全匹配为止12.1将装载问题改进的递归算法改写为迭代回溯算法。While(true){While(i<=n&&cw+w[i]<=w)//进入左子树{r=r-w[i]cw=cw+w[i]x[i]=1i++}If(i>n){//到达叶子节点for(j=1;j<=n;j++)bestx[j]=x[j]bestw=cw}else{//进入右子树r=r-w[i]x[i]=0i++}While(cw+r<=best

6、w){//剪枝回溯i--while(i>0&&!x[i]){//从右子树返回r=r+w[i]i--}If(i=0)Returnbestw//进入右子树x[i]=0cw=cw-w[i]i++}}12.10n个雇员被分配做n件工作，分配第i个人做第j件工作的代价为c[i,j]，其中c[i,j]>=0，1<=i,j<=n，设计一个回溯算法找出一种分配使得总代价最少。END