(Kỹ thuật nhánh cận) Bài toán người du lịch (Travelling Salesman)

Sưu tầm:


Cho n thành phố đánh số từ 1 đến n và m tuyến giao thông 2 chiều được cho bởi mảng C cấp nxn.
Ở đây c[i,j]= c[j,i] = chi phí đường đi trực tiếp giữa 2 thành phố i và j.


Giả thiết c[i,i] = 0 với mọi i và c[i,j] = ( vô cùng )  nếu không có đường đi trực tiếp giữa thành phố i và j.


Một người du lịch xuất phát từ  thành phố 1, muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi đúng 1 lần và cuối cùng trở lại 1. Hãy chỉ cho người đó hành trình với chi phí  ít nhất.


*Solve:


Hành trình cần tìm có dạng  x[1... n+1] trong đó x[1] = x[n+1] = 1 ở đây giữa thành phố x[i] và x[i+1] phải có đường đi trực tiếp ( c[i,j] khác  vô cùng) và ngoại trừ thành phố 1, không thành phố nào được lặp lại 2 lần. Có nghĩa là dãy x[1..n] lập thành 1 hoán vị của (1,n).


Duyệt quay lui x[2] có thể chọn một trong các thành phố x[1] có đường đi tới trực tiếp, với mỗi cách thử chọn x[2], x[3] có thể chọn 1 trong các thành phố mà x[2] có đường đi tới trực tiếp  trừ x[1]. Tổng quát, x[i] có thể chọn 1 trong các thành phố chưa đi qua mà từ x[i-1] có đường đi tới trực tiếp ( 1<=i<=n).


Input:


*Dòng 1:Chứa sô thành phố n ( 1<=n <= 100) và số tuyến đường m trong mạng lưới giao thông.


* m dòng tiếp theo mỗi dòng ghi số liệu 2 thành phố có đường đi trực tiếp và chi phí trên quãng đường đó ( chi phí này nhỏ hơn 10000).


                             

            KY THUAT NHANH CAN CHO BAI TOAN NGUOI DU LICH
            
program Travelling Salesman;
const
        InputFile = 'TOURIST.INP';
        OutputFile = 'TOURIST.OUT';
        max = 100;
        maxE = 10000;
        maxC = max*maxE; {+oo}
        
var
        c: array[1...max] of Integer; {Ma tran chi phi}
        
        x, BestWay: array[1...max+1] of Integer;
        { x de thu cac kha nang, BestWay de ghi nhan nghiem}
        
        t : array[1...max+1] of Integer;
        { t[i] de luu chi phi di tu x[1] den x[i]}
        
        Free : array[1...max] of Boolean;
        {Free de danh dau, Free[i] = TRUE  neu chua di qua thanh pho i}
        
        m,n: Integer;
        Minspending : Integer; {Chi phi hanh trinh toi uu}
        dmin : Integer; {Chi phi Min trong cac tuyen duong}
        
procedure Enter;

var
    i,j,k : Integer;
    f: Text;
    
begin
    Assign( f,InputFile); Reset(f);
    ReadLn(f,n,m);
    for i:= 1 to n do { Khoi tao mang chi phi ban dau}
       for j:= 1 to n do
         if i= j then c[i,j] := 0
         else c[i,j] = maxC;
    for k:= 1 to m do
       begin
          ReadLn( f,i,j,c[i,j]);
          c[i.j] := c[j,i]; 
          {Chi phi nhu nhau tren ca 2 chieu}
       end;
       Close(f);
end;

procedure Init; {Khoi tao }

begin
    FillChare ( Free,n,TRUE);
    Free[1] := False; {Cac thanh pho la chua di qua ngoai tru 1}
    x[1] := 1; {Xuat phat tu thanh pho 1}
    t[1] := 0; {Chi phi xuat phat tu thanh pho 1 bang 0}
    MinSpending := maxC; {+oo}
    
end;

procedure Attempt( i: Integer); {Thu cac cach chon x[i] }

var
    j: Integer;

begin
    for j:= 2 to n do { Thu cac thanh pho tu 2 den n}
       if Free[j] then {Neu gap thanh pho chua di qua}
       begin
             x[i] := j; {thu di}
             t[i] = t[i-1] + c[x[i-1],j];
             {Chi phi := Chi phi nuoc truoc + Chi phi duong di truc tiep}
             
             if( t[i] < Minspending) then
             {Hien nhien neu co dk nay nay thi c[x[i-1],j] < maxC}
             
                 if i = n 
                    if( t[n] + c[x[n],1]) < MInspending then
                      
                      {Tu x[n] quay lai 1 van ton it chi phi hon truoc}
                      begin
                      
                       {Bat dau cap nhat}
                       BestWay := x;
                       Minspending := t[n] + x[c[n],1];
                  else
                     if( t[i] + dmin*(n-i+1) < Minspending)
               { tu i ta con phai di tiep n-i+1 tuyen duong nua}
               { dmin la chi phi nho nhat trong cac chang duong}
               { Neu tong tren >= Minspending thi khong can lam gi nua}
                         
                         begin
                             
                             Free[j] := FALSE; 
                        { Danh dau thanh pho vua thu qua}
                             Attempt(i+1); {Tim cac kha nang chon x[i+1]}
                             Free[j] := TRUE; {Bo dau danh chon};
                             
                          end;
                          
                      end;
                      
end;