碎纸片还原MATLAB实现.zip_tsp碎纸片_碎纸TSP_碎纸拼接_碎纸片_碎纸片拼接

%% 对附件2进行TSP求解 %% 求解经典城市TSP问题 % 采用ant cycle system 模型 clear db2 = ImgStore('I:\教育\我的作品\数模\2013国赛赛题\B\附件2'); alpha = 0.5; % 信息素重要程度 beta = 0.5; % 启发函数重要程度 rho = 0.3; % 信息素挥发律 D = distance(db2); % 城市距离坐标矩阵 m = 19; % 城市数量 Q = 100; % Q值 n = 19; % 蚂蚁数量 iter = 1; % 迭代代数初值 itermax = 100; % 迭代代数终值 Table = zeros(n,m); % 路径记录表 SolutionSpace = 1:m; % 解空间 Tau = ones(m,n); % 初始信息素矩阵 Eta = 1./D; Route_best = zeros(itermax,m); % 各代最佳路径 Length_best = zeros(itermax,1); % 各代最佳路径距离 Length_ave = zeros(itermax,1); % 各代路径的平均长度 %% 迭代寻优 while iter <= itermax % 每个城市都有一只蚂蚁 start = randperm(n); % 初始路径记录 Table(:,1) = start; % 逐个蚂蚁路径选择,难道路径都确定了吗,是的，更新函数为下一次循环服务 for i = 1:n % 逐个城市路径路径选择 for j = 2:m % 禁忌表，但应该可以更优化 tabu = Table(i,1:(j-1)); % 待访问的城市集合 allow = SolutionSpace(~ismember(SolutionSpace,tabu)); % 概率更新，十分巧妙 P = allow; for k = 1:length(allow) P(k) = Tau(tabu(end),allow(k)).^alpha * Eta(tabu(end),allow(k))^beta; end P = P/sum(P); % 轮盘赌确定下一个城市 Pc = cumsum(P); target_index = find(Pc>rand); target = allow(target_index(1)); Table(i,j) = target; end end % 计算路径 Length = zeros(n,1); for i = 1:n Route = Table(i,:); for j = 1:(n-1) Length(i) = Length(i)+D(Route(j),Route(j+1)); end end % 计算最短路径和平均路径距离 if iter == 1 [min_Length,min_index] = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length); Route_best(iter,:) = Table(min_index,:); else [min_Length,min_index] = min(Length); Length_best(iter) = min(min_Length,Length_best(iter-1)); Length_ave(iter) = mean(Length); if Length_best(iter) == min_Length; Route_best(iter,:) = Table(min_index,:); else Route_best(iter,:) = Route_best(iter-1,:); end end % 更新信息素 Delta_Tau = zeros(m,m); for i = 1:n for j = 1:m-1 Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q./Length(i); end Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,n)) + Q./Length(i); end Tau = (1-rho)*Tau+Delta_Tau; iter = iter+1; Table = zeros(n,m); fprintf('第%d代运行结束\n',iter-1); end disp(['最短路径为:' num2str(Route_best(end,:))]); fprintf('最短距离为为%s',Length_best(end)); fprintf('平均距离为为%s',Length_ave(end)); ProcessView; figure(2); Length = Route_best(end,:); show(Length,db2);