《关于绍兴道路数学抽象及最短路径的一般解法研究.doc》由会员分享，可在线阅读，更多相关《关于绍兴道路数学抽象及最短路径的一般解法研究.doc（10页珍藏版）》请在三一文库上搜索。
1、关于绍兴道路数学抽象及最短路径的一般解法研究研究组成员:李一飞 胡晟杰 金继辉 潘皖滨指导教师： 李 瑾研究方式： 实地调研 小组讨论 得出结论关键问题： 用数学语言抽象城市道路如何算出最短路径成果形式： 论文正文：课题缘由： 城市在不断扩大的过程中，道路交通网也越来越复杂，人们比起公交车，也更倾向于驾车出行，于是制订路线便成了头等问题。我们小组想用数学思想来求地图上任意两点间的最短路径。小组讨论（概括）：金继辉：关于抽象，我有想法，就像画地图那样，只不过图不需要画的太像，用线来表示路，然后标注每条路的长度。胡晟杰：每条路不太好，不一定非要按着地图上的方式来，我们可以把道路划分成N个段落，然后
2、再每个段落上标注其长度。李一飞：抽象程度不够高，我们的最终目的是用程序框图来解决这些问题，我们没有办法让程序来理解这图，至少目前是不可能的，而且输入数据的时候也很麻烦，图的表达方式也难统一。金继辉：用矩阵。李一飞： ！金继辉：这个不是我们学过的东西么，行和列分别表示节点，其对应的值表示两节点间的距离。李一飞：恩。抽象就到这里吧，然后是最短路径？潘皖滨：可以随机的试验道路，找到最短的距离。金继辉：如果有这样子的图，那就用从a1出发，a-b1-c1-d1 算出距离后再试验 a1-b1-c2-d1 就像这样试完整个图。胡胜杰：这不是很简单么，一会会就好了。李一飞：金继辉同学你应该画一个有几百个节点的
3、图随机试验不太好，不过可以在短时间内找到一个可以接受的解，金继辉的方案适用于小数据量的图，比方说5个节点的，但是也只适用于图形化的数据，可我们现在只有一个表格，如果用表格如何实现呢?金继辉：那就先把表格转换成图？李一飞：潘皖滨：关于最短路径，可以先找到一个比较小的子路径，然后把他们圈出来，之后想办法联系起来。李一飞：哦？金继辉：可没有那个图啊。李一飞：如果简单的把各个节点连接起来，可以得到一个抽象程度比较低的图。但是这样子的图，我觉得和表格没有区别。金继辉：你跑题了我们要的是这样子的图。潘皖滨：这样子我可以画满一个足球场如果你想画满两个也可以李一飞：里面有重复的，如果能剔除掉就可以得到想要的图
4、了。胡晟杰：排列。李一飞：恩，第一部分解决了呼还有是组合李一飞：然后是最短路径了。刚才有提到一点，随机算法的pass掉，但是潘皖滨说的最小值是有可行性的，可是如何区分大还是小？潘皖滨：取平均数，然后大于平均数的算大，小于平均数的算小金继辉：如果只有5个节点，那么便有8种具有可行性的路径。李一飞： 是排列，5个节点就是3个元素的排列即ABC,AC,BC,AC,A,B,C,和空集。金继辉：我是想说，我觉得在节点数很多的情况下，用试遍所有的情况来算最短路径，也不会用很多时间。李一飞：有6个节点时，去掉首末节点，其间还有4个节点，用0表示不经过该节点，用1表示经过该节点，则可能性有0000 0001
5、0010 1111 便是24=16种，当有n个节点时，O(n)=2(n-2),这是幂函数胡晟杰：我们要挑战极限的情况，当n=34时就有43亿种排列，肯定是行不通的，潘皖滨说的最小值，也许有发展的余地。或许每次都取最小值就能够达到最优解。潘皖滨：（感激）胡晟杰：从路径的半中央找显然不太好。潘皖滨：胡晟杰：从结尾？总结：道路抽象的思想：用矩阵中的元素表达城市道路节点间的距离，其中行和列分别代表节点，对应的值代表节点间的距离。用图示法来表达即用点表示道路的交点，用线表示道路，并在线上标注距离，以便于进行分析。（节点可重复出现，同一节点之间的距离为0）最短路径算法的思想：将起点到终点之间的节点阶段化，
6、再在每个阶段中寻求最优解以达到整体的最优化。程序框图及说明：求最短路径:如上表格（矩阵），是一个已经抽象出来的道路图，其中总共有5个节点(A-E)，同时每两个节点间都有道路相连，其中AB单元格对应的元素所代表的意义为：从A节点到B节点的距离为7。(经过无数次的实验，从A到的E的最短路程确定为ACDE=8 或 ADE=8)二维矩阵算是最简便的抽象方法了，就像图像的解析式，但坏处是不够直观，因此还要把其中的节点用点表示出来，然后再逐个连线，并标注其距离。从最上方的D开始标记，D到E的最短距离为3，就在D的下方写3。然后标记C，从C到E有两条路，即CDE和CE,CDE的距离为5，CE的距离为17，最
7、短距离为5，就在C下方写5依此类推，标记完成后如右图。这样在A的最下的数字便是最短路径了，即8。再由此方法和二维矩阵里的数据做比较。从C行开始标记即元素CD。然后找到D行，在D行中0的右边找最小的一个数字，加到元素CD上去。从B行开始标记即元素BC。然后找到C行，在C行中0的右边找最小的一个数字加到元素BC上去依此类推。最后的结果为:A行中最小的数字便是最短路径的长度。把上述文字抽象成一般算法便得到：在N*N的矩阵中，从第N-2行的第N-1个元素开始标记，直到指导标记到第N-1个元素为止（包括第N-1个元素）。标记第i行的第j个元素的方法为:从第j行中0的右边找最小的数字，加到元素ij上。最后
8、，第一行中最小的数字便是最短路径的长度，最小数字的个数便是最短路径的个数。程序框图如下：pMap是1*N的矩阵，用乘法来将其模拟成二位矩阵，即访问ij的算式为 i*iLen(矩阵宽度)+j。回溯路径：虽然课题是找到最短路径，但我们希望能在求出最短路径的同时找到最短的路径。由最短路径的算法，不难看出，从节点A出发，下一个节点肯定是A行中最小元素所对应的列的节点，依次一次类推，通过求最短路径长度时所得到的pMap矩阵，便可以找到最短路径。程序框图如下：其中pMap为前一框图输出的pMap。iLen为元素的个数。(i+ 代表 i=i+1 )课题补充：至此，我们已经完成的固定起点终点的最短路径算法，但
9、现实中起点以及终点往往要视现实情况而定，因此在此补充一个程序框图，用于变换输入的数据，既将指定的起点，终点分别移动到第一行和最后一行。转换思想：先将第一行和起始所在行，最后一行和终点所在行互换。然后再将起始列与第一列，终止列与于最后一列互换。若以C作为起点，D作为终点。初始状态：第一次交换后：第二次交换后：结束。程序框图如下：（其中 iBegin 为起点在 pMap中所在的行 iEnd为终点在pMap中所在行iLen为节点个数）总结：至此，我们小队的研究活动告一段落了。与其品尝臭豆腐或黄酒，我们更喜欢一些有挑战性的课题。As of Microsoft Internet Explorer 4.0
10、, you can applmultimedia-style effects to your Web pages using visual filters and transitions. You can apply visual filters and transitions to standard HTML controls, such as text containers, images, and other windowless objects. Transitions are time-varying filters that create a transition from one
11、 visual state to another. By combining filters and transitions with basic scripting, you can create visually engaging and interactive documents.Internet Explorer 5.5 and later supports a rich variety of optimized filters. Click the following button to see a demonstration of many of these filters and
12、 how to usetheProcedural surfaces are colored surfaces that display between the content of an object and the objects background. Procedural surfaces define each pixels RGB color and alpha values dynamically. Only the procedure used to compute the surface is stored in memory. The content of an object
13、 with a procedural surface applied is not affected by the procedural surface.警告：此类已序列化的对象将不再与以后的 Swing 版本兼容。当前的序列化支持适合在运行相同 Swing 版本的应用程序之间短期存储或 RMI。从 1.4 版开始，已在 java.beans 包中加入对所有 JavaBeansTM 的长期存储支持。请参见 XMLEncoder。引用类型和原始类型的行为完全不同，并且它们具有不同的语义。引用类型和原始类型具有不同的特征和用法，它们包括：大小和速度问题，这种类型以哪种类型的数据结构存储，当引用类型和原始类型用作某个类的实例数据时所指定的缺省值。对象引用实例变量的缺省值为 null，而原始类型实例变量的缺省值与它们的类型有关。当JAVA程序违反了JAVA的语义规则时，JAVA虚拟机就会将发生的错误表示为一个异常。违反语义规则包括2种情况。一种是JAVA类库内置的语义检查。例如数组下标越界,会引发IndexOutOfBoundsException;访问null的对象时会引发NullPointerException。另一种情况就是JAVA允许程序员扩展这种语义检查，程序员可以创建自己的异常，并自由选择在何时用throw关推动了Web的迅速发展，常用的浏览器现在均支持10