wstsp.h

开发环境：Visual C++ .net2003 功能：利用禁忌搜索思想求解TSP问题。

#pragma once
#include <vector>

typedef struct _CityPoint
{
	FLOAT x;
	FLOAT y;
}CityPoint, *PCityPoint;

typedef std::vector<INT> CityOrderDef;

typedef struct stCityInfo
{
	INT	m_CityNum;
	CityOrderDef m_pCityOrder;	
	PCityPoint m_pCities;//按从0开始的顺序
public:
	stCityInfo()
	{
		m_CityNum = 0;
		m_pCityOrder.clear();
		m_pCities = NULL;
	}

	stCityInfo(INT _CityNum, PCityPoint _pCities, CityOrderDef _pCityOrder)
	{
		m_CityNum = _CityNum;
		m_pCityOrder = _pCityOrder;
		m_pCities = _pCities;
	}
}CityInfo, *PCityInfo;


typedef struct stTaboElement
{
	CityInfo m_CityInfo;
	FLOAT m_distance;

public:
	stTaboElement():m_distance(0.0),m_CityInfo(){}

}TableElement;
typedef std::vector<TableElement> TaboTable;
typedef TableElement CityRouter;

typedef struct stCityPeer
{
	INT i;
	INT j;

public:
	VOID SetCityPeer(stCityPeer p_CityPeer)
	{
		i = p_CityPeer.i;
		j = p_CityPeer.j;
	}
	BOOL EqualPeer(stCityPeer p_CityPeer)
	{
		if((i == p_CityPeer.i && j == p_CityPeer.j) &&
			(i == p_CityPeer.j && j == p_CityPeer.i) ) return TRUE;

		return FALSE;
	}
}CityPeer;

typedef std::vector<CityPeer> TaboTableCityPeer;
typedef struct stCityPeerInfo
{
	CityPeer m_CityPeer;
	FLOAT m_Distance;
}CityPeerInfo;
typedef std::vector<CityPeerInfo> CityPeerInfoVector;

class WSTSP
{
public:
	WSTSP(void);
	~WSTSP(void);

public:
	static BOOL Show(CityOrderDef _Order);


public:
	//返回的是最佳路径在Vector中的编号
	static INT GetBestRoute(TaboTable p_TaboTable);
	static INT GetBestRoute(CityPeerInfoVector p_CityPeerInfoVector);

	static INT GetRightIndex_Greedy(CityOrderDef _CityOrder, INT _CurCityNum);
	static INT GetLeftIndex_Greedy(CityOrderDef _CityOrder, INT _CurCityNum);
	static INT GetCityIndex(CityOrderDef _CityOrder, INT _CurCityNum);

	static BOOL GetShortestCities(CityInfo &_CityInfo, INT _City, INT *_CitySerial, INT _ShortestCityNum = 3);
	static BOOL MakeCityDistStyle(CityInfo &_CityInfo, INT **_CitySerial, INT _ShortestCityNum = 3);//已经定义好_CitySerial
	static BOOL AdjustCityOrder(CityInfo &_CityInfo);
	static BOOL MakeStyleCityOrder(CityInfo &_CityInfo, INT **_CitySerial, INT _ShortestCityNum = 3);

	static FLOAT CityDistance(FLOAT _Ax, FLOAT _Ay, FLOAT _Bx, FLOAT _By);
	static FLOAT CityDistance(CityPoint _A, CityPoint _B);
	static FLOAT TSPTotalDistance(PCityInfo _pCityInfo);

	static BOOL ReadCityInfoFromFile(PCHAR _FileName, CityInfo &_CityInfo);
	static BOOL GenCityInfoToFile(PCHAR _FileName, INT _CityNum);

	static VOID SwapValues(INT & _A, INT & _B);
	static VOID GenRandCityOrder(CityInfo &_CityInfo);
	static VOID GenRandCityOrder(CityOrderDef &_CityOrder);
	static VOID SwapTwoCity(CityOrderDef &_CityOrder);
	static VOID SwapTwoCity(CityOrderDef &_CityOrder, INT i, INT j);

	static VOID ReverseSubOrder(CityOrderDef &_CityOrder);
	static VOID ReverseSubOrder(INT _Begin, INT _End, CityOrderDef & _CityOrder);
	static VOID RearrangeSubOrder(CityOrderDef &_CityOrder);
	static VOID RearrangeSubOrder(INT _Begin, INT _End, CityOrderDef & _CityOrder);
	static BOOL EqualOrders(CityOrderDef _A, CityOrderDef _B);
	static BOOL CrossSubOrder(CityOrderDef _CityOrderPa, CityOrderDef _CityOrderPb, CityOrderDef & _CityOrderSa, CityOrderDef & _CityOrderSb);   
	static BOOL CrossSubOrder(INT _Begin, INT _End, CityOrderDef _CityOrderPa, CityOrderDef _CityOrderPb, CityOrderDef & _CityOrderSa, CityOrderDef & _CityOrderSb); 
};