图论算法与模型构建要点.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * L0-b0=hi-hi-l0 当I=L0时，根据条件，Si-L0+1…Si中0的个数(L0-(hi-hi-L0))在a0～b0之间，即a0=L0-(hi-hi-L0)=b0 a0-L0=hi-L0-hi -b1=hi-l1-hi ? 当I=L1时，根据条件，Si-L1+1 … Si中1的个数(hi-hi-L1)在a1～b1之间，即a1=hi-hi-L1=b1。 a1=hi-hi-L1 一旦有了h序列，我们可以由左至右构造s串：如果hi-1=hi，则说明si=0；否则si=1(1=I=n)。由此看来，问题的关键是如何计算h序列。 仔细观察上述推论条件，发现有以下特点： （1） 除h0=0外，其余的条件都是由“=”连接的不等式 ?? （2）? 每个不等式都是含两个h未知数、一个常数的一次不等式； 可见，所有不等式都整理成了k=hi-hj 它给我们启示，上述不等式类似于连接两点的一条有向边。因此，我们联想到信息学解题中常用的图论知识。 模型2 构造有向图G 我们构造有向图G，如图： 其中vi代表s串中的第I位。若k=vi-vj,则vi向vj引出一条权为k的有向边vi,vj,表明si…sj中至少需增加k个1（k为正值）或减少k个1(k为负值)。由此得出构造有向图G的方法： 0=hi-hi-1 -1=hi-1-hi a0-L0=hi-L0-hi L0-b0=hi-hi-l0 a1=hi-hi-L1 -b1=hi-l1-hi 计算图G的最长路径： 我们已构造了一个有n+1个顶点的有向图G。 （1） 图G中无环 令D[I]表示从顶点0到顶点I的最长路径长度。 对于图中 每条从点I指向点J的权为C[I,J]的边，有性质 D[I]+C[I,J]=D[J]（注意：这与上述不等式的形式相似） 这样，令hi=D[I]，h完全符合所有限制条件，即为原不等式组的一组解 。 （2） G中含有环 可用反证法证明无解。 从s1出发，顺序确定每位二进制数。当hi=hi-1时，说明s1…si-1中1的个数与s1…si中1的个数相同，即si为0；否则si为1。 最短路 例题4：求第一、第二、第三最短路问题 城市交通 见文档 城市交通分析 在求两点之间的最短路径时，有一种比较优秀的方法：“Floyd-Warshall”算法，其算法的中心思想是这样的： 求A至B的满足中间结点不超过K的最短路径。而后，随着K逐渐增加至N而求出A至B的最短路径。 则其算法的结构如下： For K=1 To N {K从1增至N} For A=1 To N Do For B=1 To N Do {求每一对结点的中间结点不超过K的最短路径} IF (Map[A,K]0) And (Map [K,B]0) Then {如果A与K，K与B均可达} IF (Map[A,B]=0) Or (Map[A,B]Map[A,K]+Map[K,B]) Then {如果A、B不可达，或者A、B之间的路径不如A-K-B这条路径短，则改变Map[A,B]的值} Map[A,B]:=Map[A,K]+Map[K,B]; 注：Map[A,B]为从A到B的最短路的距离，如果A,B不可达，则Map[A,B]=0。 在求改进M条边使最短路下降最快中，我们同样可以发现： 1：将道路A-B改造M条边可以分为如下两个问题（如果K是最短路上的一点） 一：求A-K改造T条边； 二：求K-B改造M-T条边。 T可以取从0至M的任意值。问题A-B改造M条边的最优解取决与这两个子问题的最优解。 2：在求M条边的过程中，始终只与改造T与M-T条边的问题发生联系。 ? 以上两个特点即为“动态规划”的“无后效性”与“最优子问题”两个性质。所以，这个“城市交通”问题的