论坛 › 算法类综合讨论版 › Matlab写的回溯法解TSP问题

tankadozmy 发表于 2011-1-15 10:24

Matlab写的回溯法解TSP问题

function tsp_backtrace(i)
global d;
global x;
global n;
global m_x;
global m_val;
if i>n
val=0;
for j=1:n-1
val=val+d(x(j),x(j+1));
end
val=val+d(x(n),x(1));
if m_val>val
m_val=val;
m_x=x;
end
else
for j=i:n
t=x(i); x(i)=x(j); x(j)=t;
tsp_backtrace(i+1);
t=x(i); x(i)=x(j); x(j)=t;
tsp_backtrace(i+1);
end
end
end下面是个小例子。。。
global d;
global x;
global n;
global m_x;
global m_val;
d=[0 1 3 5;
3 0 2 1;
8 3 0 5;
1 7 3 0];
x=1:4;
n=4;
m_x=x;
m_val=inf;
tsp_backtrace(1);

tankadozmy 发表于 2011-1-15 10:25

插入代码后缩进的格式全不见了。。。。不怨我哈~~~~

fif1fds00712 发表于 2011-1-15 10:53

过来看看！

chenyuanyuan 发表于 2011-1-15 16:35

以前做过 禁忌搜索

nutswang 发表于 2011-1-15 20:55

练练手不错。不过对于规模稍微大点的问题，精确算法的时间消耗就相当严重了，即使使用c。

李——建辉 发表于 2012-1-21 20:19

尽力而为，无愧于心         103774

查看完整版本: Matlab写的回溯法解TSP问题