分支定界求TSP问题_分支定界法_分支界定法求tsp问题_分支定界_源码

% 分支定界法求最短路 % 使用智能算法求出一个可行较优解 clear clc % 数据输入 position = [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; 3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756; 2788 1491;2381 1676;2648 1328;3715 1678;3918 2179;4061 2370; 3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367; 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975]; [m,n] = size(position); D = zeros(m); for i = 1:m for j = 1:m if i == j D(i,j) = 0; else D(i,j) = sqrt((position(i,1)-position(j,1))^2+(position(i,2)-position(j,2))^2); end end end global gen; global maxgen; maxgen = 1000; [record,track] = delimit(position,D); [~,index] = min(record); drawpath(track(index,:),position); hold on xlabel('x轴') ylabel('y轴') title('最短路径') outputpath(track(index,:)) figure hold on plot(1:maxgen,record); xlabel('迭代次数'); ylabel('距离'); title('优化过程'); disp(['第一个解的距离为：',num2str(pathlength2(D,track(index,:)))]); load('bestChrom.mat') % 分支界定法求最优解 solution1 = track(index,:); solution2 = track(index,:); temp = solution2; len = length(solution1); for i = len:-1:2 flag = 1; while flag == 1 for j = 2:i-1 thing = solution2; thing = insert2(i,j,thing); if pathlength(D,thing) < pathlength(D,temp) temp = thing; end end if temp == solution2; flag = 0; end solution2 = temp; end end temp = solution2; len = length(solution1); for i = len:-1:2 flag = 1; while flag == 1 for j = 2:i-1 thing = solution2; thing = insert2(i,j,thing); if pathlength(D,thing) < pathlength(D,temp) temp = thing; end end if temp == solution2; flag = 0; end solution2 = temp; end end drawpath(solution2,position); disp('经分支界定法求得的最短路径为：') outputpath(solution2); disp(['解的距离为：',num2str(pathlength2(D,solution2))]);