0

我正在尝试在 MATLAB中实现“ Sprague-Grundy 定理”。这个定理本质上试图找到数组中的最小排除元素，例如在数组 [0 1 3 4 5] 中，该值将是 2。除此之外，该函数需要能够沿不同行递归矩阵（特别是图论中的邻接矩阵）例如，如果我有邻接矩阵：

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

如果我将此矩阵用作输入，并且函数从第 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 回答