-
Notifications
You must be signed in to change notification settings - Fork 1
/
TSP ky thuat tham an.c
227 lines (225 loc) · 5.57 KB
/
TSP ky thuat tham an.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<math.h>
typedef struct{
float x,y;
char tp[5];
}thongtin;
//Ban dau luu tru danh sach cac canh
typedef struct{
float L[100][100];
}cung;
thongtin *thongtintp(int *n){
FILE *f=fopen("TSP1.txt","r");
thongtin *dstp = (thongtin*)malloc(sizeof(thongtin));
int i=0;
if(f==NULL){
printf("Loi mo tep");
return 0;
}
while(!feof(f)){
fscanf(f,"%f %f %[^\n]",&dstp[i].x,&dstp[i].y,&dstp[i].tp);
i++;
dstp=realloc(dstp,sizeof(thongtin)*(i+1));
}
*n=i;
fclose(f);
return dstp;
}
void in(thongtin *dstp,int n){
int i;
for(i=0;i<n;i++){
printf("%s %.2f %.2f\n",dstp[i].tp,dstp[i].x,dstp[i].y);
}
}
//Khoi tao
void Create(cung *E,int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
E->L[i][j]=0;
}
}
}
//them cung
void addedges(cung *E,int x,int y,float w){
E->L[x][y] = E->L[y][x] =w;
}
//Tinh trong so cho moi canh
void danhsachcung(thongtin *dstp,cung *E,int n){
int i,j;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
float w=sqrt(pow(dstp[i].x - dstp[j].x,2)+pow(dstp[i].y - dstp[j].y,2));
addedges(E,i,j,w);
}
}
}
void incung(cung *E,int n){
int i,j;
for(i=0;i<n;i++){
printf("%3c\t\t",i+97);
}
for(i=0;i<n;i++){
printf("\n%c ",i+97);
for(j=0;j<n;j++){
printf("%.2f\t\t",E->L[i][j]);
}
}
}
//Noi dung chinh
//Luu trong so cua cac cung nam tren duong cheo chinh
typedef struct{
int u,v;//U la dinh dau, V la dinh cuoi
float w;//trong so
}canh;
void doccaccanhchinh(thongtin *dstp,canh a[],int n){
int i,j,k=0,temp;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
if(i==j){
int t;
for(t=0;t<=j;t++){//doc de bo qua cac so nam duoi duong cheo chinh
temp=sqrt(pow(dstp[i].x - dstp[j].x,2)+pow(dstp[i].y - dstp[j].y,2));
}
}
else{
a[k].u=i;
a[k].v=j;
a[k].w=sqrt(pow(dstp[i].x - dstp[j].x,2)+pow(dstp[i].y - dstp[j].y,2));
k++;
}
}
}
}
void Indanhsachcanhchinh(canh a[],int m,int la_PA){
int i,j;
float tong=0;
for(i=0;i<m;i++){
printf("%d. %c-%c = %.2f\n",i+1,a[i].u+65,a[i].v+65,a[i].w);
if(la_PA){
tong+=a[i].w;
}
}
if(la_PA){
printf("\nTong do dai cac canh la %.2f",tong);
}
}
//sap xep
void Swap(canh *x,canh *y){
canh temp=*x;
*x=*y;
*y=temp;
}
void bubblesort(canh A[],int m){
int i,j;
for(i=0;i<m-1;i++){
for(j=m-1;j>i;j--){
if(A[j].w < A[j-1].w){
Swap(&A[j],&A[j-1]);
}
}
}
}
//kiem tra dinh cap 3
int dinhcap3(canh PA[],int k/*Gom k canh*/, canh moi/*dua vao mot canh moi*/){
int i,dem;
i=0;
dem=1;//Dem = 1 la da co mot dinh la mot
while(i<k && dem<3){
/*Ta xet canh moi cua dinh dau co trung voi canh dau cua dinh hien tai khong hoac
Ta xet canh moi cua dinh dau co trung voi canh cuoi cua dinh hien tai khong*/
if(moi.u == PA[i].u || moi.u == PA[i].v){
dem++;
}
i++;
}
if(dem==3) return 1;//Neu dem = 3 thi tra ve 1
//nguoc lai
i=0;
dem=1;//Dem = 1 la da co mot dinh la mot
while(i<k && dem<3){
/*Ta xet canh moi cua dinh cuoi co trung voi canh dau cua dinh hien tai khong hoac
Ta xet canh moi cua dinh cuoi co trung voi canh cuoi cua dinh hien tai khong*/
if(moi.v == PA[i].u || moi.v == PA[i].v){
dem++;
}
i++;
}
return dem==3;
}
//khoi tao rung
void init_forest(int parent[],int n){
int i;
//khoi tao moi dau cha cua tat ca cac dinh dieu bang chinh no
for(i=0;i<n;i++){
parent[i]=i;
}
}
//Tim goc cua mot dinh bat ky trong mot rung cay
int find_root(int parent[],int x){
while(x != parent[x]){
x=parent[x];
}
return x;//tra ve goc
}
//kiem tra chu trinh
int chu_trinh(int r_dau,int r_cuoi){
return (r_dau == r_cuoi);//Neu goc dinh dau == goc cua dinh cuoi thi do la mot chu trinh
}
//Hop nhat 2 cay lam mot
void update_forest(int parent[],int r_cay1,int r_cay2){
parent[r_cay2]=r_cay1; //hop nhat lay goc cay 1 la cha cua cay 2
}
//ky thuat tham an
void greedy(canh dscanh[],int n,canh PA[]){
int i,j;
int parent[n];
init_forest(parent,n);
int r_dau,r_cuoi;
//Chon cac canh nho nhat khong tao thanh dinh cap 3 va khong tao thanh chu trinh thieu
j=0;
for(i=0;i< n*(n-1)/2 && j<n-1 ;i++){
r_dau = find_root(parent,dscanh[i].u);
r_cuoi = find_root(parent,dscanh[i].v);
if(!dinhcap3(PA,j,dscanh[i]) && !chu_trinh(r_dau,r_cuoi)){
PA[j]=dscanh[i];//danh sach canh[i] khong tao dinh cap 3, khong tao thanh chu trinh thieu
j++;
update_forest(parent, r_dau, r_cuoi);//hop nhat 2 cay: dat cha cua goc cuoi cung bang goc dau
}
}
//Den day PA da co n-1 canh
//Tim mot canh trong so canh chua xet dua vao PA neu no khong tao thanh dinh cap va khong tao thanh chu trinh thieu
//Luc nay i danh o mot gia tri nao do
for(;i<n*(n-1)/2;i++){
r_dau = find_root(parent,dscanh[i].u);
r_cuoi = find_root(parent,dscanh[i].v);
if(!dinhcap3(PA,n-1,dscanh[i]) && !chu_trinh(r_dau,r_cuoi)){
PA[n-1]=dscanh[i];//danh sach canh[i] khong tao dinh cap 3, khong tao thanh chu trinh thieu
break;//Ket thuc vi PA da co du n canh, tao thanh chu trinh
}
}
}
int main(){
int n;
thongtin *dstp = thongtintp(&n);
cung E;
in(dstp,n);
Create(&E,n);
danhsachcung(dstp,&E,n);
incung(&E,n);
canh dscanh[100];
doccaccanhchinh(dstp,dscanh,n);
printf("\ndanh sach canh cua do thi:\n");
Indanhsachcanhchinh(dscanh,n*(n-1)/2,0);
printf("\ndanh sach canh cua do thi sau khi SAP XEP:\n");
bubblesort(dscanh,n*(n-1)/2);
Indanhsachcanhchinh(dscanh,n*(n-1)/2,0);
canh PA[n];
greedy(dscanh,n,PA);
printf("\nPhuong an:\n");
Indanhsachcanhchinh(PA,n,1);
free(dstp);
return 0;
}