用动态规划法解决TSP问题

本压缩文档包含三个文件：用动态规划法解决TSP问题可执行源代码，word文档报告，实验测试数据

#include
#include
#include
using namespace std;
int s;
int N;//城市个数
int k;
int f;
int path[20];
int init_point;
int NODE[20][3];
double COST[20][20];//两个城市的距离
double dis[1048577][20];//2^20=1048576 表示出发点到S集合是否已经访问过

double go（int sint init）
{
	k=0;
	path[0]=0;
	path[N]=0;
	k++;
    if（dis[s][init]!=-1） return dis[s][init];//去重
    if（s==（1<<（N-1））） 	  return COST[N-1][init];//只有最后一个点返回
    double minlen=100000;
    for（int i=0;i    {
        if（s&（1<        {
            if（go（s&（~（1<            {
                minlen=go（s&（~（1<            }
        }
    }
    return dis[s][init]=minlen;
}

int main（）
{
	cout<<“请输入测试数目“<    int T;
    cin>>T;
    while（T--）//测试样例数
    {
    	cout<<“请输入城市个数“<        cin>>N;
        cout<<“请输入城市坐标：“<		for（int i=0;i		{
			for（int j=0;j<3;j++）
			{
				cin>>NODE[i][j];
			}
		}
		for（int i=0;i		{
			for（int j=0;j			{
				COST[i][j]=sqrt（pow（NODE[i][1]-NODE[j][1]2）+pow（NODE[i][2]-NODE[j][2]2））;
			}
		}

        for（int i=0;i            for（int j=0;j                dis[i][j]=-1;//去重数组
        init_point=0;
        s=0;
        for（int i=1;i            s=s|（1<        double distance=go（sinit_point）;
        cout<<“最短路径为：“<        cout<
    }
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     351096  2018-07-01 15:14  15计2-2015551239-王维-用动态规划法解TSP问题\15计2-2015551239-王维-用动态规划法解TSP问题.docx

     文件       2136  2015-05-07 14:17  15计2-2015551239-王维-用动态规划法解TSP问题\data.txt

     文件       1651  2018-07-01 15:03  15计2-2015551239-王维-用动态规划法解TSP问题\动态规划法解tsp问题.cpp

     文件    1954384  2018-07-01 15:03  15计2-2015551239-王维-用动态规划法解TSP问题\动态规划法解tsp问题.exe

     目录          0  2018-07-12 10:27  15计2-2015551239-王维-用动态规划法解TSP问题

----------- ---------  ---------- -----  ----

              2309267                    5