在 MATLAB 中返回到此函数的值是否有问题导致错误答案？

Question

我下面的代码应该 return 给定网络的 max_flow 值为 7 但它 returns 2. 我确信我的错误仅限于从 s 到 t 因为我已经用我有更多经验的 c++ 重新编写了程序。我还打印了我的残差图以查看发生了什么，这显然也是不正确的。一方面，它不应该有负整数。

 0     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0    -2     2
 0     0     0     2     0     6
 0     0     0    -2    -6     0

我也亲手验证了它的7。在我的 c++ 主函数中，我使用 while (int sent = dfs(s, t, INF)) 作为我的 while 循环的条件，但在 MATLAB 中，我认为等效的是 while sent == dfs(s,t,INF)。我认为这可能是问题所在，但我找不到替代方案，也不知道我的逻辑漏洞在哪里。我知道 MATLAB 有一个内置的 maxlow 函数，但我想构建自己的函数作为学习经验。我正在使用深度优先搜索在我的残差图中找到从源到汇的路径 Flow。我将不胜感激任何关于修复此问题的指示以及您认为 should/could 需要改进的任何其他内容

    function ff
    clear;

%adjacency matrix representing capacities


    Cap =  [0, 4, 5, 0, 0, 0;
            0, 0, 2, 1, 4, 0;
            0, 0, 0, 0, 3, 0;
            0, 0, 0, 0, 0, 2;
            0, 0, 0, 2, 0, 6;
            0, 0, 0, 0, 0, 0;
                            ];




    len = length(Cap)

    Flow =zeros([len,len])
     
   
    
% source and sink
 INF=99999;
 s = 1; 
 t = 6; 
 max_flow=0;
 
 sent = 0;
 
 visited=boolean(zeros(1,len));
 
   sent = dfs(s,t,INF);

   while  sent == dfs(s,t,INF)
       
       max_flow =+ sent;

       visited=boolean(zeros(1,len));
      
   end
  
  disp('Residual graph:');
  disp(Flow);
  disp(['Max flow is ' num2str(max_flow)]);


%%dfs


    function F= dfs(Source,Sink,minimum)
      
       
      
     visited(Source) = true;
     
      
       if Source==Sink
          F = minimum;
        end 
 
       for  i = drange (2:length(visited))
            flow_cap = Cap(Source,i) - Flow(Source,i);
            
           

            if visited(i)==false && flow_cap > 0
                 visited(i) = true
             
            

                  if sent == dfs(i,Sink,min(minimum,flow_cap))
                     Flow(Source,i) =  Flow(Source,i)+sent;
                     Flow(i,Source) = Flow(i,Source)-sent ;
                     F=sent;
                  
                  end

          
           end

         F=sent;
         
        end
       
   end
  
end

Answer 1

我没有检查你的代码，但为什么不简单地使用 MATLAB 自己的 maxflow 函数呢？

>> Cap =  [0, 4, 5, 0, 0, 0;
           0, 0, 2, 1, 4, 0;
           0, 0, 0, 0, 3, 0;
           0, 0, 0, 0, 0, 2;
           0, 0, 0, 2, 0, 6;
           0, 0, 0, 0, 0, 0;
                           ];
>> g = digraph(Cap)
g =
  digraph with properties:

    Edges: [9x2 table]
    Nodes: [6x0 table]
>> maxflow(g,1,6)
ans =
     7

这给出了您预期的答案 7。

Answer 2

与一样，sent == … 不会像在 C++ 中那样更新 sent。您不能更新表达式内的变量（AFAIK）。在 MATLAB 中，您将在循环内更新 sent。

此外，max_flow =+ sent 不等同于 C++ 中的 max_flow += sent。您正在将粗心的 + 应用到 sent，它什么也不做，然后将结果分配给 max_flow。也就是说，你在做 max_flow = +sent.

这将是 MATLAB 中的正确循环：

sent = dfs(s,t,INF);
while sent
   max_flow += sent;
   visited = zeros(1,len,'logical');
   sent = dfs(s,t,INF);
end

最后，与 dfs 函数共享 visited 是不好的做法。您应该尝试在任何地方都只使用局部变量。您可以将数组传递给函数，然后再次 return 它，例如 [sent,visited] = dfs(s,t,INF,visited).

在 MATLAB 中返回到此函数的值是否有问题导致错误答案？

Is there an something wrong with the value being returned to this function in MATLAB resulting in an incorrect answer?

matlab