平面图中散落10个点，两两配对，共得5条边，计算边的长度和，如何找到长度和最小的配对方案？

平面图中散落10个点，两两配对，共得5条边，计算边的长度和，如何找到长度和最小的配对方案？

用递归遍历吧，9×7×5×3=945种可能，计算量不大。

又写了个动态规划hiahiahia

Pnts=randi(100,[10,2]);
disMat=zeros(10,10);
for i=1:10
    for j=1:10
       disMat(i,j)=norm(Pnts(i,:)-Pnts(j,:)); 
    end
end
[connect,totalLen]=dpMatch(disMat)
plot([Pnts(connect(1:5),1),Pnts(connect(6:10),1)]',...
    [Pnts(connect(1:5),2),Pnts(connect(6:10),2)]','k');
hold on
scatter(Pnts(:,1),Pnts(:,2),'filled')

计算结果
connect =

 1     3
 2     7
 5     8
 6     9
 4    10

totalLen =

102.6540

动态规划函数

function [connect,totalLen]=dpMatch(adjMat)
N=size(adjMat,1);      % 点的数目

UK=dec2bin(1:2^(N)-1); % 可行集合
UK=abs(UK(:,1:N))-48;
UK(mod(sum(UK,2),2)~=0,:)=[];

V=inf.*ones(size(UK,1),1); % 记录每个可行组合路长
tPos=find(sum(UK,2)==2);
tSet=UK(tPos,:);
for i=1:size(tSet,1)
    ind=find(tSet(i,:)==1);
    V(tPos(i))=adjMat(ind(1),ind(2));
end

Comb=zeros(size(UK,1),2); % 记录每个可行组合是由哪些组合构成
Comb(tPos,1)=tPos;

% 当前集合
for k=2:round(N/2)
    tListSet=UK(sum(UK,2)==2*k,:);
    for i=1:size(tListSet,1)
        tList=tListSet(i,:);
        tInd=combnk(find(tList),2);
        subNum=size(tInd,1);
        subListSet=repmat(tList,[subNum,1]);
        subListSet(([tInd(:,1);tInd(:,2)]-1).*subNum+...
                    [(1:subNum),(1:subNum)]')=0;
        p2ListSet=repmat(tList,[subNum,1])-subListSet;
        for j=1:subNum
            vInd1=sum(abs(UK-p2ListSet(j,:)),2)==0;
            vInd2=sum(abs(UK-subListSet(j,:)),2)==0;
            v1=V(vInd1);
            v2=V(vInd2);
            tInd2=sum(abs(UK-tList),2)==0;
            if v1+v2<V(tInd2)
                V(tInd2)=v1+v2;
                Comb(tInd2,:)=[find(vInd1),find(vInd2)];
            end  
        end
    end
end
totalLen=V(end);
CombSet=Comb(end,:);
for i=1:(round(N/2)-2)
    tComb=Comb(CombSet(end),:);
    CombSet(end)=[];
    CombSet=[CombSet,tComb];
end
connect=zeros(round(N/2),2);
for i=1:length(CombSet)
    connect(i,:)=find(UK(CombSet(i),:));
end
end

以A~J 10个街区点为例，相当于是一个不考虑顺序的排列组合问题，
共有C(2,10) * C(2,8) * C(2,6) * C(2,4) * C(2,2) / A(5,5) 种组合方法

最短的5条边路径如下图所示：

源码可参考：

404 https://blog.csdn.net/qq_40985985/article/details/120277165

有帮助请采纳哦~

不想动脑子。。。写了个循环：

Pnts=randi(100,[10,2]);


disMat=zeros(10,10);
for i=1:10
    for j=1:10
       disMat(i,j)=norm(Pnts(i,:)-Pnts(j,:)); 
    end
end

Cmn=combnk(1:10,5);
Len=size(Cmn,1);
ClassList2=Cmn(1:Len/2,:);
ClassList1=Cmn(end:-1:(Len/2+1),:);

connect=[];
LenSet=[];
n=1;
for i=1:length(ClassList1)
    tSet1=ClassList1(i,:);
    tSet2=ClassList2(i,:);
    sSet2S=perms(tSet2);
    for j=1:length(sSet2S)
        LenSet(n)=sum(disMat(tSet1+(sSet2S(j,:)-1).*10));
        connect(n,:)=[tSet1,sSet2S(j,:)];
        n=n+1;
    end
end


minIndex=find(LenSet==min(LenSet));
connect=connect(minIndex(1),:);



plot([Pnts(connect(1:5),1),Pnts(connect(6:10),1)]',...
    [Pnts(connect(1:5),2),Pnts(connect(6:10),2)]','k');
hold on
scatter(Pnts(:,1),Pnts(:,2),'filled')