,去掉边。(2):取圈,去掉边。Р(3):取圈,去掉边。(4):取圈,去掉边。Р在图中已无圈,此时,,而,因此所得的是最短树。结果如下图,其树的总长度为12。.------(6分)Р .------(3分)Р生长法Р根据生长法的基本原理,得以下计算表Р Р{2}Р6Р3Р8Р9Р{3}Р8Р9Р5Р3Р5Р{3}Р1Р5Р{1}Р3Р{3}Р据此也得到与破圈法相同的最短树。.------(6分)Р简答题(每小题10分,共20分)Р1:动态规划建模应完成如下工作:Р(1):确定阶段与阶段变量,阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的,阶段数等于多段决策过程中从开始到结束所需要作出决策的数目,阶段变量用k表示。Р(2):明确状态变量和状态可能集合。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。Р(3):确定决策变量和决策允许集合。Р(4):确定状态转移方程。Р(5):明确阶段效应和目标。Р最优化原理:“最优策略具有的基本性质是:无论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,下余的决策序列比构成最优策略。”Р最优化原理的含义就是,最优策略的任何一部分子策略,也是相应初始状态的最优策略。每个最优策略只能由最优子策略构成。Р2:狄克斯拉算法适用的问题是所有满足的网络,算法能求出到所有其他点的最短距离,特别的,经过有限次迭代(不超过n次)则可求出到的最短距离。Р海斯算法适应的网络可以有负权,可以是有向网络,也可以是无向网络。海斯算法得到的结果是网络中的点两两之间的最短距离,且海斯算法的效率很高,可以以较少的迭代次数完成,对于一个有n个点的网络,用海斯算法只需经过m次迭代就可以求出任意两点之间的最短距离,其中m为满足的最小整数。Р福德算法是计算到所有其他点的最短距离的一种方法,它适应于有负权,但无负回路的有向或无向网络,其迭代的效率比较高。
全文预览
