距离向量算法应用到交通分配上的研究

距离向量算法应用到交通分配上的研究

哈尔滨城市规划设计研究院综合交通所李凯

【摘要】道路网与因特网又有诸多的相似，IT行业有很多使用频繁而且技术上也已经很成熟的成功的网络寻址算法，用它们解决一些交通问题是可行的。本文向广大的交通研究人员介绍了一种应用在路由寻址上的算法--距离向量算法。本文通过数学证明和举例，分析了它的正确性、计算出它的时间复杂度，并指出它的优缺点和适用范围。本文以交通研究中常用的EMME/2软件为切入点，讨论了以“距离向量算法”为核心，建立交通预测软件或地理信息软件的可能性。

【关键词】最短路算法，距离向量算法

0 前言

所谓交通分配是指将各分区之间出行分布量分配到交通网络的各条边上去的工作过程。在传统的交通规划中交通分配曾是四阶段交通预测的最后一步，在现代交通规划中，它是方案设计的理论基础，交通模型成功与否的关键。

交通分配搀杂了太多的影响因素，这一过程过于模糊而难以抽象。在几十年的发展过程中，广大的研究人员和技术工作者在交通分配这一领域投入了辛勤的汗水。交通流理论、图论、最优化理论和系统论等诸多理论都曾经被引入到这一领域，这些理论虽然暂时还不能得到完美的结果，但是都闪烁着各自的亮点、体现着各自的优势。

本文选取了一个在IT行业使用很频繁的算法，向广大的交通研究人员做简单的介绍，并尝试解决交通分配的问题。文章中所涉及到的“距离向量算法”，无论是在理论上还是技术上都已经很成熟了，并在路由器、服务型工作站等设备上得到广泛应用。本文仿照该算法在解决网络数据传输问题上的思路，设计了用来解决交通分配问题的程序流程和部分源代码。本文旨在抛砖引玉，和大家一起研究将它移植到交通领域的可能性，这种尝试的意义和作用，还要在实际工作中逐步地检验。

1 交通分配研究工作的盲区

EMME/2软件是目前在交通分配工作中应用最广泛的软件之一。它最初是加拿大的Montreal大学的交通研究中心开发，以最短路算法为核心算法。后为INRO咨询公司继承，并成为该公司的支柱产品之一。该系统目前已在欧美亚非各大洲48个国家的500多个地区使用，在中国的用户有：山东师范大学、上海城市综合交通规划研究所、上海机械学院、同济大学和沈阳城市规划设计研究院等单位。

但是，许多研究单位在做交通分配工作时，过分地依赖于EMME/2软件，有意无意地跳过了最核心的算法设计过程。他们把EMME/2软件看成一个黑盒，并不关心盒子里的东西，只知道给定输入数据，按如下图（图1）的流程，就可以得到结果。

以某种算法或某几种算法为核心的EMME/2软件

图1 用EMME/2软件计算的流程

EMME/2系统其实也是以某种算法或某几种算法为核心的软件，在目前尚无一种有效的理论来完美地描述交通分配问题的情况下，在基础路网各不相同的诸多城市里千篇一律地使用一种软件来预测交通量的分配，似乎不是明智的做法。

当然，有经验的研究者早就发现：很多情况下，EMME/2系统的输出结果并不令人满意，他们也在这方面做出了积极的探索，试图解释错误的原因。不过，令人遗憾的是，我们的研究者把很多的精力都用在软件输入数据的修订上（大多是某参数或某因素所占权重的的确定）。比如以下的几篇论文：《EMME/2在城市道路交通容量预测中的反复尝试》，《需求网络平衡模式中EMME/2模式变量的确定》，《道路交通预测与实际流量差异原因分析》，《对EMME/2交通预测工作的几点看法》。

还有，上海城市综合交通规划研究所使用EMME/2系统做交通分配时，还创新性地加入了一个K系数。

但我们也许都没有想到：并不是我们输入的数据不够准确，也许真正需要修订的恰恰是那个黑盒——EMME/2的核心算法。

2 使用距离向量路由算法的可行性

我们在做交通分配时，常常抱怨车辆在路网中的行驶规律难以把握。最初，IT行业的网络工程师们也有类似的烦恼，他们也常常抱怨数据帧或数据分组并不按照他们所设想地那样在网络（以因特网为例）上有规律地寻址，而经常导致某个网络接入点上的信息拥塞。

经过几十年的研究，计算机网络已经有了一套十分成熟的体系结构，一般分为5层（也可分7层），由第三层的网络层来决定某个数据分组在因特网上路径的选择，并为网络层配备了IP

207

路由寻址协议（IP routing

protocals ）。在长期的实践过程

中，距离向量算法（DV ）被证

明是目前最成功的网络寻址

算法。

带报头的数据分组如同发

动机驱动的汽车，网络结点如

同道路交叉口，数据分组从主机1（Host h1）经

过路由寻址算法的指导到达主机2（Host h2），也

就如同汽车在路网上行驶并到达目的地。其实，因

特网上的结点何止百万，一个城市辖区里一两千个

交叉口根本无法与之相比；因特网上的信息量何止

百万兆，一个城市几十万台车又算得了什么。 3 距离向量路由算法的思想

距离向量（DV ）算法中每个结点都从和它相邻

的结点中接受相应的寻址信息，执行迭代计算，并将

计算结果分发回其相邻结点，并不是所有结点都执行

相同的计算步骤。

更有趣的是，当连续两次计算结果相同时，该算

法会自动停止计算；而当某结点相邻结点的寻址信息

变化时，该算法又会自动启动计算。 3.1 每个结点上的代价表

DV 算法主要的数据结构是每

个结点上保留的代价表。每个结点

的代价表中每一行对应网络中的一

个目的结点，每一列对应其直接相

邻结点。例如，要得到结点X 经过

直接相邻结点Z 到达目的Y 的路由，

结点X 的代价表项D x (Y ,Z)是X 和Z 之间直接链路的代

价c(X,Z)与邻接点Z 目前已知的从Z 到Y 的最小代价

路径的和。也就是：D x (Y ,Z)= c(X,Z)+ minw{Dz(Y ,w)}。 看一下图4的网络拓扑结构和给出的结点E 的代价表，它有助于我们的理解。我们先看第一行：

① 显然，从E 直接连接到A 的代价为1，即D E (A,A)=1。

② D E (A,D)，由E 出发，经过D 到达A 。在D 点时要查看D 点的代价表，会发现从D

到图2 路由寻址示意图 图3 数据分组寻址示意图

图4 一个代价表的例子

209

A 的代价最小为3，顾而D E (A,D)= c(E,D)+

minw{D D (A,w)}=2+3=5。在这里我们用到了D

点的代价表，这时D 的代价表像E 一样，也许

正在计算中。不过由于计算的迭代性，即使

minw{D D (A,w)}取了错误的值，但是经过数次迭

代计算，也可得到最终结果。关于迭代计算的原

理在下文叙述。

③ 同理，D E (A,B)=14，注意：代价不是15！

同理，我们得到E 点整个的代价表，并知道

了哪条路是代价最小的路，这样计算其他点的代价表时，

如果用到E 就可以提供准确的信息了。 3.2 迭代计算的过程

由图6的网络拓扑结构

和结点间的代价，我们不难

理解迭代计算的过程，它是

一个不断计算、逐步趋于稳

定的过程。同理我们就能得

到网络上所有结点的代价

表。

从这里我们能发现DV

算法的智能性：

① 自动学习：计

算刚启动时，一个结点

只知道与其相邻结点

之间的代价，但几次迭

代计算后，就能添满整

个代价表。

② 自动停止和启

动计算：当连续两次计

算结果相同时，算法认

为得到稳定的代价表，

并停止计算；当出现结

点间代价发生变化的

情况，算法自动启动计算，刷新代价表。

4 距离向量路由算法的伪代码

1 Initialization: 图5 E点的代价表 图6 X点的计算过程

图7 计算过程

2 for all adjacent nodes v:

3 D (*,v) = infty /* the * operator means "for all rows" */

4 D (v,v) = c(X,v)

5 for all destinations, y

6send min D (y,w) to each neighbor /* w over all X's neighbors */

7

8 loop

9 wait (until I see a link cost change to neighbor V

10 or until I receive update from neighbor V)

11

12 if (c(X,V) changes by d)

13 /* change cost to all dest's via neighbor v by d */

14 /* note: d could be positive or negative */

15 for all destinations y: D (y,V) = D (y,V) + d

16

17 else if (update received from V wrt destination Y)

18 /* shortest path from V to some Y has changed */

19 /* V has sent a new value for its min DV(Y,w) */

20 /* call this received new value is "newval" */

21 for the single destination y: D (Y,V) = c(X,V) + newval

22

23 if we have a new min D (Y,w)for any destination Y

24 send new value of min D (Y,w) to all neighbors

25

26 forever

由上文看出，第8步到第26步是一个循环过程，在该过程中，每个结点的计算都要从相邻结点那里得到最小代价值，计算得到的结果也要及时通知相邻结点。尽管最开始的几次循环，这些值可能都不正确，但是数次循环后，这些值就逐步稳定，直到连续两次计算结果一样，就认为得到了稳定的结果。

得到稳定结果后，如果代价发生变化，运算也可能再次自动地启动。下文将详细地描述DV 算法的这一特点。

5 链路代价变化

我们在因特网上冲浪时，会碰到某网站拥塞的情况，跟交叉口堵车很类似。但是过一会儿，该网站就不再拥塞了，这是因为路由算法根据链路代价的变化情况重新分配链路上的数据流量而起的作用。

使用DV算法的路由器并不像EMME/2那样一次性的完成计算，它最大的特点就是，时刻监视链路代价的变化情况，当链路代价变化后，算法自动启动，重新分配数据流量。

211

下面让我们详细地看一下，当链路代价变化情况下，DV 算法到底是如何计算的。

5.1 “好消息”传得快

图8描述了当从Y 到Z 的链路代价从4变为1时，距离向量算法的执行过程。我们在这里只关心Y 和Z 的到目的结点的代价表表项，其余表项不再赘述。

图8 链路代价变化：好消息传得快

DV 算法只需要两次迭代计算就进入稳定状态，“好消息”很快就在网络里传播开来。

5.2 “坏消息”传得慢

图9描述了当从Y 到Z 的链路代价从4变为60时，距离向量算法的执行过程。DV 算法需要44次迭代计算才能进入稳定状态，“坏消息”传播得的确很慢，这样很容易增加系统的消耗，降低软件的实用性。

图9 链路代价变化：坏消息传得慢

不过，成熟的IT 技术早就解决了这种问题，在距离向量算法中加入名为“毒性逆转”的处理技术，就可完美地解决坏消息传播过慢的缺点。关于“毒性逆转”的内容，在这里就不展开来讲述了。

6 算法的复杂性

随着存储空间的加大，算法的空间复杂性已经不再是主要矛盾了，我们只要考虑时间上的复杂性。

假设路网结点数为n ，车辆数为m ，EMME/2的核心算法--最短路算法的时间复杂性为O( n2m)。假设距离向量算法平均需要s 次计算才能得到稳定的结果，该算法的时间复杂性为O( nms)。

我们从上一章节的内容上可以看出，在没有加入“毒性逆转”的处理技术前，DV 算法最坏的情况才是计算n 次，所以s

因特网里，迭代次数也不会很多，更何况是道路网，特别是加入“毒性逆转”后，基本上寥寥

几次就可以稳定了。而一个城市的交叉口数量往往一两千，所以s远远小于n，既而nms远远小于n2m，DV算法在时间复杂性上的优势是很明显的。

7 结论

EMME/2的核心算法--最短路算法和上文介绍的网络第三层协议中的距离向量算法相比较各自的优缺点分析：

①两种算法都是以车辆为研究对象，重点研究车辆在路网中的寻路的规律；

②两种算法都要调查路网资料和调查居民的出行期望；

③ DV算法在时间复杂性上明显优于最短路算法；

④ DV算法是“自动学习”性的算法。链路代价变化时，EMME/2必须重新建模，重新计算；距离向量算法相对比较智能，适应性也强，即便是新增一个结点或删除一个结点，都可以自动开始计算。

由上面的比较结果可以看出，DV算法最大的特点就是实时计算，“自动更新代价表”可以保证该算法对路网的任何一点变化产生响应，“时间复杂性小”进一步保证了该算法的响应速度。

这些特征使得DV算法有着广阔的应用前景，配合交叉口监控设备，我们可以作到如下成果。比如：车流量的实时调配，红绿灯配时的实时变化，单行道的禁行时间的计算等等。

参考文献

[1] James.F.Kurose,Keith.W.Rose, Computer Networking A Top-Down Approach the Internet.高等教育出版社,2001年8月:49-59.

[2] 罗云启，罗毅．数字化地理信息系统．北京希望电子出版社，2003年11月：40-156

[3] 刘灿齐．现代交通规划学．人民交通出版社，2001年10月：58-109

[4] 文国玮．城市交通与道路系统规划．清华大学出版社，2001年1月：49-69

[5] 陆锡明，李敏，陈声洪．上海交通规划模型及其应用：32-88

向量法求异面直距离解法探求

向量法求异面直距离解法探求

————————————————————————————————作者：————————————————————————————————日期： 2

向量法求异面直线的距离解法探求 湖南 黄爱民 空间异面直线的距离问题是立体几何的重点，难点，同时也是历届高考试题的热点问题。如何很好地利用向量法求解这类问题又是一个值得探讨与研究的问题。下举例谈谈向量法求解这类问题的基本方法与策略。 一、 定义法： 例1、如图1，正方形ABCD 与ABEF 成600的二面角，且正大光明方形的边长为，M ，N 分别为BD ，EF 的中点，求异面直线BD 与EF 的距离。 解析：选取为,,,AB AF AD 基向量。显然AF AD ,的夹角为600，AD AB ,的夹角为900，AF AB ,的夹角为900， AD AF AB AD AF AB AD FE DF BD FN DF MD MN 2 121)()(212121-=+-+-=++=++=ΘEF MN EF MN AB AD AB AF AB AD AF FE MN BD MN BD MN a a AB AD AB AF AD AD AF AB AD AD AF BD MN ⊥⊥∴=?-?=?-=?⊥⊥∴=+--=?+?--?=-?-=?∴即又即）（,021)2 1(.,,0002160cos 2 121)21(2022从而MN 为异面直线BD 与EF 的公垂线。 ,2 3||434160cos 41)21(||2202222222a MN a a a a AD AD AF AF AD AF MN MN ==+-=+?-=-==Θ异面直线BD 与EF 的距离为a 2 3。 点评：本题利用向量数量积定义，很好地证明MN 为异面直线的公垂线。然后利用向量 模与数量积的关系，巧妙进行了模与向量的转化，解法自然，回味无穷。 二、射影法： 分别以这两异面直线上任意两点为起点和终点的向量为a ，与这两条异面直线都垂 直的法向量为n ，则两异面直线间的距离是a 在n 方向上的正射影向量的模设为d ，从而由 公式||| |n n a d ?=求解。 例2、如图2，四棱锥P-ABCD 的底面是正方形， ,PA ABCD ⊥底面33PA AB a ==，求异面直线AB 与PC 的距离。 解析：以A 为坐标原点，AB 为x 轴建立如图所示的直角坐标系，则B （a,0,0）,C(a,a,o),P(0,0,3a)，则)3,,(),0,0,(a a a PC a AB -==， 设PC AB ,的公垂线的方向向量为),,(z y x n =由 ? ??==??????=-+=?==?z y x az ay ax PC n ax AB n 30030，不妨令x=0,y=1,z=3则有)3,1,0(=n ，又)3,0,0(a AP =，∴AB 与PC 间的距离为：a a n AP n d 1010910 9||| |==?=。 点评：异面直线公垂线难于确定时，可用向量法求异面间的距离。这种方法的关键是利 用待定系数法确定公垂线的方向向量n 。

计算机网络原理 距离矢量路由

计算机网络原理距离矢量路由 距离矢量路由选择（Distance Vector Routing）算法是通过每个路由器维护一张表（即一个矢量）来实现的，该表中列出了到达每一个目标地的可知的最短路径及所经过的线路，这些信息通过相邻路由器间交换信息来更新完成。我们称这张表为路由表，表中按进入子网的节点索引，每个表项包含两个部分，到达目的地最优路径所使用的出线及一个估计的距离或时间，所使用的度量可能是站段数，时间延迟，沿着路径的排队报数或其他。 距离矢量路由选择算法有时候也称为分布式Bellman-Ford路由选择算法和Ford-Fulkerson算法，它们都是根据其开发者的名字来命名的(Bellman，1957；Ford and Fulkerson，1962)。它最初用于ARPANET路由选择算法，还用于Internet和早期版本的DECnet 和Novell的IPX中，其名字为RIP。AppleTalk t Cisco路由器使用了改进型的距离矢量协议。 在距离矢量路由选择算法中，每个路由器维护了一张子网中每一个以其他路由器为索引的路由选择表，并且每个路由器对应一个表项。该表项包含两部分：为了到达该目标路由器而首选使用的输出线路，以及到达该目标路由器的时间估计值或者距离估计值。所使用的度量可能是站点数，或者是以毫秒计算的延迟，或者是沿着该路径排队的分组数目，或者其他类似的值。 假设路由器知道它到每个相邻路由器的“距离”。如果所用的度量为站点，那么该距离就为一个站点。如果所用的度量为队列长度，那么路由器只需检查每一个队列即可。如果度量值为延迟，则路由器可以直接发送一个特殊的“响应”（ECHO）分组来测出延时，接收者只对它加上时间标记后就尽快送回。

向量法求空间距离教案

A B C D O S x y z 图2 A B C D α n a b 龙文学校——您值得信赖的专业化个性化辅导学校 龙文学校个性化辅导教案提纲 教师：_______ 学生：_______ 年级：______ 授课时间：_____年___月___日_____——_____段 一、授课目的与考点分析：向量法求空间距离 能用向量方法解决空间距离问题，了解向量方法在研究集合问题中的应用. 二、授课内容及过程： 1、点到平面的距离 方法：已知AB 为平面α的一条斜线段，n 为平面α的法向量， 则A 到平面α的距离d =AB n n ? . 2、两条异面直线距离： 方法：a 、b 为异面直线，a 、b 间的距离为：AB n d n ?= . 其中n 与a 、b 均垂直，A 、B 分别为两异面直线上的任意两点 题型1：异面直线间的距离 例1、如图2，正四棱锥S ABCD -的高2SO =，底边长2AB =。求异面直线BD 和SC 之间的距离？ 题型2：点面距离 如图，在长方体1111ABCD A BC D -，中，11,2AD AA AB ===，点E 在棱AD 上移动.（1）证明：11D E A D ⊥； （2）当E 为AB 的中点时，求点E 到面1ACD 的距离； （3）AE 等于何值时，二面角1D EC D --的大小为4 π. 解：以D 为坐标原点，直线1,,DA DC DD 分别为,,x y z 轴， 建立空间直角坐标系，设AE x =，则11(1,0,1),(0,0,1),(1,,0),(1,0,0),(0,2,0)A D E x A C （1）.,0)1,,1(),1,0,1 (,1111E D DA x E D DA ⊥=-=所以因为

距离向量算法更新路由表3

计算机网络实习报告 论文题目距离向量算法更新路由表 学生专业班级通信07级2班 学生姓名（学号） 指导教师 完成时间 2010年05月22日 实习（设计）地点信息楼139（112）机房 2010 年 05 月 22 日

距离向量算法更新路由表 一．实验目的 1．认识并掌握路由器结构组成及路由建立与更新的原理 2．理解、掌握和利用距离向量算法的应用。 3. 能够用距离向量算法建立一个路由表并根据相邻路由器发来的数据进行更新。 5．所实现的路由器模拟Internet上的IP路由器，它能确定网络的最短路由，并在其上传输分组 二．原理概述 距离向量路由算法被距离向量协议作为一个算法，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点是等同的。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输。 这个表中的列代表直接和它相连的“邻居”路由器相连，行代表在网络中的所有目的地。在距离向量路由算法中，相邻路由器之间周期性（一般为3分钟）地相互交换各自的路由表。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。它是一种动态路由选择算法。每个路由器都定期与其相邻的所有路由器交换路由表，据此更新它们自己的路由表。 所有路由器只与其相邻路由器交换信息，在发来为RIP报文情况下更新其路由表的具体步骤为： 1.对地址为X的相邻路由器发来的RIP报文，先修改报文中的所有项目，把“下跳”字段中地址均改为X，把所有“距离”字段的值加1.每一个项目都有三项数据，即：到目的网络N，距离是d，下一条路由器是X 2.对修改后的RIP报文中每个项目，进行以下步骤： 若原来路由表中没有目的网络N，则把该项目添加到路由表中。 否则若吓一跳地址是X，把收到的项目替还原路由表中的项目 否则若收到的项目中的距离d小于路由表中的距离，则进行更新。 否则什么也不做。 3．若三分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即把距离置为16.（本实验将其定义为6） 4.返回。 三．设计方案 路由表的建立和更新 假设建立七个路由器，其中三个A，B和C。路由器A的两个网络接口E0和S0 分别连接在 10.1.0.0和10.2.0.0网段上；路由器B的两个网络接口S0和S1 分别连接在 10.2.0.0和10.3.0.0网段上；路由器C的两个网络接口S0和E0 分别连接在 10.3.0.0和10.4.0.0网段上； 如上面各路由表的前两行所示，通过路由表的网络接口到与之直接相连的网 络的网络连接，其向量距离设置为0。这即是最初的路由表。

距离矢量路由算法原理

距离矢量路由算法原理实验 【实验目的】 1、要求实验者利用路由选择算法模拟软件提供的通信功能，模拟距离矢量路由选择算法的初始化、路由信息扩散过程和路由计算方法； 2、掌握距离矢量算法的路由信息扩散过程； 3、掌握距离矢量算法的路由计算方法。 【预备知识】 1、路由选择算法的特征、分类和最优化原则 2、路由表的内容、用途和用法 3、距离矢量算法的基本原理 【实验环境】 1、分组实验，每组4~10人。 2、拓扑： 虚线表示节点之间的逻辑关系，构成一个逻辑上的网状拓扑结构。 3、设备：小组中每人一台计算机。 4、实验软件：路由选择算法模拟软件（routing.exe ） 【实验原理】 路由选择算法模拟软件根据给定的拓扑结构，为实验者提供基本的本地路由信息，并能发送和接收实验者所组织的路由信息，帮助实验者完成路由选择算法的路由信息扩散过程、路由计算过程和路由测试过程。 1、模拟软件的功能（图2-1） ● 在局域网内根据小组名称和成员数量建立一个模拟网络拓扑结构，每个成员模拟拓扑中的一台路由器，路由器上的本地路由信息由实验软件提供。 ● 向实验者指定的发送对象发送实验者自行组织的发送内容。 ● 提示实验者有数据需要接收，并显示接收内容。 N 路由节点2 路由节点N-1 N = 4 ~ 10

●为实验者提供记录路由计算结果的窗口——路由表窗口。 ●为实验者提供分组逐站转发方法来验证路由选择的结果。 图2-1 路由选择算法模拟软件主界面 2、模拟软件的使用方法 1）建立小组 通过建立小组，每个小组成员可以获得本节点的编号和本地直连链路信息。 a）4～10人一组，在实验前自由组合形成小组。小组人数尽量多些，每人使用一台计算机。启动实验软件后点击“建立小组”按钮。（图2-2） 图2-2 选择建立小组 b）在建立小组的窗口内填入小组名称和成员数量。同一小组成员必须填写同样的小组名称和成员数量才能正确建立小组。（图2-3） 图2-3 建立小组窗口图2-4 小组建立过程

向量法求空间点到平面的距离教案

学习必备 欢迎下载 向量法求空间点到面距离（教案） 新课导入： 我们在路上行走时遇到障碍物一般会想到将障碍物挪开，那还有别的方法吗？ 对！绕过去。在生活中我们都知道转弯，那么在学习上我们不妨也让思维转个弯，绕过难点 用另一种方法解决。 我们知道要想求空间一点到一个面的距离，就必须要先找到这个距离，而找这个距离恰恰是 一个比较难解决的问题，我们今天就让思维转个弯，用向量法解决这个难题。 一、复习引入： 1、 空间中如何求点到面距离？ 方法1、直接做或找距离； 方法2、；等体积 方法3、空间向量。 2、向量数量积公式 a · b =a b cos θ（θ为a 与b 的夹角） 二、向量法求点到平面的距离 教材分析 重点: 点面距离的距离公式应用及解决问题的步骤 难点: 找到所需的点坐标跟面的法向量 教学目的 1. 能借助平面的法向量求点到面、线到面、面到面、异面直线间的距离。 2. 能将求线面距离、面面距离问题转化为求点到面的距离问题。 3. 加强坐标运算能力的培养，提高坐标运算的速度和准确性。

学习必备欢迎下载

学习必备 欢迎下载 若AB 是平面α的任一条斜线段，则在BOA Rt ? ABO COS ∠? ? 如果令平面的法向量为n ，考虑到法向量的方向，可以得到点B 到平面的距离为 BO 因此要求一个点到平面的距离，可以分为以下三步：（1）找出从该点出发的平面的任一 条斜线段对应的向量（2）求出该平面的一个法向量（3）求出法向量与斜线段对应的向量的 数量积的绝对值再除以法向量的模 思考、已知不共线的三点坐标,如何求经过这三点的平面的一个法向量? 例1、在空间直角坐标系中,已知(3,0,0),(0,4,0)A B ,(0,0,2)C ,试求平面ABC 的一个法向量. 解:设平面ABC 的一个法向量为(,,)n x y z = 则n AB n AC ⊥⊥，.∵(3,4,0)AB =-,(3,0,2)AC =- ∴(,,)(3,4,0)0(,,)(3,0,2)0x y z x y z ?-=???-=?即340320x y x z -+=??-+=? ∴3432y x z x ?=????=?? 取4x =,则(4,3,6)n = ∴(4,3,6)n =是平面ABC 的一个法向量. 例2、如图，已知正方形ABCD 的边长为4，E 、F 分别是AB 、AD 的中点，GC ⊥平面ABCD ，且GC ＝2，求点B 到平面EFG 的距离. 解：如图，建立空间直角坐标系C －xyz ． 由题设C(0,0,0)，A(4,4,0)，B(0,4,0)， D(4,0,0)，E(2,4,0)， F(4,2,0)，G(0,0,2)． (2,2,0),(2,4,2),B (2,0,0)EF EG E =-=--=设平面EFG 的一个法向量 为(,,)n x y z = 2202420 11(,,1)33 n EF n EG x y x y n ⊥⊥-=?∴?--+=?∴=，

用向量法求空间距离

用向量法求空间距离 湖南省冷水江市七中(417500) 李继龙 在高中立体几何中引入空间向量，为解决立体几何问题提供了一种新的解题方法，有时也能降低解题难度.下面通过例题介绍用向量法求空间距离的方法. 一、 求两点之间的距离 用向量求两点间的距离，可以先求出以这两点为始点和终点的向量，然后求出该向量的模，则模就是两点之间的距离. 例1 已知正方体ABCD-A 1B 1C 1D 1的棱长为1，点P 是AD 1的中点，Q 是BD 上一点， DQ=4 1 DB ，求P 、Q 两点间的距离. 解 如图1，以1DD DC DA 、、所在的直线分别为x 轴、y 轴和z 轴建立空间直角坐标系D-xyz ，则 0)4 141(Q )21021(，，、，，P ， 所以)21 －4141(－，，=. 46= ,即P 、Q 两点的距离为4 6. 二、 求点到直线之间的距离 已知如图2，P 为直线a 外一点，Q 为a 上任意一点，PO ⊥a 于点O ，所以点P 到直线a 的距离为|PO|=d . 则有>= < 故>

例2 在长方体OABC-O 1A 1B 1C 1中，OA=2，AB=3，AA 1=2.求点O 1到直线AC 的距离. 解 建立如图3所示的空间直角坐标系，连结AO 1，则A(2，0，0)，C(0，3，0)，O 1(0，0，2). 所以0)32－(AC 2)02－(AO 1，，，，，==. 故 d = 13 286 213168=- = 所以点O 1到直线AC 的距离为13 286 2. 三、 求点到平面的距离 如图4设A 是平面α外一点，AB 是平面α的一条斜线，交平面α于点B ，而是平面α的法向量，那么向量 在方向上的射影长就是点A 到平面α的距离d ，所以 d ==>

用向量法求空间距离

A B C D m n 1 图向量法求空间距离 向量融形、数于一体，具有几何形式和代数形式的“双重身份”，向量成为中学数学知识的一个交汇点，空间向量将空间元素的位置关系转化为数量关系，将过去的形式逻辑证明转化为数值计算，化繁难为简易，化复杂为简单，成为解决立体几何问题的重要工具。 1.异面直线n m 、的距离 分别在直线n m 、上取定向量,,b a 求与向量b a 、都垂直的向量，分别在 n m 、上各取一个定点B A 、，则异面直线n m 、的距离 d 等于在上的射影长，即| |n d = 证明：如图1，设CD 为公垂线段，取b a ==, | |||)(?=?∴?++=?∴++= | |||||n n AB d ?= =∴ 2平面外一点P 到平面α的距离 如图2，先求出平面α的法向量，在平面内任取一定 点A ，则点p 到平面α的距离d 等于在上的射影长，即| |n d = 因为空间中任何向量均可由不共面的三个基向量来线性表示，所以在解题时往往根据问题条件首先选择适当的基向量，把相关线段根据向量的加法、数乘运算法则与基向量联系起来。再通过向量的代数运算，达到计算或证明的目的。一般情况下，选择共点且不共面的三个已知向量作为基向量。 [例 1] 如图3，已知正三棱柱111C B A ABC -的侧棱长为2， 底面边长为1，M 是BC 的中点，当1AB MN ⊥时，求点1A 到平面AMN 的距离。 图2 A B C M N 1 A 1 B 1 C 图3

几何体中容易找到共点不共面且互相垂直的三个向量，于是有如下解法： 解：当1AB MN ⊥时，如图4 ， 、)0,0,0(A )81 ,1,0()0,43,43()2,21,23(1N M B 、、、)2,0,0(1A ，则 )2,0,0(),0,4 3,43( ),8 1 ,41,43(1==- =AA AM MN ， 设向量),,(z y x n =与平面AMN 垂直，则有 )0()1,1,3(8 ),81,83( 8183 0434********>-=-=∴?????? ?-==?=???????=+=++-??????⊥⊥z z z z z n z y z x y x z y x AM n MN n 取)1,1,3(0-=n 向量1AA 在0n 上的射影长即为1A 到平面AMN 的距离，设为d ，于是 5 5 21)1()3(|)1,1,3()2,0,0(||||,cos |||2 2201011011= +-+-?= =>

向量法求空间点到平面的距离教案

向量法求空间点到面距离（教案） 新课导入： 我们在路上行走时遇到障碍物一般会想到将障碍物挪开，那还有别的方法吗？ 对！绕过去。在生活中我们都知道转弯，那么在学习上我们不妨也让思维转个弯，绕过难点 用另一种方法解决。 我们知道要想求空间一点到一个面的距离，就必须要先找到这个距离，而找这个距离恰恰是 一个比较难解决的问题，我们今天就让思维转个弯，用向量法解决这个难题。 一、复习引入： 1、 空间中如何求点到面距离？ 方法1、直接做或找距离； 方法2、；等体积 方法3、空间向量。 2、向量数量积公式 a · b =a b cos θ（θ为a 与b 的夹角） 二、向量法求点到平面的距离 剖析：如图， BO 平面 ，垂足为O ，则点B 到平面 的距离是线段BO 的长度。 教材分析 重点: 点面距离的距离公式应用及解决问题的步骤 难点: 找到所需的点坐标跟面的法向量 教学目的 1. 能借助平面的法向量求点到面、线到面、面到面、异面直线间的距离。 2. 能将求线面距离、面面距离问题转化为求点到面的距离问题。 3. 加强坐标运算能力的培养，提高坐标运算的速度和准确性。

若AB 是平面 的任一条斜线段，则在BOA Rt ABO COS ? 如果令平面的法向量为n ，考虑到法向量的方向，可以得到点B 到平面的距离为 BO 因此要求一个点到平面的距离，可以分为以下三步：（1）找出从该点出发的平面的任一 条斜线段对应的向量（2）求出该平面的一个法向量（3）求出法向量与斜线段对应的向量的 数量积的绝对值再除以法向量的模 思考、已知不共线的三点坐标,如何求经过这三点的平面的一个法向量? 例1、在空间直角坐标系中,已知(3,0,0),(0,4,0)A B ,(0,0,2)C ,试求平面ABC 的一个法向量. 解:设平面ABC 的一个法向量为(,,)n x y z r 则n AB n AC r u u u r r u u u r ，.∵(3,4,0)AB u u u r ,(3,0,2)AC u u u r ∴(,,)(3,4,0)0(,,)(3,0,2)0x y z x y z 即340320x y x z ∴3432y x z x 取4x ,则(4,3,6)n r ∴(4,3,6)n r 是平面ABC 的一个法向量. 例2、如图，已知正方形ABCD 的边长为4，E 、F 分别是AB 、AD 的中点，GC ⊥平面ABCD ，且GC ＝2，求点B 到平面EFG 的距离. 解：如图，建立空间直角坐标系C －xyz ． 由题设C(0,0,0)，A(4,4,0)，B(0,4,0)， D(4,0,0)，E(2,4,0)， F(4,2,0)，G(0,0,2)． (2,2,0),(2,4,2),B (2,0,0)EF EG E u u u r u u u r u u u r 设平面EFG 的一个法向量 为(,,)n x y z r 2202420 11(,,1)33 n EF n EG x y x y n r u u u r r u u u r r ，

计算机网络距离矢量路由算法实验报告

计算机网络实验报告

距离矢量路由算法 一，实验内容： A D 设计一个算法，实现上面拓扑图的各个结点之间路由表的交换，要求显示出结点路由表的交换过程并显示每次交换结束后的各个结点保存的路由表的内容。最后显示交换了几次后各个结点路由表开始变得稳定。 二，算法设计： 首先创建一个类。它有两个成员变量。一个是二维数组型的x[i][j]用来存放从加点i到结点j的距离，一个是一位数组型的y[i]用来存放从源结点到目标结点i的路径上的第一个途经的结点。然后为每一个结点实例化一个对象用来存放此节点的路由表。初始化各个节点的路由表，如果两个节点之间有连线则将其之间的距离赋给x[i][j],y[j]=j.如果没有直接路径则设 x[i][j]=1000,y[j]=0.算法开始的时候各个结点交换路由表。比较如果有类似x[i][j]和x[j][k]的项则设置 x[i][k]=MIN(x[i][k],x[i][j]+x[j][k]),为了在结点A的邻居节点执行距离矢量路由更新时，它使用的是A的旧表，可以再设置两个二

维数组用来暂时存放各个节点的新路由表，待各个节点一次交换都完毕后在把暂存的新节点依次赋给各个节点的路由表。各个节点都执行此操作，为了确定供交换了几次可以设置一个标质量k.初始k=0，交换一次K就加一，最后k的值便是交换的次数。 三，遇到的问题及解决方案： 刚开始遇到这个题目是觉得无从下手，觉得这个图这么复杂函数循环又没有规律怎样让各个节点依次交换呢，又怎样判断什么时候各个节点的路由表变稳定呢？着一些列的问题使自己变得很烦躁。待到心情平静下来认真的一点一点推敲的时候发现只有七个节点，为每个节点设置一个交换函数也不麻烦而且这样思路便变得非常的清楚，至于怎样知道何时路由表稳定则我在每个结点函数中设置了一个标志量，在主函数中将其初始化为零，在下面的结点函数中都将其变成1，这样只有调用子函数这个标志量便会变成1，检测标质量是否为1来判断路由表是否变的稳定。 四，源代码 package wangluo; class Jiedian { int y[]=new int[8]; //存放路径上的下一个节点 int x[][]=new int[8][8]; //存放节点间的距离 } public class Luyou { public static void main(String[] args) { Jiedian a=new Jiedian();

向量法求空间点到平面的距离教案

向量法求空间点到面距离（教案） 教材分析 重点：点面距离的距离公式应用及解决问题的步骤 难点：找到所需的点坐标跟面的法向量 教学目的 1.能借助平面的法向量求点到面、线到面、面到面、异面直线间的距离。 2.能将求线面距离、面面距离问题转化为求点到面的距离问题。 3.加强坐标运算能力的培养，提高坐标运算的速度和准确性。 新课导入： 我们在路上行走时遇到障碍物一般会想到将障碍物挪开，那还有别的方法吗 对！绕过去。在生活中我们都知道转弯，那么在学习上我们不妨也让思维转个弯，绕过难点用另一种方法解决。 我们知道要想求空间一点到一个面的距离，就必须要先找到这个距离，而找这个距离恰恰是 一个比较难解决的问题，我们今天就让思维转个弯，用向量法解决这个难题。 一、复习引入： 1、空间中如何求点到面距离 方法1、直接做或找距离； 方法2、；等体积 方法3、空间向量。 2、向量数量积公式 a ? b = a b cos 0（0为a与b的夹角） 二、向量法求点到平面的距离

如果令平面的法向量为 n ，考虑到法向量的方向，可以得到点 B 到平面的距离为 _r BA?n BO=—:— n 因此要求一个点到平面的距离， 可以分为以下三步：(1)找出从该点出发的平面的任一 条斜线段对应的向量 (2)求出该平面的一个法向量 (3)求出法向量与斜线段对应的向量的 数量积的绝对值再除以法向量的模 思考、已知不共线的三点坐标，如何求经过这三点的平面的一个法向量 ? 例1、在空间直角坐标系中，已知A(3,0,0), B(0,4,0) , C(0,0,2),试求平面 ABC 的一个 法向量. 解：设平面ABC 的一个法向量为 r n (x, y, z) r uuu r uuur uuu unr 则 n AB , n AC . v AB (3,4,0), AC (3,0, 2) ? (x, y, z)( 3,4,0) 0即 3x 4y 0 3 y x (x, y, z)( 3,0,2) 0 3x 2z 0 . 4 取x 4,则n (4, 3,6) 3 z x 2 ??? n (4, 3,6)是平面 ABC 的一个法向量 例2、如图，已知正方形 ABCD 的边长为4, E 、F 分别是AB 、AD 的 中点，GC 丄平面 ABCD ，且GC = 2,求点B 到平面EFG 的距离. 解：如图，建立空间直角坐标系 C-xyz. 由题设 C(0,0,0)，A(4,4,0)，B(0,4,0)， D(4,0,0)，E(2,4,0)， F(4,2,0)，G(0,0,2). uuir uuur EF (2, 2,0), EG ( 2, 4,2), uuu BE (2,0,0) 设平面EFG 的一个法向量 若AB 是平面 的任一条斜线段，则在 Rt BOA 中，BO = BA?COS ABO BA?BO B A B O BO 剖析：如图，BO 平面 ，垂足为0，则点B 到平面 的距离是线段 BO 的长度。 =网? BA? BO

距离矢量协议和链路状态协议的区别(参考模板)

距离矢量协议和链路状态协议的区别 一．什么是距离向量路由协议以及什么是链接状态路由协议？ （1.）这类协议使用贝尔曼-福特算法（Bellman-Ford）计算路径。在距离-矢量路由协议中，每个路由器并不了解整个网络的拓扑信息。它们只是向其它路由器通告自己的距离、也从其它路由器那里收到类似的通告。（如果在90秒内没有收到相邻站点发送的路由选择表更新，它才认为相邻站点不可达。每隔30秒，距离向量路由协议就要向相邻站点发送整个路由选择表，使相邻站点的路由选择表得到更新。这样，它就能从别的站点（直接相连的或其他方式连接的）收集一个网络的列表，以便进行路由选择。距离向量路由协议使用跳数作为度量值，来计算到达目的地要经过的路由器数。） 每个路由器都通过这种路由通告来传播它的路由表。在之后的通告周期中，各路由器仅通告其路由表的变更。该过程持续至所有路由器的路由表都收敛至一稳定状态为止。 这类协议具有收敛缓慢的缺点，然而，它们通常容易处理且非常适合小型网络。距离-矢量路由协议的一些例子包括：路由信息协议（RIP）内部网关路由协议（IGRP） （2.）链接状态路由协议更适合大型网络，但由于它的复杂性，使得路由器需要更多的C P U资源。 在链路状态路由协议中，每个节点都知晓整个网络的拓扑信息。各节点使用自己了解的网络拓扑情况来各自独立地对网络中每个可能的目的地址计算出其最佳的转发地址（下一跳）。所有最佳转发地址汇集到一起构成该节点的完整路由表。 与距离-矢量路由协议使用的那种每个节点与其相邻节点分享自己的路由表的工作方式不同，链路状态路由协议的工作方式是节点间仅传播用于构造网络连通图所需的信息。最初创建这类协议就是为了解决距离-矢量路由协议收敛缓慢的缺点，然而，为此链路状态路由协议会消耗大量的内存与处理器能力。 （它能够在更短的时间内发现已经断了的链路或新连接的路由器，使得协议的会聚时间比距离向量路由协议更短。通常，在1 0秒钟之内没有收到邻站的H E L LO报文，它就认为邻站已不可达。一个链接状态路由器向它的邻站发送更新报文，通知它所知道的所有链路。它确定最优路径的度量值是一个数值代价，这个代价的值一般由链路的带宽决定。具有最小代价的链路被认为是最优的。在最短路径优先算法中，最大可能代价的值几乎可以是无限的。） 如果网络没有发生任何变化，路由器只要周期性地将没有更新的路由选择表进行刷新就可以了（周期的长短可以从3 0分钟到2个小时）。 链路状态路由协议的例子有：开放式最短路径优先协议（OSPF），中间系统到中间系统路由交换协议（IS-IS） 二．具体理解链路状态和距离矢量路由协议 距离矢量（DV）是“传说的路由”，A发路由信息给B，B加上自己的度量值又发给C，路由表里的条目是听来的，虽说“兼听则明，偏信则暗”，但是选出最优路径的同时会引发环路问题，当然，DV协议也使用水平分割，毒性逆转，触发更新等特性来避免，无奈的是，

向量法求空间点到平面的距离教案

向量法求空间点到面距离（教案） 新课导入： 我们在路上行走时遇到障碍物一般会想到将障碍物挪开，那还有别的方法吗 对！绕过去。在生活中我们都知道转弯，那么在学习上我们不妨也让思维转个弯，绕过难点 用另一种方法解决。 我们知道要想求空间一点到一个面的距离，就必须要先找到这个距离，而找这个距离恰恰是 一个比较难解决的问题，我们今天就让思维转个弯，用向量法解决这个难题。 一、复习引入： 1、 空间中如何求点到面距离 方法1、直接做或找距离； 方法2、；等体积 方法3、空间向量。 2、向量数量积公式 a · b =a b cos θ（θ为a 与b 的夹角） 二、向量法求点到平面的距离 剖析：如图，⊥BO 平面α，垂足为O ，则点B 到平面α的距离是线段BO 的长度。 教材分析 重点: 点面距离的距离公式应用及解决问题的步骤 难点: 找到所需的点坐标跟面的法向量 教学目的 1. 能借助平面的法向量求点到面、线到面、面到面、异面直线间的距离。 2. 能将求线面距离、面面距离问题转化为求点到面的距离问题。 3. 加强坐标运算能力的培养，提高坐标运算的速度和准确性。

若AB 是平面α的任一条斜线段，则在BOA Rt ? ABO COS ∠? 如果令平面的法向量为n ，考虑到法向量的方向，可以得到点B 到平面的距离为 BO 因此要求一个点到平面的距离，可以分为以下三步：（1）找出从该点出发的平面的任一 条斜线段对应的向量（2）求出该平面的一个法向量（3）求出法向量与斜线段对应的向量的 数量积的绝对值再除以法向量的模 思考、已知不共线的三点坐标,如何求经过这三点的平面的一个法向量? 例1、在空间直角坐标系中,已知(3,0,0),(0,4,0)A B ,(0,0,2)C ,试求平面ABC 的一个法向量. 解:设平面ABC 的一个法向量为(,,)n x y z = 则n AB n AC ⊥⊥，.∵(3,4,0)AB =-,(3,0,2)AC =- ∴(,,)(3,4,0)0(,,)(3,0,2)0x y z x y z ?-=???-=?即340320x y x z -+=??-+=? ∴3432y x z x ?=????=?? 取4x =,则(4,3,6)n = ∴(4,3,6)n =是平面ABC 的一个法向量. 例2、如图，已知正方形ABCD 的边长为4，E 、F 分别是AB 、AD 的中点，GC ⊥平面ABCD ，且GC ＝2，求点B 到平面EFG 的距离. 解：如图，建立空间直角坐标系C －xyz ． 由题设C(0,0,0)，A(4,4,0)，B(0,4,0)， D(4,0,0)，E(2,4,0)， F(4,2,0)，G(0,0,2)． (2,2,0),(2,4,2),B (2,0,0)EF EG E =-=--=设平面EFG 的一个法向量 为(,,)n x y z = 220242011(,,1)33 n EF n EG x y x y n ⊥⊥-=?∴?--+=?∴=，

向量的相似度计算常用方法9个

向量的相似度计算常用方法 相似度的计算简介 关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用户-物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。下面我们详细介绍几种常用的相似度计算方法。 共8种。每人选择一个。第9题为选做。 编写程序实现（这是第一个小练习，希望大家自己动手，java实现）。计算两个向量的相似性： 向量1（0.15, 0.45, 0.l68, 0.563, 0.2543, 0.3465, 0.6598, 0.5402, 0.002） 向量2（0.81, 0.34, 0.l66, 0.356, 0.283, 0.655, 0.4398, 0.4302, 0.05402） 1、皮尔逊相关系数（Pearson Correlation Coefficient） 皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在[-1，+1] 之间。 s x , s y 是 x 和 y 的样品标准偏差。 类名：PearsonCorrelationSimilarity 原理：用来反映两个变量线性相关程度的统计量 范围：[-1,1]，绝对值越大，说明相关性越强，负相关对于推荐的意义小。 说明：1、不考虑重叠的数量；2、如果只有一项重叠，无法计算相似性（计算过程被除数有n-1）；3、如果重叠的值都相等，也无法计算相似性（标准差为0，做除数）。

该相似度并不是最好的选择，也不是最坏的选择，只是因为其容易理解，在早期研究中经常被提起。使用Pearson线性相关系数必须假设数据是成对地从正态分布中取得的，并且数据至少在逻辑范畴内必须是等间距的数据。Mahout中，为皮尔森相关计算提供了一个扩展，通过增加一个枚举类型（Weighting）的参数来使得重叠数也成为计算相似度的影响因子。 2、欧几里德距离（Euclid ean Distance） 最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是： 可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。 类名：EuclideanDistanceSimilarity 原理：利用欧式距离d定义的相似度s，s=1 / (1+d)。 范围：[0,1]，值越大，说明d越小，也就是距离越近，则相似度越大。 说明：同皮尔森相似度一样，该相似度也没有考虑重叠数对结果的影响，同样地，Mahout通过增加一个枚举类型（Weighting）的参数来使得重叠数也成为计算相似度的影响因子。 3、Cosine 相似度（Cosine Similarity） Cosine 相似度被广泛应用于计算文档数据的相似度： 类名： UncenteredCosineSimilarity 原理：多维空间两点与所设定的点形成夹角的余弦值。 范围：[-1,1]，值越大，说明夹角越大，两点相距就越远，相似度就越小。 说明：在数学表达中，如果对两个项的属性进行了数据中心化，计算出来的余弦相似度和皮尔森相似度是一样的，在mahout中，实现了数据中心化的过程，所以皮尔森相似度值也是数据中心化后的余弦相似度。另外在新版本

距离向量算法模拟

计算机网络基础课程设计报告 学号：080004202 姓名： 班级：计科80802 题目：距离向量算法 一、问题描述

1、对地址为X的相邻的路由器发来的RIP报文，先修改此报文中的所有项目；把 “下一跳”字段中地址都改为X，并把所有距离都加1。 2、对修改后的报文的每一个项目，进行以下步骤：若原路由器没有该目的网络， 就直接加在路由表中；不然，再看下一跳路由器地址，若是X，则用收到的项 目替换原来的；若下一跳地址不同，，收到的项目的距离小于原来的距离，则替 换，否则什么都不用做。 3、若3分钟没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的 路由器，即把距离设为16 4、返回 二、设计方案 三、课程设计程序源代码

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 四、测试数据与结果分析 84 85

86 87 例如：原路由器R6路由表信息 88 89 90 91 不同，比较距离，R4的距离更小，所以更新。最后得到 92 93 五、课程设计心得与体会 94 95 在这次课程设计中， 96 得充分理解题意， 97 明白怎么解题之后，然后才将解题过程一步步列出来 98 再用算法写出来 99 这次的设计我做了三次，第一次选题、理解题意，对题有个印象；第二次列出解题过程，100 在纸上写算法，再在VC上运行，并把自己能改的改了；第三次请教同学，最终完成算101 法的实现。现在回想，发现其实算法的实现并不是很难，最重要的是写文档。大一第二102 学期，C++老师王波说过：对于计算机专业的学生，刚进公司只是编代码的，工资低；103 再做个几年，如果能力好，才能去做个写文档，工资也高了很多。我的方向是编程，所104 以为了以后能找到更好的工作，现在得好好努力。

距离向量路由算法实验报告

信息安全_专业 1002_班 2012年12月20日 姓名吴文珊学号_0909102525 一．实验题目 模拟距离向量路由算法的路由表交换过程，演示每轮交换后路由表的变化，动态生成网络拓扑图，从初始路由表开始，进行交换路由表，演示每轮交换后的路由表的变化。观察和讨论多少轮交换后路由表稳定。 二．需求分析 本程序用C编写，完成距离向量路由算法的模拟。 (1)输入的形式与输出值的范围：输入时要求输入节点个数、初始网络拓扑图中边的条数（即：邻居节点的对数），节点名称、每条边的弧头、弧尾节点、边权值。名字定义为字符串形式，节点个数、边条数、边权值为整形变量； (2)输出的形式：输入信息后，程序输出每轮交换之后新的的路由表 (3)程序所能达到的功能：完成节点信息的输入、随机选取节点交换向量，并更新路由表，显示经过多少轮交换路由表稳定，并停止交换。 (4)测试数据： 节点个数：4 边条数：4 节点名称：a b c d

弧头弧尾权值 a b 3 b d 6 c a 2 d a 6 最终距离向量矩阵如下： a b c d a 0 3 2 6 b 3 0 5 6 c 2 5 0 8 d 6 6 8 0 三．概要设计 (1)为了实现上述功能，须定义结构体的抽象数据类型 (2)本程序包含了个函数： void visit(VertexType ver)//访问顶点的函数 void input(VertexType &ver) //输入顶点信息的函数 int LocateVex(MGraph G,VertexType u)//查找顶点u,并返回void CreateDN(MGraph &G)//构造有向网G GetVex(MGraph G，int v)//得到图中顶点V void Display(MGraph G)//显示路由表 void ShortestPath_Floyd()文档由风行播放器https://www.wendangku.net/doc/737266007.html,/ 暴风影音2014：https://www.wendangku.net/doc/737266007.html,/ 整理 各函数间关系如下： CreateDN() LocateVex() visit() Main() Display() GetVex()