Как вы получаете вывод от всех детей в рекурсивной функции? - PullRequest
Новая
       14

Как вы получаете вывод от всех детей в рекурсивной функции?

2 голосов
/ 29 апреля 2019

Я пытаюсь написать скрипт, чтобы найти все пути от источника к стоку в вашей типичной проблеме максимального потока. В целом это будет служить шагом 1 при реализации алгоритма Форда-Фулкерсона в качестве проекта для класса.

Я выполнил некоторую базовую отладку, но, похоже, происходит то, что алгоритм не выдает все дочерние элементы, которые должны быть через цикл for, а вместо этого просто находит один и тот же путь несколько раз, а затем завершается. 

#pathfinder
function final=pathFinder(A,path) #call with path=1 to initiate
    #A is a matrix that looks like
    # u v w where uv is an edge, and w is its weight (weight is used later)
    vert=path(numel(path)); #get last vertex used
    F=find(A(:,1)'==vert); #find incident edges
    disp("F is");
    disp(F); #displaying these for debugging purposes
    if(sum(F)==0) #terminates with no more edges (happens only at sink)
      #save externally
      disp("path found!");
      disp(path);
      final=0; #terminate it
    else
     for i=1:numel(F) #this should split this up in "children" for recursion, but it does not. Why?
        b=F(i);
        path=[path, A(b,2)]; #add new vertex/edge to path
        disp("non-final path");
        disp(path);
        disp("going deeper");
        final=pathFinder(A,path); #recurs on next vertex
     endfor
    endif
endfunction

Пример графика, который я использую: 

A=[1 2 0; 1 3 0; 2 3 0; 2 4 0; 3 4 0];

, которые должны иметь пути [1 2 3 4], [1 2 4], [1 3 4] (в порядке, указанном в алгоритме).

1 Ответ

2 голосов
/ 03 мая 2019

С вашим кодом есть две проблемы:

  1. vert=path(numel(path)) говорит о том, что количество элементов на пути - это индекс вершины, с которого вы хотите начать.Это не верно.Вам нужно использовать vert=path(end), последний элемент в пути.

  2. В цикле вы обновляете path.Следующая итерация цикла, поэтому вы используете измененный path, а не возврат.Вам нужно изменить ввод path для следующего рекурсивного вызова, но не локальной переменной path.

Это исправленный код: 

function pathFinder(A,path) % call with path=1 to initiate
   % A is a matrix that looks like
   %  u v w where uv is an edge, and w is its weight (weight is used later)
   vert=path(end); % get last vertex used
   F=find(A(:,1)'==vert); % find incident edges
   if isempty(F) % terminates with no more edges (happens only at sink)
      % save externally
      disp(path);
   else
      for b=F % loop over the incident edges
         pathFinder(A,[path, A(b,2)]); % recurse on next vertex
      end
   end
end

Я удалил выходные данные отладки для краткости.Я также изменил некоторые вещи только для октав (endfor, # комментарии) на что-то, что также будет работать в MATLAB.

...