%**************************************
%
% Model trgovskega potnika
%
% Pomožna funkcija metropolis in potrebne podfunkcije
%
% (c) 2009 Matej Bažec
%
%**************************************

function [a,l]=metropolis(a0,m,t)
    a=a0;
    n=length(a);
    l=distance(a0,m,n);
    b=1/t;
    for j=1:1000*n
        [a,l]=sweep(a,m,b,n,l);
    end;
end

function [a,l]=sweep(a0,m,t,n,l1)
    a=a0;
    i1=1+floor(n*rand());
    i2=1+floor(n*rand());
    if i1>n
        i1=n;
    end;
    if i2>n
        i2=n;
    end;
    ex=a(i1);
    a(i1)=a(i2);
    a(i2)=ex;
    l2=distance(a,m,n);
    l=l2;
    dl=l2-l1;
    if dl>0 && exp(-dl*t)<rand()
        a=a0;
        l=l1;
    end;
end

function l=distance(a0,m,n)
    l=0;
    prev=a0(1);
    for k=2:n
        next=a0(k);
        l=l+m(prev,next);
        prev=next;
    end;
    l=l+m(prev,a0(1));
end
