TSP之动态规划找最优解

动态规划解决TSP问题
    假设p0,p1,p2...pn-1是从p0到pn-1的最短路径，则p1,p2...pn-1也是最短路径。
    pi:点i
    d(i,v):从i经过点集合v所有点的最短路径长度
    c(i,j):从i到j的距离花费
    目的：求d(0,v)最短路径和长度
    v=空集， d(0,v)=0
    v不等于空集，d(0,v)=min{c(0,i)+d(i,v-{i})} i属于v

 

#include <windows.h>
#include <iostream>
#include <set>
#include "config.h"

using namespace std;
/*
    动态规划解决TSP问题
    假设p0,p1,p2...pn-1是从p0到pn-1的最短路径，则p1,p2...pn-1也是最短路径。
    pi:点i
	d(i,v):从i经过点集合v所有点的最短路径长度
	c(i,j):从i到j的距离花费
	目的：求d(0,v)最短路径和长度
	v=空集， d(0,v)=0
	v不等于空集，d(0,v)=min{c(0,i)+d(i,v-{i})} i属于v


*/
typedef struct _MyPoint
{
	double GetDistance(const _MyPoint& point)
	{
		int delta_x = abs(this->x-point.x);
		int delta_y = abs(this->y - point.y);
		return sqrt(delta_x*delta_x + delta_y*delta_y);
	}
	int x;
	int y;
	
}*LPMYPOINT;
std::vector<LPMYPOINT> points;
double cost[100][100];

double CalcShortestDis(int i, const std::set<int>& VPoints,std::vector<int>& path)  // d(i,v)
{
	if (VPoints.size() == 0)
	{
		return 0;
	}
	std::set<int>::iterator it = VPoints.begin();
	double tempmin = 9999999999.0;
	for (; it != VPoints.end(); ++it)
	{
		int nextpoint = *it;
		std::set<int> nextVPoints;
		nextVPoints.insert(VPoints.begin(), VPoints.end());
		nextVPoints.erase(nextpoint);
		std::vector<int> temppath;
		double dis = cost[i][nextpoint] + CalcShortestDis(nextpoint, nextVPoints, temppath);
		if (dis < tempmin)
		{
			path.clear();
			path.push_back(nextpoint);
			for (std::vector<int>::iterator tempIt = temppath.begin(); tempIt != temppath.end(); ++tempIt)
			{
				path.push_back(*tempIt);
			}
			tempmin = dis;
		}
	}
	return tempmin;
}
int main()
{
	int nStartTime = GetTickCount();
	memset(cost, 0x00, 100 * 100);
	int num = 0,i=0,j=0;
	num = atoi(getConfig("config", "num").c_str());
	
	char szTemp[10];
	while (i<num)
	{
		memset(szTemp,0x00,10);
		sprintf(szTemp,"p%d",i);
		std::vector<std::string> vec;
		Split(getConfig("points", szTemp), ",", vec);
		LPMYPOINT point = new _MyPoint();
		point->x = atoi(vec[0].c_str());
		point->y = atoi(vec[1].c_str());
		points.push_back(point);
		i++;
	}
	min = 0;
	for (i = 0; i < num; i++)
	{
		for (j = 0; j < num; j++)
		{
			cost[i][j] = points[i]->GetDistance(*points[j]);;
		}
	}
	
	/*for (i = 0; i < num-1; i++)
	{
		min += cost[i][i+1];
	}*/
	std::set<int> VPoints;
	for (i = 1; i < num; i++)
	{
		VPoints.insert(i);
	}
	std::vector<int> path;
	double dis = CalcShortestDis(0, VPoints, path);
	cout << "最短路径长度：" << dis << endl;
	cout <<"最短路径：" << endl;
	for (i = 0; i < path.size(); i++)
	{
		cout <<"p"<< path[i] << ",";
	}
	cout << endl;
	int nEndTime = GetTickCount();
	cout << "耗时：" << nEndTime - nStartTime << "ms"<< endl;

	for (i = 0; i < points.size(); i++)
	{
		delete points[i];
	}
	system("pause");
	return 0;
}

 

config配置文件中输入点数和点的x、y位置，截图如下：

 

工程代码下载：链接：https://pan.baidu.com/s/1O3nVpn_Z-3gQIljsNdXx-g 
提取码：6agh