动态规划求解TSP圈

痛定思痛。 2022-04-25 09:30 231阅读 0赞

求解思路：

**动态规划的方法的最大难点就在于初始变量的确定，选择合适的初始变量才能更好的运用动态规划的方式解决问题。我在这里定义的变量就是d(i,S),设s出发点，其中i是一个点,而S是点的集合，这个变量的意思就是从i出发，经过S中的所有点一次且仅一次且回到出发点s的最小距离。当S为空时，就表示i到起始点s的权值。**

所以有如下的动态规划方程：

d(i,S)=min\{Cij+d(j,S-j)\}(j属于S）

d(i,S)=Cis（i!=s且S=NULL）

Cij表示weight(i,j)

**这里实现我用的是递归的思想，那个每次从集合中去除点的操作，我用了一个vector，然后从最后的点开始循环，每次把要去除的点和最后的点交换下，在pop掉，递归调用后再把之前的用push\_back加上，这样也不会影响前面的点的顺序。**

所以通过上面的方程我们就能求得最小TSP圈的权值了。

**然后是路径的求取：**

**在这里设定一个二维数组M\[i\]\[S\],S表示一个集合，这个表示从i到集合S中选取的最优点，这也就是路径上的一点。为了表示集合的独特性，可以用集合中的点3次方之和来表示，也可以用2的几次方之和等等，只要保证不重复即可。**

**  然后再用求出来的点进行下一次的求解，如果上一次的解是j，则下一次为M\[j\]\[S-j\],就这样求下去，循环顶点个数减一次就可以了**

int linkedDgraph1::TSP_dp_d(int i,int ii,vector<int> vec,int **res)
    {
    	int temp = 1000;
    	int index = 0;
    	int sum=0;
    	if (vec.size() == 0)
    		return getWeight(i, ii);
    	for (int j = vec.size()-1; j >=0; j--)
    	{
    		int k = vec[j];
    		//index = k;
    		sum += pow(k,3);
    		vec[j] = vec[vec.size() - 1];
    		vec[vec.size() - 1] = k;
    		vec.pop_back();
    		int dis = getWeight(i, k) + TSP_dp_d(k,ii, vec,res);
    		if (dis < temp)
    		{
    			temp = dis;
    			index = k;
    		}
    		vec.push_back(k); 
    	}
    	res[i][sum] = index;
    	//precursor[index] = i;
    	return temp;
    }

void linkedDgraph1::TSP_dp(int i,int** result)
    {
    	vector<int> vec(verticeNumber - 1, 0);
    	int count = 0,sum=0;
    	for (int j = 0; j < verticeNumber; j++)//初始化数组
    	{
    		if (i != point[j])
    		{
    			vec[count] = point[j];
    			sum += pow(point[j], 3);
    			count++;
    		}
    	}
    	cout<<"最短路径为： "<<TSP_dp_d(i,i,vec,result)<<endl;
    	int temp=i;
    	// temp = result[1][54];
    	cout << i << " ";
    	for (int i = 0; i < verticeNumber-1; i++)
    	{
    		int res = result[temp][sum];
    		cout << res << " ";
    		temp = res;
    		sum = sum - pow(res, 3);
    	}
    	cout << i << " ";
    }

示例结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjQ3NTQ0_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjQ3NTQ0_size_16_color_FFFFFF_t_70]: /images/20220125/ff1a0b9d5474456d843f943150b240e5.png