查看: 1665|回复: 2

[问题求助] MATLAB中的floyd算法优化问题

字体大小: 正常放大

[______]

1 主题	13 听众	157 积分

升级 28.5%

TA的每日心情

	擦汗 2015-9-14 08:05

签到天数: 14 天

[LV.3]偶尔看看II

自我介绍: 数模新人一只

电梯直达

1^#

发表于 2014-7-24 11:18 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

本帖最后由 [______] 于 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

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

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

调用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

上述程序计算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循环太多呢？如果是要怎么提高速度……