Как преобразовать рекурсию в итерационный способ ветвления и связанного алгоритма в Matlab - PullRequest
Новая
       9

Как преобразовать рекурсию в итерационный способ ветвления и связанного алгоритма в Matlab

0 голосов
/ 01 мая 2018

У меня проблема с преобразованием алгоритма ветвления и связывания из рекурсивного в итеративный. Код для рекурсивного метода следующий: 

function [xx,val,status,bb]=bnb(f,A,b,Aeq,beq,lb,ub,x,v,M,e,bound) 

[x0,val0,status0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options); 

if status0<=0 | val0 > bound  
    ...
    return
end

ind=find( abs(x0(M)-round(x0(M)))>e ); 
if isempty(ind)       
    if val0 < bound   
        ...
    else
        ...
    end
    return
end

...

A1=[A ; zeros(1,c)];
A1(end,br_var)=1;
b1=[b;floor(br_value)];

A2=[A ;zeros(1,c)];
A2(end,br_var)=-1;
b2=[b; -ceil(br_value)];

[x1,val1,status1,bound1]=bnb(f,A1,b1,Aeq,beq,lb,ub,x0,val0,M,e,bound);
if status1 >0 & bound1<bound
   ...
end

[x2,val2,status2,bound2]=bnb(f,A2,b2,Aeq,beq,lb,ub,x0,val0,M,e,bound);

if status2 >0 & bound2<bound  
    ...
end

У меня проблема с переходом к двум переменным. В рекурсивном методе ограничения неравенства разделяются на два подусловия A1, b1 и A2, b2, и называются две подфункции. Однако, итеративно, у меня есть проблема, чтобы вызвать эти ограничения отдельно. В этом текущем состоянии мой код, как описано ниже. Однако это не работает. Что не так с моим кодом здесь? 

while ~isempty(nactivenodes)
    currentnode = nactivenodes(1)
    exnode = nactivenodes(1);
    nactivenodes(1) = [];
    [x0,val0,status0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options); 

    if state0 <= 0 || val0 > bound  
        ...
        %no return
    else
        ind = find(abs(x0(M) - round(x0(M))) > eps);
        if isempty(ind)
            state = 1;        
            if val0 < bound    % this solution is better than the current solution
                ...
            else
               ...
            end
            %no return
        else
            ...

            nactivenodes(end+1) = currentnode+exnode;
            nactivenodes(end+1) = currentnode+exnode+1
            if mod(nactivenodes(1),2) == 0
                A=[A ; zeros(1,c)];
                A(end,br_var)=1;
                b=[b;floor(br_value)];
            elseif mod(nactivenodes(1),2) == 1
                A=[A ;zeros(1,c)];
                A(end,br_var)=-1;
                b=[b; -ceil(br_value)];
            end

        end
    end
end
...