# how to modify the program for traveling salesman problem?

Page 1 of 1

## 0 Replies - 2106 Views - Last Post: 20 October 2009 - 03:33 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=133160&amp;s=b91a213ceaabf29470925ee4d3c15769&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 cron7

Reputation: 0
• Posts: 11
• Joined: 16-October 09

# how to modify the program for traveling salesman problem?

Posted 20 October 2009 - 03:33 AM

The code below is to solve Traveling Salesman Problem with node 5 (5 customers).
I wonder how to modify the program so that node 96 (96 customers) can be solved.
```#include "stdio.h"
#include "stdlib.h"
int D[5][5]={0,10,15,6,2,10,0,8,13,9,15,8,0,20,15,6,13,20,0,5,2,9,15,5,0};
int tabu[6]={0};
int cand[6]={0};
int fbest=59;//45[0 1 2 3],60[0 2 1 3],60[3 1 0 2],59[3 0 1 2]
int xbest[4]={3,0,1,2};
int x[4]={3,0,1,2};
int f=59;
int bnum=0;

int find(int array[],int k)
{
int i=0;
for (;i<4;i++){
if (array[i]==k) {
return i+1;
}
}
}
void CreAns( )
{
int temp = 100;
int ftemp = 100;
int t;
int pos=-1;
int k=-1;
for (int i=0;i<6;i++){
if (!tabu[i]&&(temp > cand[i])) {
temp = cand[i];
k = i;
}
if (ftemp > cand[i]) {
ftemp = cand[i];
pos = i;
}
}
if (k == -1) {
switch(pos) {
case 0:
t=x[0];
x[0]=x[1];
x[1]=t;
break;
case 1:
t=x[0];
x[0]=x[2];
x[2]=t;
break;
case 2:
t=x[0];
x[0]=x[3];
x[3]=t;
break;
case 3:
t=x[1];
x[1]=x[2];
x[2]=t;
break;
case 4:
t=x[1];
x[1]=x[3];
x[3]=t;
break;
case 5:
t=x[2];
x[2]=x[3];
x[3]=t;
break;
}
for(int j=0;j<6;j++){
if (tabu[j] > 0) {
tabu[j] -=1;
}
}
if (fbest > ftemp) {
for (int i=0;i<4;i++)
xbest[i] = x[i];
fbest = ftemp;
}
tabu[pos] = 3;
bnum++;
}
if (k != -1) {
switch(k) {
case 0:
t=x[0];
x[0]=x[1];
x[1]=t;
break;
case 1:
t=x[0];
x[0]=x[2];
x[2]=t;
break;
case 2:
t=x[0];
x[0]=x[3];
x[3]=t;
break;
case 3:
t=x[1];
x[1]=x[2];
x[2]=t;
break;
case 4:
t=x[1];
x[1]=x[3];
x[3]=t;
break;
case 5:
t=x[2];
x[2]=x[3];
x[3]=t;
break;
}
f=cand[k];
for(int j=0;j<6;j++){
if (tabu[j] > 0) {
tabu[j] -=1;
}
}
if (fbest > temp) {
for (int i=0;i<4;i++)
xbest[i] = x[i];
fbest = temp;
}
tabu[k] = 3;
}
}
void CreCan( )
{
int prior;
int pos=-1;
int k=0;
int x_temp[4];
int t;
int sum;
int l;
for (int i=0;i<6;i++){
switch(i) {
case 0:
for (l=0;l<4;l++)
x_temp[l] = x[l];
t=x_temp[0];
x_temp[0]=x_temp[1];
x_temp[1]=t;
sum = 0;
k = 0;
prior = 0;
while (k<4) {
pos = find(x_temp,k);
sum = sum + D[prior][pos];
prior = pos;
k++;
}
sum = sum + D[prior][0];
cand[0] = sum;
break;
case 1:
for (l=0;l<4;l++)
x_temp[l] = x[l];
t=x_temp[0];
x_temp[0]=x_temp[2];
x_temp[2]=t;
sum = 0;
k = 0;
prior = 0;
while (k<4) {
pos = find(x_temp,k);
sum = sum + D[prior][pos];
prior = pos;
k++;
}
sum = sum + D[prior][0];
cand[1] = sum;
break;
case 2:
for (l=0;l<4;l++)
x_temp[l] = x[l];
t=x_temp[0];
x_temp[0]=x_temp[3];
x_temp[3]=t;
sum = 0;
k = 0;
prior = 0;
while (k<4) {
pos = find(x_temp,k);
sum = sum + D[prior][pos];
prior = pos;
k++;
}
sum = sum + D[prior][0];
cand[2] = sum;
break;
case 3:
for (l=0;l<4;l++)
x_temp[l] = x[l];
t=x_temp[1];
x_temp[1]=x_temp[2];
x_temp[2]=t;
sum = 0;
k = 0;
prior = 0;
while (k<4) {
pos = find(x_temp,k);
sum = sum + D[prior][pos];
prior = pos;
k++;
}
sum = sum + D[prior][0];
cand[3] = sum;
break;
case 4:
for (l=0;l<4;l++)
x_temp[l] = x[l];
t=x_temp[1];
x_temp[1]=x_temp[3];
x_temp[3]=t;
sum = 0;
k = 0;
prior = 0;
while (k<4) {
pos = find(x_temp,k);
sum = sum + D[prior][pos];
prior = pos;
k++;
}
sum = sum + D[prior][0];
cand[4] = sum;
break;
case 5:
for (l=0;l<4;l++)
x_temp[l] = x[l];
t=x_temp[2];
x_temp[2]=x_temp[3];
x_temp[3]=t;
sum = 0;
k = 0;
prior = 0;
while (k<4) {
pos = find(x_temp,k);
sum = sum + D[prior][pos];
prior = pos;
k++;
}
sum = sum + D[prior][0];
cand[5] = sum;
break;
}

}
}
void insert(int array[])
{
int Cn[2];
int i,j;
int pos;
int index[4];
Cn[0]=Cn[1]=-1;
while (Cn[0]==Cn[1]) {
for(i=0; i<2;i++){
Cn[i]=rand()%4;
}
}
for(j=0;j<2;j++){
pos=array[Cn[j]];
array[Cn[j]]=-1;
for(i=0;i<4;i++){
if (array[i]>pos) {
array[i]--;
}
}
}
for(i=0;i<4;i++){
index[i]=-1000;
}
for(i=0;i<4;i++){
if (array[i]>=0) {
index[array[i]]=i;
}
}
i=0;
while (index[i]>=0) {

}
}
int main()
{
int i;
for (i=0;i<10000;i++){
CreCan();
CreAns();
if (bnum > 40) {
break;
}
}

printf("\n");
for (i=0;i<4;i++)
printf("%d ",xbest[i]);
printf(" %d\n",fbest);
for (i=0;i<4;i++)
printf("%d ",x[i]);
printf(" %d\n",f);
return 1;

}

```

thanks

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }