⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 ds7.5.2.htm

📁 这是清华大学所用的数据结构的电子版教材
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第一章&nbsp; 绪论</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>

<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">

<!--mstheme--><font face="宋体">
<p align="center"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#FFFF00" size="6">7.5.2  
关键路径</font></span></b></p>
<p ALIGN="JUSTIFY"><b><font size="5" color="#FFFF00"><font FACE="楷体_GB2312" LANG="ZH-CN">用边表示活动的网络</font>(AOE<font FACE="楷体_GB2312" LANG="ZH-CN">网络</font>)</font></b></p>
<p><font FACE="楷体_GB2312" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp; 
如果在无有向环的带权有向图中</b></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"><!--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><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN">用有向边表示一个工程中的各项活动</font>(Activity)</b></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--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 size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN">用边上的权值表示活动的持续时间</font>(Duration)</b></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--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 size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN">用顶点表示事件</font>(Event)</b></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN">&nbsp; 
则这样的有向图叫做用边表示活动的网络，简称</font>AOE 
(Activity On Edges)<font FACE="楷体_GB2312" LANG="ZH-CN">网络。</font></b></font></p>
<p><font size="5" color="#FFFFFF"><b>&nbsp; AOE<font FACE="楷体_GB2312" LANG="ZH-CN">网络在某些工程估算方面非常有用。例如，可以使人们了解：</font></b></font></p>
<blockquote>
  <p><font size="5" color="#FFFFFF"><b>(1) <font FACE="楷体_GB2312" LANG="ZH-CN">完成整个工程至少需要多少时间</font>(<font FACE="楷体_GB2312" LANG="ZH-CN">假设网络中没有环</font>)?</b></font></p>
  <p><font size="5" color="#FFFFFF"><b>(2) <font FACE="楷体_GB2312" LANG="ZH-CN">为缩短完成工程所需的时间</font>, 
  <font FACE="楷体_GB2312" LANG="ZH-CN">应当加快哪些活动</font>?</b></font></p>
</blockquote>
<font FACE="宋体" LANG="ZH-CN" SIZE="6" COLOR="#cc3300"></font>
<p><b><font size="5" color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN">&nbsp; 
在</font>AOE<font FACE="楷体_GB2312" LANG="ZH-CN">网络中</font>, <font FACE="楷体_GB2312" LANG="ZH-CN">有些活动顺序进行，有些活动并行进行。</font></font><font FACE="楷体_GB2312" LANG="ZH-CN" size="5" color="#FFFFFF">从源点(入度为0的顶点)到各个顶点，以至从源点到汇点（出度为0的顶点）的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。</font></b></p>
<p><b><font size="5" color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN">&nbsp; 
因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径</font>(Critical 
Path)<font FACE="楷体_GB2312" LANG="ZH-CN">。</font></font></b></p>
<b><font FACE="Arial Narrow" SIZE="6" COLOR="#0000ff"></font>
<p><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFFFF">&nbsp; 
要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径</font></p>
<p><img border="0" src="ds7.5.8.gif" width="1128" height="445"></p>
</b><b>
<p><font FACE="楷体_GB2312" LANG="ZH-CN" size="5" color="#FFFF00">定义几个与计算关键活动有关的量：</font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"><!--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="宋体">
      <p ALIGN="JUSTIFY"></font><font color="#FFFFFF" size="5"><font FACE="楷体_GB2312" LANG="ZH-CN">事件</font>V<sub>i</sub> 
      <font FACE="楷体_GB2312" LANG="ZH-CN">的最早可能开始时间</font>Ve[i]<font FACE="Times New Roman">:</font><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></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体"><font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"><!--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="宋体">
      <p ALIGN="JUSTIFY"></font><font color="#FFFFFF" size="5"><font FACE="楷体_GB2312" LANG="ZH-CN">事件</font>V<sub>i 
      </sub><font FACE="楷体_GB2312" LANG="ZH-CN">的最迟允许开始时间</font>Vl[i]<font FACE="Times New Roman">:</font><font FACE="楷体_GB2312" LANG="ZH-CN">是在保证汇点</font>V<sub>n-1 
      </sub><font FACE="楷体_GB2312" LANG="ZH-CN">在</font>Ve[n-1] <font FACE="楷体_GB2312" LANG="ZH-CN">时刻完成的前提下，事件</font>V<sub>i</sub> 
      <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="宋体">
    <p ALIGN="JUSTIFY"></font><font color="#FFFFFF" size="5"><font FACE="楷体_GB2312" LANG="ZH-CN">活动</font>a<sub>k</sub><font FACE="楷体_GB2312" LANG="ZH-CN">的最早可能开始时间</font>e[k]<font FACE="Times New Roman">:</font><font FACE="楷体_GB2312" LANG="ZH-CN">设活动</font>a<sub>k</sub><font FACE="楷体_GB2312" LANG="ZH-CN">在边</font>&lt;V<sub>i</sub>,
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -