查找距离总和小于给定数字的有限度量 space 的所有子集

Question

我有五个元素 A、B、C、D 和 E。

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

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 中系统地执行此操作？

Answer 1

几个一般点：

由于原始问题被标记为 matlab，我将展示一个我在那里测试过的解决方案。
此解决方案使用 FEX 上的函数 VChooseK and VChooseKRO，需要使用适当的编译器将其编译到 MEX 中。
即使问题讨论的是距离，并且将不连续的路径（即 A->C + B->D）相加没有什么意义，因为这在问题中没有明确指定为无效的东西，下面的解决方案将它们输出为嗯。
针对 OP 中给出的示例显示了解决方案。它应该稍微修改以输出 250 节点的可读结果，（即将节点 "names" 从字母更改为数字，看看如何 26 < 250）。
当前仅打印输出。如果需要对结果进行进一步的计算，则需要进行一些修改（以临时变量的形式）。

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

上面的输出是：

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

'AB'    'AC'
'AC'    'BD'

Answer 2

这是一个普通的 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

输出：

查找距离总和小于给定数字的有限度量 space 的所有子集

Find all subsets of a finite metric space for which the sum of distances is less than a given number

matlab

combinations

octave

path-finding

undirected-graph