#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