tspts.h

用禁忌算法求解tsp（旅行商问题）具有速度快

//Author: yinhui
//Date  : 2007.06.14

#include <vector>
#include <list>

#define MAXCITYNUM 100
#define MAXTABUCOUNT 20    //每个元素被禁忌的时间
typedef std::vector<int> vecCityRouter;


typedef struct  
{
	double length;    //禁忌长度
	int count;    //禁忌最大次数，超过后就执行特赦
}TabuListItem;

typedef std::list<TabuListItem> listTabuList;

//城市坐标类
class Coordinate
{
public:
	Coordinate() {m_fX = 0.0; m_fY = 0.0;}
	Coordinate(float x, float y) {m_fX = x; m_fY = y;}

	void Set(float x, float y) {m_fX = x; m_fY = y;}

public:
	float m_fX;
	float m_fY;
};

//城市间距离类
class Distance
{
public:
	Distance() {m_nFromCity = 1; m_nEndCity = 1; m_fDist = 0.0;}
	
	void Set(int fCity, int eCity, float dist)
	{
		m_nFromCity = fCity;
		m_nEndCity = eCity;
		m_fDist = dist;
	}

public:
	int m_nFromCity;
	int m_nEndCity;
	float m_fDist;
};

//TSP问题中的城市类
class City
{
public:
	City() {m_nIndex = 1; m_corCity.Set(0.0, 0.0);}
	City(int idx, float x, float y) : m_corCity(x, y) {m_nIndex = idx;}

public:
	int m_nIndex;    //城市编号
	Coordinate m_corCity;
};

typedef std::vector<City> VecCity;
typedef std::vector<Distance> VecDistance;
//
class TabuSearch
{
public:
	TabuSearch() {}

	void Init();    //系统初始化
	bool IsInnerCycStop();    //判断内循环是否结束，结束返回true，否则返回false
	bool IsOuterCycStop();    //判断外循环是否结束，结束返回true，否则返回false
	vecCityRouter NextSolution();    //随机选择邻域中一个解作为下一个测试解
    //void ComputeStartTemper();    //计算初始温度
	//void DecreaseTemper();    //温度下降方式
    void CreateInitSolution(vecCityRouter& initRouter);    //生成初始路由1->2->...->n->1
	double ComputeDistance(City& fCity, City& eCity, Distance& cityDist);    //计算两城市间距离
	void ComputeTotalDistace();    //计算所有城市间距离
	double FindDistance(int fIndex, int eIndex);    //根据城市编号查城市间距离
	double ComputeRouterDistance(vecCityRouter& curCityRou);    //计算路由总长度
	void ObtainParams(int nTabuLength, int nCandSize, int nSameCount, int nIterCount,
		              VecCity vCitys, int nCityNum);
	float DoOneSearch(float t);
	float GetNowDistance();
//	void TSPAnneal(CListBox *pLB);
	void TSPTabuSearch(CListBox *pLB);

public:
	int m_nTabuLength, m_nCandSize, m_nSameCount, m_nIterCount, m_nCityNum;
	vecCityRouter m_crRouter;
	VecDistance m_vecDistance;
	VecCity m_vecCitys;
	vecCityRouter m_vecRouter;
};