2

我有五个元素A, B,C和。DE

每个元素之间的距离由下面的矩阵给出：

Distances =
    [0  5   3   8   15;
     5  0   7   5   20;
     3  7   0   12  12;
     8  5   12  0   8;
     7  20  12  8   0]

我想选择元素的所有组合，使得距离之和小于10.

它可以通过以下方式递归完成：

  • 首先找到符合条件的 2 项组合的集合。
  • 然后，通过在先前找到的符合条件的 2 项组合中添加另一个项来查找符合 3 项的组合的集合。
  • 等等。

对于上面的示例，手动执行此操作，我得到以下组合：

A,  
B,  
C,  
D,  
E,  
A   B,
A   C,
A   D,
B   C,
B   D,
D   E,  
A   B   C

如果元素的数量很大（比如 250），我将如何在 Octave 中系统地执行此操作？

4

2 回答 2

1

Several general points:

  • Since the original question was tagged with , I will show a solution which I tested there.
  • This solution uses the functions VChooseK and VChooseKRO found on FEX, which need to be compiled into MEX using an appropriate compiler.
  • Even though the question talks about distances, and there's little sense in adding up discontinuous paths (i.e. A->C + B->D), since this is not specified explicitly in the question as something invalid, the solution below outputs them as well.
  • The solution is shown for the example given in the OP. It should be modified slightly to output readable results for 250 nodes, (i.e. change the node "names" from letters to numbers seeing how 26 < 250).
  • Outputs are currently only printed. Some modifications need to be made (in the form of temporary variables) if further computations are required on the result.

function q41308927
%% Initialization:
nodes = char((0:4) + 'A');
D = [0  5   3   8   15;
     5  0   7   5   20;
     3  7   0   12  12;
     8  5   12  0   8;
     7  20  12  8   0];
thresh = 10;
d = triu(D); % The problem is symmetric (undirected), so we only consider the upper half.
% Also keep track of the "letter form":
C = reshape(cellstr(VChooseKRO(nodes,2)), size(D)).'; % "C" for "Combinations"
%{
C = 

  5×5 cell array

    'AA'    'AB'    'AC'    'AD'    'AE'
    'BA'    'BB'    'BC'    'BD'    'BE'
    'CA'    'CB'    'CC'    'CD'    'CE'
    'DA'    'DB'    'DC'    'DD'    'DE'
    'EA'    'EB'    'EC'    'ED'    'EE'
%}
C = C(d>0); d = d(d>0);
assert(numel(C) == numel(d)); % This is important to check
%% Find eligible sets of size n
for k = 1:numel(nodes)  
  if numel(d)<k
    break
  end
  % Enumerate combinations:
  C = C(VChooseK(1:numel(C),k));
  d = sum(VChooseK(d,k),2);  
  % Filter combinations:
  if any(d < thresh)    
    C(d >= thresh,:) = [];
    d = d(d < thresh);
    disp(sortrows(C)); % This is just to show it works like the manual example
  else
    break  
  end    
end

The output of the above is:

'AB'
'AC'
'AD'
'BC'
'BD'
'DE'

'AB'    'AC'
'AC'    'BD'
于 2016-12-24T08:25:29.630 回答
0

这是一个普通的 Octave（或 Matlab）解决方案。矩阵Distances与问题相同。该算法构建一个 0-1 矩阵a，其中每一列编码一个距离总和小于limit（例如 10）的集合。

矩阵a用恒等元初始化，因为所有单元素子集都是可接受的（距离之和为 0）。然后选择每一列c = a(:,m);并研究添加另一个元素的可能性（cand = c; cand(k) = 1;意味着添加第 k 个元素）。不失一般性，只考虑在集合的最后一个当前元素之后添加元素就足够了。

乘积cand'*Distances*cand是候选集距离之和的两倍cand。因此，如果它小于限制的两倍，则添加该列：a = [a cand];. 最后，a为了便于阅读，矩阵以转置形式显示。

limit = 10;
n = length(Distances);    
a = eye(n, n);
col1 = 1;
col2 = n;

while (col1 <= col2)
  for m = col1:col2
    c = a(:,m);
    for k = max(find(c>0))+1:n
      cand = c;
      cand(k) = 1;
      if cand'*Distances*cand < 2*limit
        a = [a cand];
      end
    end
  end
  col1 = col2 + 1;
  col2 = length(a);
end

disp(a')

输出：

   1   0   0   0   0
   0   1   0   0   0
   0   0   1   0   0
   0   0   0   1   0
   0   0   0   0   1
   1   1   0   0   0
   1   0   1   0   0
   1   0   0   1   0
   0   1   1   0   0
   0   1   0   1   0
   0   0   0   1   1

对于 250 x 250 矩阵，性能在很大程度上取决于大小limit。如果它太大以至于所有或大部分 2^250 集都符合条件，那么这将耗尽内存。（2 ^ 250 比 10 ^ 75 多，所以我认为你不会想在这么多套附近看到任何地方）。

这是为了以更易读的形式输出：

for m = 1:length(a)
  disp(find(a(:,m))')
end

输出：

 1
 2
 3
 4
 5
   1   2
   1   3
   1   4
   2   3
   2   4
   4   5
于 2016-12-24T23:17:28.810 回答