任意选择10个全国省会城市，并标注各个城市之间的距离，使用MATLAB对相应的10个城市进行拓扑图的绘制。通过列出相应算法的设计思路及方案，实现邮件投递的最短邮路。

• 算法及数学模型

• 设计思路：将邮件从昆明出发送达每一个城市，使之邮递路线最短，由此选择TSP算法进行代码实现。

  任意选择十个城市并列出距离矩阵

• 1、昆明 2、成都 3、上海 4、天津 5、厦门 6、北京 7、武汉 8、杭州 9、西安 10、深圳

• 测试结果

  

算法代码

Test

function dis = test(arc,w)

name={'昆明','成都','上海','天津','厦门','北京','武汉','杭州','西安','深圳'};

    n=length(arc);

        edgeCount=1;TSPLength=0;

        flag=1:n; %初始化了一个flag，用来记录哪些点被遍历过

        flag(:)=0; %表示所有点都还未被走过

        u=w;

        flag(w)=1; %用来标识起点

        fprintf(char(name(1)))

        while edgeCount<n

            min=10000;

            for j=1:n

                if(flag(j)==0 && arc(u,j)~= inf && arc(u,j)<min)

                    v=j; min=arc(u,j);

                end           

            end

            TSPLength=TSPLength+arc(u,v);

            flag(v)=1;

            edgeCount=edgeCount+1;

            fprintf('-->')

             fprintf(char(name(v)))

            u=v;

        end  

        fprintf('\n')

        fprintf('最短路径长度为:')

       TSPLength

end

Test1

clear all

clc

%%MATLAB期末作业——从昆明出发将邮件送往10个城市，规划一条投递线路是邮路最短

%绘制10个城市的拓扑结构（根据地图比例及几何坐标绘制），标注出必要的各个城市的距离

%%利用TSP算法求最小路径

disp('选定城市——1 昆明 2 成都 3 上海 4 天津 5 厦门 6 北京 7 武汉 8 杭州 9 西安 10 深圳')

 tic

    arc(1,1)=inf;arc(1,2)=817;arc(1,3)=2342;arc(1,4)=2584;arc(1,5)=1959;

    arc(1,6)=2590;arc(1,7)=1558;arc(1,8)=2157;arc(1,9)=1487;arc(1,10)=1441;

    arc(2,:)=[817,inf,1968,1877,1978,1804,1143,1890,744,1711];

    arc(3,:)=[2342,1968,inf,1083,1012,1213,824,177,1375,1455];

    arc(4,:)=[2584,1877,1083,inf,1945,134,1148,1199,1098,2164];

    arc(5,:)=[1959,1978,1012,1945,inf,2012,966,875,1737,577];

    arc(6,:)=[2590,1804,1213,134,2012,inf,1154,1260,1070,2169];

    arc(7,:)=[1558,1143,824,1148,966,1154,inf,732,780,1107];

    arc(8,:)=[2157,1890,177,1199,875,1260,732,inf,1330,1273];

    arc(9,:)=[1487,744,1375,1098,1737,1070,780,1330,inf,1730];

    arc(10,:)=[1441,1711,1455,2164,577,2169,1107,1273,1730,inf];

    disp('经过赋值后的邻接矩阵为:')

        arc

    

    disp('最短路径为:')

test(arc,1)

t1=toc

    s = [1,1,1,1,1,1,1,1,1,...

         2,2,2,2,2,2,2,2,...

         3,3,3,3,3,3,3,...

         4,4,4,4,4,4,...

         5,5,5,5,5,...

         6,6,6,6,...

         7,7,7,...

         8,8,...

         9];

    t = [2,3,4,5,6,7,8,9,10,...

         3,4,5,6,7,8,9,10,...

         4,5,6,7,8,9,10,...

         5,6,7,8,9,10,...

         6,7,8,9,10,...

         7,8,9,10,...

         8,9,10,...

         9,10,...

         10];

    

    arc1=[817,2342,2584,1959,2590,1558,2157,1487,1441,...

          1968,1877,1978,1804,1143,1890,744,1711,...

          1083,1012,1213,824,177,1375,1455,...

          1945,134,1148,1199,1098,2164,...

          2012,966,875,1737,577,...

          1154,1260,1070,2169,...

          732,780,1107,...

          1330,1273,...

          1730];    

      

    name={'昆明','成都','上海','天津','厦门','北京','武汉','杭州','西安','深圳'};

    G=graph(s,t,arc1,name);

    plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2);

    p=plot(G)

    T=minspantree(G);

highlight(p,T,'EdgeColor','red','LineWidth',3)

clear all

tic

  max=inf;    

    arc(1,1)=max;arc(1,2)=817;arc(1,3)=2342;arc(1,4)=2584;arc(1,5)=1959;

    arc(1,6)=2590;arc(1,7)=1558;arc(1,8)=2157;arc(1,9)=1487;arc(1,10)=1441;

    arc(2,:)=[817,max,1968,1877,1978,1804,1143,1890,744,1711];

    arc(3,:)=[2342,1968,max,1083,1012,1213,824,177,1375,1455];

    arc(4,:)=[2584,1877,1083,max,1945,134,1148,1199,1098,2164];

    arc(5,:)=[1959,1978,1012,1945,max,2012,966,875,1737,577];

    arc(6,:)=[2590,1804,1213,134,2012,max,1154,1260,1070,2169];

    arc(7,:)=[1558,1143,824,1148,966,1154,max,732,780,1107];

    arc(8,:)=[2157,1890,177,1199,875,1260,732,max,1330,1273];

    arc(9,:)=[1487,744,1375,1098,1737,1070,780,1330,max,1730];

    arc(10,:)=[1441,1711,1455,2164,577,2169,1107,1273,1730,max];

    names={'昆明','成都','上海','天津','厦门','北京','武汉','杭州','西安','深圳'};

     for n=1:3

         fprintf('第%d次检测:\n',n);

         Length=0;

         r=randperm(9)+1;

           Length=Length+arc(1,r(1));

         for i=2:9

               Length=Length+arc(r(i-1),r(i));

         end

         fprintf('   随机选择的路径为:');

          fprintf(char(names(1)))

         for j=2:9

              fprintf('--->')

              fprintf(char(names(r(j))))

         end

         fprintf('\n      随机选择的路径长度为:');

         fprintf('%d\n', Length);

         end

t2=tic

• 目录

  算法及数学模型

  测试结果

  算法代码

  参考文献

  ---

上述城市间距均来自百度地图