# C Program

• 02-10-2013
return0
C Program
Hey guys, I was wondering how difficult of a Program this is and around how much time it would be expected to complete it.

1. Traveling Salesperson Problem

2. We have talked about the Traveling Salesperson Problem in class.
3. For this assignment, you are to read an input file that gives the
4. distances between each possible pair of "cities" for a traveling
5. sales problem and then compute the cost of a "legal" tour. Again,
6. as defined in class, a legal tour of N cities starts at any one of them
7. and visits each of the other cities exactly once before returning to
8. the original destination city. And the cost of a tour is the sum of
9. the "distances" between adjacent cities in the tour.

10. Your program output should print out the cost of the legal tour (or path) and
11. also list the "cities" (well the integers associated with those cities) in the
12. order visited. So, given data for a 4-city (Dallas, New York, Boston) the legal
13. tours are:

14. Dallas, New York, Los Angeles, Boston, Dallas
15. Dallas, Boston, New York, Dallas
16. New York, Dallas, Boston, New York
17. New York, Boston, Dallas, New York
18. Boston, New York, Dallas, Boston
19. Boston, Dallas, New York, Boston

20. and if we assume that the "cost" (or distance) or is represented as

21. Dallas to New York is 1900 miles
22. Boston to Dallas is 1950 miles
23. New York to Boston 150 miles
24. Los Angeles to Dallas is 1400 miles
25. Los Angeles to Boston is 3150 miles
26. Los Angeles to New York is 3100 miles

27. your answer might be something like

28. The tour New York, Dallas, Boston, Los Angeles New York costs 7150.

29. which would represent the sum of 1900 (New York to Dallas), 1950 (Dallas to Boston),
30. 3150 (Boston to Los Angeles) and 3100 (Los Angeles to New York). However, we'll
31. "generalize" both our input and output to use consecutive integers, starting at 1,
32. to represent the cities of the tour.

33. NOTE: For the example data given, 7150 would not be the minimal cost tour. For
34. example, the tour Los Angeles, Dallas, Boston, New York, Los Angeles would
35. cost only 6600. However, for THIS program you're not required to come up
36. with a minimal cost tour, just a legal tour. Any legal tour will do.

37. Requirements:

38. Your C program should consist of the single file, X.c (or whatever
39. you decide to call your program.)

40. Your program will read an input file (from stdin) which includes
41. an unspecified number of command lines which describe the problem.
42. The input (file) will contain two types of commands,
43. and each command will be included on a single line of the file. The
44. commands are:

45. c W
46. a X Y Z

47. for Create a city and Add an edge between two cities. The symbols
48. W,X,Y,Z all stand for "arbitrary" integers. Each "city" will be
49. "named" with a distinct integer, specifically the one included in
50. the "c" command. In the "a" command (add an edge) the edge should
51. be From X To Y, with Cost Z. To make the program a bit easier,
52. all the "Create" commands will precede any "Add" commands in the input
53. file. If you wish you can assume an upper limit of 20 cities, "named"
54. 0-19, for this version of the program. You may also assume that the
55. "names" of the nodes will be consecutive integers starting at 1.

56. So, here is what the input file might look like for our problem including
57. Dallas, Los Angeles, Boston and New York above.

58. c 1
59. c 2
60. c 3
61. c 4
62. a 1 2 1400
63. a 1 3 1950
64. a 1 4 1900
65. a 2 3 3150
66. a 2 4 3100
67. a 3 4 150

68. Since we assume that the distance between cities X and Y is the same whether
69. we go from X to Y or Y to X, we don't need to list the distance for each
70. direction of travel between any pair of cities.

71. Output:
72. A single line which lists the nodes in a legal tour and the cost of that
73. tour. So, for our the input file provided and the example tour listed above
74. (New York, Dallas, Boston, Los Angeles New York) the actual output of your
75. program might be:

76. The tour 4 1 2 3 4 costs 7150.

77. Also, remember that we will (attempt to) compile your program using the command

78. gcc *.c
• 02-10-2013
TheBigH
This doesn't seem too hard or time consuming, but it depends how much programming you have done before. You'll need to know how to handle command line arguments, and familiarity with arrays. If you're comfortable with those, it should only take you about an afternoon to do.
• 02-10-2013
0x47617279
Haha, right I honest to god do peoples homework just because I believe they've tried.. but omg haha, go away
• 02-10-2013
TheBigH
To be fair, the OP hasn't asked us to do it, just for an estimate of how hard it is.
• 02-11-2013
Salem
Given that you only have to output "one legal tour", which the example is just the input order closed to make it a circuit, I'd say 30 mins to an hour.
• 02-11-2013
Click_here
You may want to spend a few hours reading up on the problem, and Dynamic programming.

Did you know wiki has a page for this problem?
[/edit]
• 02-15-2013
return0
Hey guys here is what I got for my program :
Code:

```#include"stdio.h" int x[15],used[15]; int adj[15][15]={0}; int path[15][15],wght[15]; int c,min; int path_ok(int k,int n){ if(used[x[k]])   return 0; if(k‹n-1)   return(adj[x[k-1]][x[k]]); else   return(adj[x[k-1]][x[k]] && adj[x[k]][x[0]]); } void TSP(int k,int n) { int i,sum; for(x[k]=1;x[k]<n;x[k]++) { if(path_ok(k,n)) {   used[x[k]]=1; if(k==n-1) {   sum=0; printf("\n\n\tPOSSIBLE PATH %d : ",c+1); for(i=0;i<n;i++) { printf("%d\t",x[i]);   path[c][i]=x[i];   sum+=adj[x[i]][x[i+1]]; } printf(" : %d",sum); wght[c]=sum; if(c==0 || sum<min)   min=sum;   c++; used[x[k]]=0;getch(); }   else TSP(k+1,n); used[x[k]]=0; } } } void findmin(int n) { int i,j;   for(i=0;i<c;i++) if(wght[i]==min) {   printf("\n\n\tMINIMUM PATH : "); for(j=0;j<n;j++) printf("%d\t",path[i][j]); } } void main() { int i,n,j; int edg;   clrscr(); printf("\n\n\t\tTRAVELLING SALESMAN PROBLEM\n\n"); printf("\n\tEnter the no. of Cities : ");   scanf("%d",&n); printf("\n\n Enter the Cost if path Exist Between cities.:{c1,c2}.Else Enter 0\n\n"); printf("\n\tCITIES\t\tCOST\n\n");   for(i=0;i<n;i++)   for(j=i+1;j<n;j++) { printf("\n\t %d------ %d \t:",i,j);   scanf("%d",&edg); if(edg)   adj[i][j]=adj[j][i]=edg; } used[0]=1; TSP(1,n); if(!c) printf("\n\n\t\tNO PATH FOUND TO COVER ALL THE CITIES\n\n"); else { printf("\n\n\t\tLEGAL TOUR IS %d AND THE PATHS ARE \n\n",min); findmin(n); } getch(); } ```
Does anyone know what is wrong in this code?
• 02-15-2013
Crossfire
HOLY CRAP!!!

yeah i see a big prob, your entire formatting is jacked!

edit/repost your code so we can read it, with proper indenting!

thank you
• 02-16-2013
King Mir
Is that a program or poetry?
• 02-16-2013
Salem
Perhaps he was aiming at this?
http://www.ioccc.org/1987/westley.c
• 02-16-2013
phantomotap
Quote:

Perhaps he was aiming at this?
Aiming a tad high aren't you?

Soma
• 02-16-2013
King Mir
Quote:

Originally Posted by Salem
Perhaps he was aiming at this?
http://www.ioccc.org/1987/westley.c

I'm disappointed that that no longer compiles.
• 02-16-2013
Salem
Quote:

Originally Posted by King Mir
I'm disappointed that that no longer compiles.

Consider it a challenge :D
• 02-16-2013
King Mir
Quote:

Originally Posted by Salem
Consider it a challenge :D

There was only one line wrong. Easy to fix. C code - 47 lines - codepad. I'm happy now.

Course that's still not c11...
• 02-16-2013
phantomotap
O_o

There is no need to order the operations as in the original so we can do a little better.

Soma

C code - 47 lines - codepad