基于旅行商模型的碎紙片拼接複原

對于2013 的碎片拼接問題的附件一與附件二，基于旅行商算法的碎片拼接問題，尋找最優哈密頓圈

先利用matlab計算出他的邊權矩陣，再用lingo規劃模型，求出最優的哈密頓圈，最終可以得到正确的排序，利用人工幹預，找到 初末位置，即可還原。

matlab部分代碼（求邊權矩陣）：

clear
close all
clc
dirname='C:\Users\Grin\Desktop\數學模組化各種文檔\2013年賽題\B\附件1';
files=dir([dirname,'\*.bmp']);
Num_file=numel(files);
I=cell(1,Num_file)
for k = 1:19

I{k} = imread([dirname '\' files(k).name]);
end

for k=1:19
    J(k)=graythresh(I{k});
    P{k}=im2bw(I{k},J(k));
end
for k=1:19
    [le,n]=size(P{k});
    left{k}=P{k}(:,1);
    right{k}=P{k}(:,n);
end
for k=1:19
    for n=1:19
         if n==k
       
        else
    a(n,k)=sum(abs(left{n}-right{k}));
         end
    end
end

           

lingo部分代碼：

model:

sets:

cities/1..19/:u;

link(cities,cities):

distance,x;endsets

data:

distance=

    ;在此輸入matlab計算的邊權值矩陣

enddata

[email protected](cities);

[email protected](link(i,j)|i#ne#j:distance(i,j)*x(i,j));

@for(cities(i):

@sum(cities(j)|j#ne#i:x(j,i))=1;

@sum(cities(j)|j#ne#i:x(i,j))=1;

@for(cities(j)|j#gt#1#and#j#ne#i:

u(j)>=u(i)+x(i,j)

-(n-2)*(1-x(i,j))+(n-3)*x(j,i);

);

);

@for(link:@bin(x));

@for(cities(i)|i#gt#1:

u(i)<=n-1-(n-2)*x(1,i);

u(i)>=1+(n-2)*x(i,1););

end
           

碎片的複原代碼：

circle=%輸入lingo計算出的排序
sum2;
for k=1:19
  
    circle2(k)=circle(20-k);
end
circle2

for i=1:19
begin=72*(i-1)+1;
end_f=72*i;
num=circle2(i);
all_file_new(:,begin:end_f)=I{num};
end
figure
show_file_new=all_file_new(1:1980,:);
imshow(show_file_new);