TSP 模拟退火

TSP——模拟退火解法

都知道TSP是经典的NP问题，从一个点开始遍历所有点，不重复，求最短路径。

可以用枚举终点，跑流量为2的最小费用，图论来做，时间复杂度为费用流已经用到堆优化了。显然点，边较多将无法承受。

如果不要求精确解，使用模拟退火也是一个不错的选择。模型简单，转移很暴力。

先随机生成一些解，然后随机挑两个点，开始试探转移。

这里，几乎是按照退火算法模板写的了，有初始化，有状态转移，有接受准则。

clc, clear

sj0=load('sj.txt');

x=sj0(:,[::]);x=x(:);

y=sj0(:,[::]);y=y(:);

sj=[x y]; d1=[,];

sj=[d1;sj;d1]; sj=sj*pi/;

d=zeros();

for i=:

   for j=i+:

    d(i,j)=*acos(cos(sj(i,)-sj(j,))*cos(sj(i,))*cos(sj(j,))+sin(sj(i,))*sin(sj(j,)));

   end

end

d=d+d';

path=[];long=inf;



rand('state',sum(clock));  %初始化随机数发生器



for j=:  %求较好的初始解

    path0=[ +randperm(),]; temp=;

    for i=:

        temp=temp+d(path0(i),path0(i+));

    end

    if temp<long

        path=path0; long=temp;

    end

end



e = 0.1^;

L = ;

at = 0.999;

T = ;



for k = :L

    c = +floor(*rand(,));

    c = sort(c);

    c1 = c();

    c2 = c();

    df=d(path(c1-),path(c2))+d(path(c1),path(c2+))-d(path(c1-),path(c1))-d(path(c2),path(c2+));

    if df <

        path=[path(:c1-),path(c2:-:c1),path(c2+:)];

        long = long+df;

    elseif exp(-df/T)>rand

        path=[path(:c1-),path(c2:-:c1),path(c2+:)];

        long=long+df;

    end

    T = T*at;

    if T < e

        break;

    end

end



xx = sj(path,);

yy = sj(path,);

plot(xx,yy,'-*');

巴特西

TSP 模拟退火

TSP——模拟退火解法

最新文章

热门文章