旅行商问题TSP三种解决算法 基于C++的编程

旅行商问题是一个经典的问题，此代码用三种方法（枚举法，回溯法，贪心法），并可以对这三种方法进行比较

//------------------------------------- tsp.cpp文件--------------------------------------------------   
#include “AdjtwGraph.h“   
#include    
#include    
#include    
#include    
#include    
using namespace std;  
ofstream fout（“out.txt“）;  
int N;  
AdjTWGraph g;  
struct Node      
 {   int currentIndex;  
     int level;  
     Node * previous;  
     Node（int L = 0 int V = 0 Node *p = NULL）:level（L）currentIndex（V） previous（p） {}  
};  
class Tspbase  
{  
  protected:      
    vector currentPath;  
    vector bestPath;  
    int cv;  
    int bestV;  
    Node * root;  
  
    void EnumImplicit（int k）;  

	void BackTrackImplicit（int k）;  
  
    bool Valid（Node *pint v）  //   
         {  bool flag = true;  
            for（Node *r = p; r->level > 0 && v; r = r->previous）  flag = r->currentIndex !=v;  
            return flag;  
        }  
    void StoreX（Node * p） //   
    {
		for（Node *r = p; r->level >0 ; r = r->previous ）  
		{       
				currentPath[r->level-1] = r->currentIndex;    }  
        }  
  void Print（）;  
  public:  
     Tspbase（）{currentPath.resize（N）;    bestPath.resize（N）;    }  
    ~Tspbase（）{currentPath.resize（0）;bestPath.resize（0）;}  
  
    void TspEnumImplicit（）;  
    void TspBackTrackImplicit（）; 
	void TspGreedy（）;     
        
    void DataClear（bool flag）  
     {   currentPath.resize（N）;        bestPath.resize（N）;  
         if（flag）        { Node * p=root*q;  
                      while（p!=NULL） {q=p->previous; delete p; p=q;}      
        }  
    }  
};  
 
 
void Tspbase::TspEnumImplicit（）  //         枚举隐式   
 {   
	fout<<“TspEnumImplicit ...“<    cv=0;
    bestV=10000;  
    for（int i=0;i		currentPath[i]=i;  

    EnumImplicit（1）;  
    Print（）;  
}  
void Tspbase::EnumImplicit（int k）  
 {    if（k == N）  
    {    if（（cv + g.GetWeight（currentPath[N-1]0）） < bestV）  
         {  
            bestV = cv + g.GetWeight（currentPath[N-1]0）;  
           for（int i = 0; i < N; i++）  
              bestPath[i] = currentPath[i];  
        }          
    }  
    else  
       for（int j = k; j < N; j++）  
         {    swap（currentPath[k]currentPath[j]）;  
            cv += g.GetWeight（currentPath[k-1]currentPath[k]）;  
            EnumImplicit（k+1）;  
            cv -= g.GetWeight（currentPath[k-1]currentPath[k]）;  
           swap（currentPath[k]currentPath[j]）;  
       }  
}  

void Tspbase::TspGreedy（）  //TSP贪心算法   
 {    
	fout<<“TspGreedy ........“<    bestV = 0;       
    vector NEAR（N）; //    
    NEAR[0] = -1;  
    for （int i = 1; i < N; i++）  
       NEAR[i] = 0;  

    bestPath[0] = 1;  
    int t;  
    for （int s = 1; s < N; s++）  
    {  
      int j = 1;  
      while （j < N && NEAR[j] < 0）   
          j++;  
      int K = j;  
      for （int k = j + 1; k < N; k++）  
         if （NEAR[k] >= 0

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-12-12 10:46  tsp\
     文件        2673  2012-11-28 09:55  tsp\AdjtwGraph.h
     目录           0  2012-12-12 10:46  tsp\Debug\
     文件      585812  2012-12-12 10:46  tsp\Debug\tsp.exe
     文件      830248  2012-12-12 10:46  tsp\Debug\tsp.ilk
     文件      393751  2012-12-12 10:46  tsp\Debug\tsp.obj
     文件     3218128  2012-12-12 10:21  tsp\Debug\tsp.pch
     文件     1156096  2012-12-12 10:46  tsp\Debug\tsp.pdb
     文件       99328  2012-12-12 10:46  tsp\Debug\vc60.idb
     文件      151552  2012-12-12 10:46  tsp\Debug\vc60.pdb
     文件         198  2012-11-28 10:47  tsp\data.txt
     文件         289  2012-12-12 10:46  tsp\out.txt
     文件        5925  2012-12-12 10:46  tsp\tsp.cpp
     文件        4313  2012-11-28 10:05  tsp\tsp.dsp
     文件         512  2012-11-28 09:40  tsp\tsp.dsw
     文件       50176  2012-12-12 10:46  tsp\tsp.ncb
     文件       53760  2012-12-12 10:46  tsp\tsp.opt
     文件        1260  2012-12-12 10:46  tsp\tsp.plg