📄 ds7.5.2.htm
字号:
V<sub>j</sub>><font FACE="楷体_GB2312" LANG="ZH-CN">上，则</font>e[k]<font FACE="楷体_GB2312" LANG="ZH-CN">是从源点</font>V<sub>0</sub><font FACE="楷体_GB2312" LANG="ZH-CN">到顶点</font>V<sub>i</sub>
<font FACE="楷体_GB2312" LANG="ZH-CN">的最长路径长度。因此</font>,
e[k] = Ve[i]<font FACE="楷体_GB2312" LANG="ZH-CN">。</font></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="aricebu1.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体"></font><font color="#FFFFFF" size="5"><font FACE="楷体_GB2312" LANG="ZH-CN">活动</font>a<sub>k
</sub><font FACE="楷体_GB2312" LANG="ZH-CN">的最迟允许开始时间</font>l[k]:</font><font color="#FFFFFF" size="5">l[k]<font FACE="楷体_GB2312" LANG="ZH-CN">是在不会引起时间延误的前提下，该活动允许的最迟开始时间。 </font></font><font color="#FFFFFF"><font face="楷体_GB2312" lang="ZH-CN" size="5">
</font><font SIZE="5">l[k] = Vl[j] - dur(<i, j>)</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">。
其中，</font><font SIZE="5">dur(<i, j>)</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">是完成</font><font SIZE="5">a<sub>k
</sub></font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">所需的时间。</font></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体"><!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="aricebu1.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">时间余量</font><font SIZE="5">
l[k] - e[k]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">表示活动</font><font SIZE="5">a<sub>k
</sub></font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">的最早可能开始时间和最迟允许开始时间的时间余量。</font><font SIZE="5">l[k]
== e[k]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">表示活动</font><font SIZE="5">a<sub>k
</sub></font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">是没有时间余量的关键活动。</font></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体"></b>
<p> <b><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">为找出关键活动</font><font SIZE="5">,
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">需要求各个活动的</font><font SIZE="5">
e[k] </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">与</font><font SIZE="5">
l[k]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">，以判别是否</font><font SIZE="5">
l[k] == e[k].</font></font></p>
<p><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
为求得</font><font SIZE="5">e[k]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">与</font><font SIZE="5">
l[k]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">，需要先求得从源点</font><font SIZE="5">V<sub>0</sub></font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">到各个顶点</font><font SIZE="5">V<sub>i
</sub></font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">的</font><font SIZE="5">
Ve[i] </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">和</font><font SIZE="5">
Vl[i]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">。</font></font></p>
<p><font color="#FFFF00"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">求</font><font SIZE="5">Ve[i]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">的递推公式</font></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font></b><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN"> 从</font>Ve[0]
= 0<font FACE="楷体_GB2312" LANG="ZH-CN">开始，向前递推</font></b></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><b><font size="5" color="#FFFFFF"> <V<sub>j</sub>,V<sub>i</sub>>
Î S2, i = 1, 2, ¼ , n-1</font></b><font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"></p>
<p></font><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN"> 其中</font>,
S2<font FACE="楷体_GB2312" LANG="ZH-CN">是所有指向顶点</font>V<sub>i</sub><font FACE="楷体_GB2312" LANG="ZH-CN">的有向边</font><V<sub>j</sub>,V<sub>i</sub>><font FACE="楷体_GB2312" LANG="ZH-CN">的集合。</font></b></font><font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"></p>
<p></font><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN"> 从</font>Vl[n-1]
= Ve[n-1]<font FACE="楷体_GB2312" LANG="ZH-CN">开始，反向递推</font></b></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><b><font size="5" color="#FFFFFF"> <V<sub>i</sub>,V<sub>j</sub>>
Î S1, i=n-2, n-3, ¼ , 0</font></b></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN"> 其中</font>,S1<font FACE="楷体_GB2312" LANG="ZH-CN">是所有从顶点</font>V<sub>i</sub><font FACE="楷体_GB2312" LANG="ZH-CN">发出的有向边</font><V<sub>i</sub>,V<sub>j</sub>><font FACE="楷体_GB2312" LANG="ZH-CN">的集合。</font></b></font><font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"></p>
</font>
<p><font FACE="楷体_GB2312" LANG="ZH-CN" size="5" color="#FFFFFF"><b>
这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。</b></font></p>
<font FACE="宋体" LANG="ZH-CN" SIZE="6" COLOR="#cc3300"></font>
<p><font color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
设活动</font><font SIZE="5">a<sub>k</sub>(k = 1, 2, …, e)</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">在带权有向边</font><font SIZE="5"><V<sub>i</sub>,V<sub>j</sub>>
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">上</font><font SIZE="5">,
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">它的持续时间用</font><font SIZE="5">dur(<V<sub>i</sub>,V<sub>j</sub>>)
</font></b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"><b>表示，则有</b></font></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><font color="#FFFFFF"><b><font SIZE="5"> e[k] = Ve[i]</font></b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"><b>；</b></font></font></p>
<p><font color="#FFFFFF"><b><font SIZE="5"> l[k] = Vl[j]</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">-</font><font SIZE="5">dur(<V<sub>i</sub>,V<sub>j</sub>>)</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">；</font><font SIZE="5">k
= 1, 2, …, e</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">。</font></b></font></p>
<p><font face="楷体_GB2312" lang="ZH-CN" size="5" color="#FFFFFF"><b>
这样就得到计算关键路径的算法。</b></font><font color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"> </font></b></font></p>
<b>
<p style="margin-bottom: 0"><img border="0" src="ds7.5.9.gif" width="1128" height="445"></p>
</b><p align="left" style="margin-top: 0"><img border="0" src="ds7.5.10.gif" width="1128" height="361"></p>
<p align="center"> </p>
<p align="center"><b><a href="ds7.5.htm"><font size="5" color="#FFFF00">返回</font></a></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -