Question

求MATLAB大佬帮忙写段道路投资代码

数学模型已经简化如图，要求结果中包含最优路径图

Answer 1

问题本身是个np难问题，随着点数n的增加，计算量呈n！递增
对于n=10以内的计算，可以用穷举法得到
n再增大，计算的时间就会很长
求全局最优解就没有快速的算法
只能用优化的方法求局部最优解

对于n较小的情况可以用穷举法
因为从某点出发在回到该点的路径是循环的
所以具体从哪点出发得到的解是一样的
而走的顺序是顺时针或者逆时针路程也是一样的
程序如下

n=8;
x=rand(n,1);
y=rand(n,1); %随机n个点坐标
d=squareform(pdist([x,y]));%统计坐标之间的距离

p=perms(2:n); %穷举所有可能路径，1固定为起点
m=factorial(n-1);
l=zeros(m,1); %记录路径长度的矩阵
for ii=1:m
ind=sub2ind([n,n],[1,p(ii,:)],[p(ii,:),1]); %获得路径
l(ii)=sum(d(ind));%计算路径长度
end
[minl in]=min(l); %找出最短路径
a=full(sparse([1,p(in,:)],[p(in,:),1],1,n,n)); %最短路径的连接矩阵
gplot(a,[x y],'-o'); %画最短路径图
axis equal
title(['最短路径长度:' num2str(minl)]);

程序利用随机数，随机生成n个点的x，y坐标
然后统计个点相互中间的距离矩阵d

固定第一点为出发点，利用排列穷举了所有可能路径
找出最短的路径，使用邻接矩阵a表示
最后a是一个nxn的矩阵，里面有n个1，每行只有1个1，每列也只有1个1
其余位置为0

追问

文不对题，我问的是最小投资，不是绕一圈回来的最优路径