数学建模社区-数学中国
标题: MATLAB中的floyd算法优化问题 [打印本页]
作者: [______] 时间: 2014-7-24 11:18
标题: MATLAB中的floyd算法优化问题
本帖最后由 [______] 于 2014-7-24 11:21 编辑
最近在做2011年mcm国赛B题（交巡警服务平台的配置）
用到了floyd算法求两节点之间的最短路径。
在网上找了MATLAB里的floyd函数,在第一问计算A区节点的时候效果很好，大概2分钟就出来了结果，然后同样的代码想算第二问的全市平台配置时就运算不出结果了（没报错但好几个小时都不出结果）。在此向各位前辈高手请教下是哪里出问题了，怀疑是第二问数据量太大而整个程序中的for循环太多了（但也不应该这么久啊，第二问的数据量也不至于比第一问多太多……）
废话不说上代码了：
第一问：
构建邻接矩阵
clc;
clear;
edge=xlsread('A区内部道路联通关系');
n=92;
weight=inf*ones(n, n);
for i=1:size(edge,1)
weight(edge(i,1),edge(i,2))=edge(i,3);
weight(edge(i,2),edge(i,1))=edge(i,3);
weight(i,i)=0
end
附录2：
定义floyd函数(n根据A区情况定义)
%Floyd算法
%解决最短路径问题，是用来调用的函数头文件
%输入参数a是求图的带权邻接矩阵，D(i,j)表示i到j的最短距离, %输入参数a是所求图的带权邻接矩阵，i,j起点终点,min1表示i与j最短距离，path1为最短路径
function[min1]=floyd(a,start,terminal)
D=a;n=92;path=zeros(92,92);
fori=1:n;
forj=1:n;
ifD(i,j)~=inf; %不相连路口距离定义为inf
path(i,j)=j;
end
end
end
fork=1:n;
fori=1:n;
forj=1:n;
ifD(i,k)+D(k,j)<D(i,j);
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end
end
end
end
ifnargin==3
min1=D(start,terminal);
m(1)=start;
i=1;
whilepath(m(i),terminal)~=terminal;
k=i+1;
m(k)=path(m(i),terminal);
i=i+1;
end
end
调用floyd函数对A区道路进行计算
b=weight
c=zeros(1840,3); %20个平台*92个路口为1840
fori=1:20
forj=1:92
c(92*(i-1)+j,
=[i,j,floyd(b,i,j)]
end
end
上述程序计算A区路口之间的关系，运行很成功
然后算第二问时我把邻接矩阵、floyd中的矩阵放大，确再也运行不出了…………
PS：那些笑脸是冒号和右圆括号……论坛识别为表情了
floyd函数修改
function [min1]=floyd(a,Start,terminal)
D=a;n=size(D,1);path=zeros(n,n);
主程序①（分不同城区）
clc;
clear;
edge=xlsread('all路口联通关系');
e=582;
weight=inf*ones(e,e);
for s=1:size(edge,1);
weight(edge(s,1),edge(s,2))=edge(s,3);
weight(edge(s,2),edge(s,1))=edge(s,3);
end
for t=1:582
weight1(t,t)=0;
end
%%
c=zeros(8244,3);
b=weight;
%%
%a area内部情况
for i=1:20;
for j=1:92;
c(92*(i-1)+j,
=[i,j,floyd(b,i,j)];
end
end
%%
%b area内部情况
for i=93:100;
for j=93:165;
c(1840+73*(i-93)+j-92,
=[i,j,floyd(b,i,j)];
end
end
%%
%c area内部情况
for i=166:182;
for j=166:319;
c(2424+154*(i-166)+j-165,
=[i,j,floyd(b,i,j)];
end
end
%%
%d area内部情况
for i=320:328;
for j=320:371;
c(5042+52*(i-320)+j-319,
=[i,j,floyd(b,i,j)];
end
end
%%
%e area内部情况
for i=372:386;
for j=372:474;
c(5510+103*(i-372)+j-371,
=[i,j,floyd(b,i,j)];
end %%
%f area内部情况
for i=475:485;
for j=475:582;
c(7055+108*(i-475)+j-474,
=[i,j,floyd(b,i,j)];
end
end
主程序②（不分城区582个路口全部一起算）
clc;
clear;
edge=xlsread('all路口联通关系');
e=582;
weight=inf*ones(e,e);
for s=1:size(edge,1);
weight(edge(s,1),edge(s,2))=edge(s,3);
weight(edge(s,2),edge(s,1))=edge(s,3);
end
for t=1:582
weight1(t,t)=0;
end
c=zeros(338724,3); %582的平方为3338724
b=weight1;
for i=1:size(b,1);
for j=1:size(b,2);
c(582*(i-1)+j,
=floyd(b,i,j);
end
end
无论是主程序①还是②，运行后都长时间没反应，也不报错……到底是不是for循环太多呢？如果是要怎么提高速度……
cumcm2011B.doc
(13 KB, 下载次数: 0)
cumcm2011B附件1_A区和全市六区交通网络与平台设置的示意图.doc
(100.5 KB, 下载次数: 0)
cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls
(114 KB, 下载次数: 0)
all路口联通关系.xls
(62 KB, 下载次数: 0)
A区内部道路联通关系.xls
(31 KB, 下载次数: 0)
作者: 且生 时间: 2014-7-24 21:09
楼主改发成代码形式，方便大家看代码，在表情边上有个<>。比如……
作者: [______] 时间: 2014-7-26 10:30
且生 发表于 2014-7-24 21:09 
楼主改发成代码形式，方便大家看代码，在表情边上有个。比如……
也就一处，没关系吧
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |