2

A、B、C、 の5 つの要素が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 でこれを体系的に行うにはどうすればよいでしょうか?

4

2 に答える 2

1

いくつかの一般的なポイント:

  • 元の質問はでタグ付けされていたので、そこでテストした解決策を示します。
  • このソリューションでは、適切なコンパイラを使用して MEX にコンパイルする必要がある FEX にある関数VChooseKおよびVChooseKROを使用します。
  • 質問は距離について語っていますが、不連続なパス (つまりA->C + B->D) を合計する意味はほとんどありませんが、これは質問で無効なものとして明示的に指定されていないため、以下のソリューションもそれらを出力します。
  • OPに示されている例の解決策が示されています。ノードの読み取り可能な結果を​​出力するには、わずかに変更する必要があります250(つまり、ノードの「名前」を文字から数字に変更して、方法を確認します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'
于 2016-12-24T08:25:29.630 に答える