建模二作业五

衡阳师范学院数学与计算科学系。

学生实验报告。

实验课程名称数学建模（2

系别：数计系年级： 2012 专业和班级：数学 2 班。

学生姓名。学号。

开课时间： 2014 年下学期。

2014-10-16 星期四。

某航空公司在6个城市c1——c6中有分公司，从ci到cj的直接航程票价（cij）用矩阵表示如下（表示无直接航路）：

请帮助公司设计一张从城市c1到其他城市之间的票价最便宜的路线图。

我们使用迪克斯特拉（dijkstra）算法求解。

迪克斯特拉算法的基本思想是：设置两个接点的集合和，集合中存放已找到最短路径的接点，集合中存放当前还未找到最短路径的接点。初始态时，集合中只包含源点，设置，然后不断从集合中选择到原点路径长度最短的接点加入到集合中，集合中没加入一个新的接点都要修改从源点到集合中剩余接点的当前最短路径长度值，集合中各接点的新的当前最短路径长度值，为原来最短路径长度值与从源点到过结点到底该节点的路径长度中的较小者。

此过程不断重复，直到集合t中的接点全部加入集合中为止。

求第一个城市到其它城市的最短路径的 matlab 程序如下：

clc,clear

a=zeros(6);

a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;

a(2,3)=15;a(2,4)=20;a(2,6)=25;

a(3,4)=10;a(3,5)=20;

a(4,5)=10;a(4,6)=25;

a(5,6)=55;

a=a+a';

a(find(a==0))=inf;

pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));

d(1:length(a))=inf;d(1)=0;temp=1;

while sum(pb)tb=find(pb==0);

d(tb)=min(d(tb),d(temp)+a(temp,tb));

tmpb=find(d(tb)==min(d(tb)))

temp=tb(tmpb(1));

pb(temp)=1;

index1=[index1,temp];

temp2=find(d(index1)==d(temp)-a(temp,index1));

index2(temp)=index1(temp2(1));

endd, index1, index2

运行结果为：d =

index1 =

index2 =

根据运行结果，可知：

从城市c1到城市c2之间的票价最便宜的路线图为：c1--c6--c2，票价为35；

从城市c1到城市c3之间的票价最便宜的路线图为：c1--c5--c3，票价为45；

从城市c1到城市c4之间的票价最便宜的路线图为：c1--c6--c4，票价为35；

从城市c1到城市c5之间的票价最便宜的路线图为：c1---c5，票价为25；

从城市c1到城市c6之间的票价最便宜的路线图为：c1---c6，票价为10；

从城市c1到其他所有城市的票价最便宜的路线图为：c1-c6-c5-c2-c4-c3，票价为150；

算法的时间复杂度和空间复杂度：

时间频度是指一个算法执行所耗费的时间，从理论上是不能算出来的。一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。

记为t(n)。

在时间频度中，n称为问题的规模，当n不断变化时，时间频度t(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用t(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，t（n)/f(n)的极限值为不等于零的常数，则称f(n)是t(n)的同数量级函数。记作t(n)=ｏf(n)),称ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

求解时间复杂度的matlab程序为：

递归输出一个字符串的右半部分。

var right = function(str）

var length =

%辅助函数。

var help = function（index）

基本情况：什么也不做。

help(0);

空间复杂度s(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

建模二作业五

建模二作业二

数学建模作业五

数学建模作业二

其他用户还读了

建模二作业五

建模二作业二

数学建模作业 五

数学建模作业 二

其他用户还读了

数学建模作业五

数学建模作业二