動的計画法を用いて旅行者問題(TSP)を解くC言語実現(一)
4513 ワード
あるセールスマンは都市v 1から出発し、他の都市v 2,v 3,...,v 6を1回ずつ1回だけ訪問し、最後にv 1に戻る.Dは各都市間の距離行列である.
質問:このセールスマンはどのようにルートを選択して、総行程を最も短くすることができますか?
D= 0 10 20 30 40 50
12 0 18 30 25 21
23 19 0 5 10 15
34 32 4 0 8 16
45 27 11 10 0 18
56 22 16 20 12 0
問題分析:n個の都市を1,2,...,n.与えられた集合Sに対して{2,3,4,...n}と要素kがSに属し、C(S,k)は都市1から出発し、Sの中で各都市をちょうど1回遍歴し、最後に都市kでの最適費用を終了する.
すると、Sに1つの要素kしかない場合、C(S,k)=D[1][k];
Sに複数の要素がある場合、C(S,k)=
この方程式の解は、所与の大きさの全ての集合S及びS中の可能な各要素kに対して、C(S,k)の値を計算することを要求する.
Sが{2,3,4,...n}に等しい場合、C(S,k)の値がSに属する任意の要素kに対して計算によって得られた場合、最適なループの最も費用は
アルゴリズム複雑度解析:計算に必要な加算と比較の回数はO(n^2*2^n)に等しい
空間複雑度:O(n*2^n)
アルゴリズムの改善:集合操作を改善することによって比較回数を低減し、バイナリを利用して集合を表す.集合Sにおける元素kの比較回数が1であるか否かを決定し、時間的複雑度をO(n 2^n)に低減する
#include
#include
#include
#include
#include
#define MAX_N 10
int mypow(int x, int y)
{
return (int)pow((double)x,(double)y);
}
struct path
{
int current;
int cost;
long set;//2 bits for vector
//struct path *lastNode;
struct path *lastNode;
struct path *next;
};
struct path *D[MAX_N];
/* ， 2
* n ， n 1 n ， 。
* k 1 ， k ， 0 。
*/
/* i set 。
* ， set
* 1 ， 0
*/
int inSet(int i, int set)
{
if((mypow(2,i-1)&set)>0)
return 1;
else
return 0;
}
/* set i
* set i 1， i set
*/
int insertSet(int i,int set)
{
if(inSet(i,set)==0)
return set|mypow(2,i-1);
return set;
}
/* set i
* set i 0， set
*/
int deleteSet(int i, int set)
{
if(inSet(i,set))
{
set = ~(mypow(2,i-1))&set;
}
return set;
}
/*
*/
print_path(struct path *p)
{
if(p==NULL)
{
printf("1");
return;
}
print_path(p->lastNode);
printf("->%d",p->current+1);
}
/*
* ：
* ：
*1, n 1，2，…，n. S {2,3,...n} k S。
*2, C(S,k) 1 ， S ， k .
*3, S k ，C(S，k)= d(1,k)
* S ,C(S，k) S-k m，C(s-k,m)+d(m,k) ，
*4, S S k， C(S，k）
*5, S {2,3,...n} ， C(S，k) k S ，
C(S,k)+d(k,1) 。
*PS:C(S,k) struct path set = S, current = K, cost = C(S,K)
*/
int tsp(int n, int (*a)[MAX_N])
{
int i,j;
struct path *temp,*p;
struct path **address;
long set;
int cost;
long mincost;
struct path *lastNode;
D[1] = NULL;
// S k ，C(S，k)= d(1,k)
for(i=1;icurrent = i;
temp->cost = a[0][i];
temp->lastNode = NULL;
temp->next = D[1];
temp->set = mypow(2,i-1);
D[1] = temp;
}
// n-2 , J
for(j=2;jset
// i p->set 。
//
if(inSet(i,p->set)==0)
{
// S ,C(S，k) S-k m，C(s-k,m)+d(m,k) ，
set = insertSet(i,p->set);
// C(S,k)
// ， cost ，
// ， struct path C(S,k)
if(address[set]!=NULL&&address[set]->current==i)
{
cost = p->cost + a[p->current][i];
if(cost< address[set]->cost)
{
address[set]->cost = cost;
address[set]->lastNode = p;
}
}
else
{
temp = malloc(sizeof(struct path));
temp->current = i;
temp->cost = p->cost + a[p->current][i];
temp->set = set;
temp->lastNode = p;
temp->next = D[j];
D[j] = temp;
address[set]=temp;
}
}
p = p->next;
}
free(address);
}
}
// S S k， C(S，k）
// S {2,3,...n} ， C(S，k) k S ，
//C(S,k)+d(k,1) 。
mincost = -1;
p = D[n-1];
while(p)
{
if(mincost==-1 || mincost > p->cost + a[p->current][0])
{
mincost = p->cost + a[p->current][0];
lastNode = p;
}
p = p->next;
}
//
printf("mincost=%d
",mincost);
//
print_path(lastNode);
printf("->1
");
return mincost;
}
int main(int argc, char *argv[])
{
int a[MAX_N][MAX_N]=
{ { 0, 10, 20, 30, 40, 50},
{12, 0, 18, 30, 25, 21},
{23, 19, 0, 5, 10, 15},
{34, 32, 4, 0, 8, 16},
{45, 27, 11, 10, 0, 18},
{56, 22, 16, 20, 12, 0}
};
int n = 6;
tsp(n,a);
return EXIT_SUCCESS;
}