分支算法旅行商问题.cpp

算法设计与分析的经典程序

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int n = 5;
const int map[n][n] = {{0,2,3,0,7},
                      {2,0,5,6,5},
                       {3,5,0,8,2},
                       {0,6,8,0,9},
                       {7,5,2,9,0}};

const int NoEdge = 0;
class MinHeapNode
{public:
       int lcost,cc,rcost, s,*x;
};
class LessThan
{public:
       bool operator()(const MinHeapNode& n1, const MinHeapNode& n2)
       {  return n1.lcost < n2.lcost;   
       }
};
class MinHeap
{public:
       vector< MinHeapNode > _minHeap;
       void Sort() 
	   { stable_sort(_minHeap.begin(), _minHeap.end(), LessThan()); }
       void Insert(MinHeapNode &n)		
	   {   _minHeap.push_back(n); 
		short(); 
	   }
       int DeleteMin(MinHeapNode &n)		
	   {   if(_minHeap.empty()) return 0;
		   n = _minHeap.front(); 
		   _minHeap.erase(_minHeap.begin());
		   return 1;
	   }
};
class TSP
{public:
       TSP(int n, int *a);
       ~TSP(); void DoTSP();
       friend ostream& operator<<(ostream &os, TSP &tsp);
       int n,**a, cc, bestc, *v;
};
TSP::TSP(int n, int *a)		
{  this->n = n;
    this->a = new int*[n];
    for(int i=0; i<n; i++)
    {  this->a[i] = new int[n];
        for(int j=0; j<n; j++)
        { this->a[i][j] = *(a+i*n+j);
     }
 }
}
TSP::~TSP()			
{    for(int i=0; i<n; i++)
    {    delete []a[i];
    }
    delete []a;
}
void TSP::DoTSP()
{ MinHeap H;
    int *MinOut = new int[n];
	int MinSum=0;	
    for(int i=0; i<n; i++)
    {  int Min = NoEdge;
        for(int j=0; j<n; j++)
        { if( a[i][j] != NoEdge && ( a[i][j] < Min || Min == NoEdge ))
            { Min = a[i][j];
            }
        }
        if( Min == NoEdge )
        { bestc = NoEdge;		
            return;
        }
        MinOut[i] = Min;
        MinSum += Min;
    }
    MinHeapNode E;
    E.x = new int[n];
    for(i=0; i<n; i++)
    {   E.x[i] = i;
    } 
    E.s = 0;
    E.cc = 0;
    E.rcost = MinSum;
    bestc = NoEdge;
 while(E.s < n-1)		
    {  if(E.s == n-2)		
	{ if(a[E.x[n-2]][E.x[n-1]] != NoEdge && 
               a[E.x[n-1]][0] != NoEdge &&
               (E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][0] < bestc || bestc == NoEdge ))
       		{ bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][0];
                E.cc = bestc;
                E.lcost = bestc;
                E.s++;
                H.Insert(E);
            }
            else
            {elete []E.x;		
         }
        }
        else
        { for(int i=E.s+1; i<n; i++)
            { if(a[E.x[E.s]][E.x[i]] != NoEdge)
                { int cc = E.cc + a[E.x[E.s]][E.x[i]];
            int rcost = E.rcost - MinOut[E.x[E.s]];
           int b = cc + rcost;
             if( b < bestc || bestc == NoEdge )
            {MinHeapNode N;
             N.x = new int[n];
               for(int j=0; j<n; j++)
                { N.x[j] = E.x[j];
                 }
                  N.x[E.s+1] = E.x[i];
                  N.x[i] = E.x[E.s+1];
                  N.cc = cc;
                  N.s = E.s + 1;
                  N.lcost = b;
                  N.rcost = rcost;
                  H.Insert(N);
               }
             }
           }
            delete []E.x;
        }
        if(!H.DeleteMin(E))
        {    break;
        }
    }
    if( bestc == NoEdge ) return;		
      v = new int[n];
    for(i=0; i<n; i++)
    {  v[i] = E.x[i];
    }
    while(true)
    {  delete []E.x;
        if(!H.DeleteMin(E))
        {  break;
 }
}
ostream& operator<<(ostream &os, TSP &tsp)
    for(int i=0; i<tsp.n; i++)
    {  for(int j=0; j<tsp.n; j++)
        {  cout << tsp.a[i][j] <<"   ";
        }
        cout << endl;
    }
    return os;
}
int main(int argc, char *argv[])
{  TSP tsp(n,(int *)map);
    tsp.DoTSP(); 
    cout << "最小路径和为：" << tsp.bestc << endl;
    cout << "最小路径如下：" << endl;
    for(int i=0; i<n; i++)
    {  cout << tsp.v[i] << '\t';
    }
    cout << "0" << endl;
    return EXIT_SUCCESS;
}