数学建模 钢管订购和运输(6)

a(7,32)=31;a(8,24)=12; a(9,23)=42;a(10,22)=70; a(11,33)=10;a(12,35)=10; a(13,19)=62;a(14,36)=110; a(14,18)=30;a(15,16)=20; a(15,17)=20;a(16,17)=-30;

a(17,18)=-290;a(18,19)=-160; a(18,36)=-70;a(19,20)=-320;

a(19,35)=260;a(19,36)=100; a(33,35)=190;a(20,33)=130;

a(20,21)=-160;a(20,35)=-70; a(21,22)=-170;a(21,33)=-88; a(21,37)=-690;a(22,23)=-520; a(23,24)=-720;

a(23,38)=-690;a(24,25)=-1100;a(24,32)=-202;a(24,39)=-1200;a(25,26)=-1150;

a(26,27)=-450;a(26,28)=-80; a(29,30)=-306;a(30,31)=-195;

26

a(31,32)=-20;a(33,34)=-462; for i=1:39 for j=1:i a(i,j)=a(j,i); end; end;

sw=[32 39 38 37 34 36 16]; aw=[23 33 20 35 19 36]; [T,G]=getminArr(a,sw,aw);

%a=[0 -9 inf 3 inf ;-9 0 2 inf 7;inf 2 0 2 4;3 inf 2 0 inf;inf 7 4 inf 0];findPath(a,1,4,0) %[T,G]=getminpath(a,16,10); %G

unction [T,G]=getminArr(a,sw,aw)

[i,m]=size(sw) [j,n]=size(aw); for i=1:m for j=1:n

[T(i,j),G(i,j)]=getminpath(a,sw(i),aw(j));

27

end; end; T G

function [T,G]=getminpath(a,beg,over) mn=size(a,1);

allPaths=findPath(a,beg,over,0); n=size(allPaths,1); Idmin=1; Smin=inf; t=zeros(1,n); g=zeros(1,n); m=zeros(1,n); for i=1:n for j=2:mn+1 if allPaths(i,j)==0 break; end;

w=a(allPaths(i,j-1),allPaths(i,j)); if w<0

t(i)=t(i)+abs(w);

28

end; if w>0 g(i)=g(i)+w; end;

if allPaths(i,j)==over break; end; end; end; for i=1:n

m(i)=getTC(t(i),1)+getGC(g(i),1); if m(i)

function possiablePaths = findPath(Graph, partialPath, destination, partialWeight) % findPath按深度优先搜索所有可能的从partialPath出发到destination的路径，这些路径中

29

不包含环路

% Graph: 路网图，非无穷或0表示两节点之间直接连通，矩阵值就为路网权值 % partialPath: 出发的路径，如果partialPath就一个数，表示这个就是起始点 % destination: 目标节点

% partialWeight: partialPath的权值，当partialPath为一个数时，partialWeight为0 pathLength = length(partialPath);

lastNode = partialPath(pathLength); %得到最后一个节点

nextNodes = find(Graph(lastNode,:)

GLength = length(Graph); possiablePaths = [];

if lastNode == destination

% 如果lastNode与目标节点相等，则说明partialPath就是从其出发到目标节点的路径，结果只有这一个，直接返回 possiablePaths = partialPath;

possiablePaths(GLength + 1) = partialWeight; return;

elseif length( find( partialPath == destination ) ) ~= 0 return; end

%nextNodes中的数一定大于0,所以为了让nextNodes(i)去掉，先将其赋值为0 for i=1:length(nextNodes)

30