0

MATLAB で「 Sprague–Grundy の定理」を実装しようとしています。この定理は基本的に、配列内の最小の除外要素を見つけようとします。たとえば、配列 [0 1 3 4 5] では、値は 2 になります。さらに、関数は、配列内の異なる行に沿って再帰できる必要があります。行列 (具体的には、グラフ理論からの隣接行列) たとえば、隣接行列があるとします。

10000

10000

0 0 0 1 0

0 1 0 0 0

0 0 1 0 0

この行列を入力として使用し、関数が 5 行目から開始された場合、行 "0 0 1 0 0" を反復し、3 列目に 1 が表示されると、関数は 3 列目に再帰します。行、次に 4 番目、次に 2 番目、そして 1 番目に再帰します。

私が問題を抱えているのは、関数入力がmatrix/arrayである再帰を行うことです。関数入力が整数の場合、再帰は十分に単純だと思いますが、行列/配列では、値を「追跡」して必要な最終配列を取得する方法がわかりません。これまでのところ、これは私のmatlabコードです:

function [ y ] = S_Grundy( X,r,m )
%   Recursively finds the SG value given an adj matrix, 

Row_ones = find(X(r,:) == 1)
y=0.*size(Row_ones,2);

% if(numel(Row_ones)==0)
%     y(:)=0;
%     return
% end


for i=1:size(Row_ones,2)

    if(Row_ones(i) >= m) 
       y = S_Grundy(X,Row_ones(i),m);
    end
end

if (Row_ones(i) < m)

    for j=0:max(Row_ones)
        if(isempty(find(Row_ones==j)));%&&(isempty(find(Row_ones==0))))
            y(i)=j;
        else
            y(i)=777;

%                 if(isempty(find(Row_ones==j)))
%                     y(i)=j;
%                 end
            end    
        end

    end   
end
4

1 に答える 1

0

したがって、質問を言い換えると、開始頂点から到達できないように、最小限のインデックスを持つ頂点を見つけようとしていますが、それは正しいですか?

私は再帰をまったく使用しません。これまでに到達した頂点から到達可能な頂点のセットを、それ以上見つからなくなるまで段階的に構築します。

graph = [1 0 0 0 0; 1 0 0 0 0; 0 0 0 1 0; 0 1 0 0 0; 0 0 1 0 0]

start = 5

component = graph(start, :)
lastcomponent = zeros(1, 5)

while (sum(component) > sum(lastcomponent))
    lastcomponent = component
    component = sign(sum(graph(find(component == 1), :), 1) + lastcomponent)
endwhile

result = min(find(component == 0))

（おそらくもっとうまく書くことができます。私はmatlabのプロではありません。しかし、あなたはその考えを理解する必要があります）

于 2015-03-16T14:38:53.563 に答える