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. 
   
3. We have talked about the Traveling Salesperson Problem in class.
   
4. For this assignment, you are to read an input file that gives the
   
5. distances between each possible pair of "cities" for a traveling
   
6. sales problem and then compute the cost of a "legal" tour. Again,
   
7. as defined in class, a legal tour of N cities starts at any one of them
   
8. and visits each of the other cities exactly once before returning to
   
9. the original destination city. And the cost of a tour is the sum of
   
10. the "distances" between adjacent cities in the tour.
    
11. 
    
12. Your program output should print out the cost of the legal tour (or path) and
    
13. also list the "cities" (well the integers associated with those cities) in the
    
14. order visited. So, given data for a 4-city (Dallas, New York, Boston) the legal
    
15. tours are:
    
16. 
    
17. Dallas, New York, Los Angeles, Boston, Dallas
    
18. Dallas, Boston, New York, Dallas
    
19. New York, Dallas, Boston, New York
    
20. New York, Boston, Dallas, New York
    
21. Boston, New York, Dallas, Boston
    
22. Boston, Dallas, New York, Boston
    
23. 
    
24. and if we assume that the "cost" (or distance) or is represented as
    
25. 
    
26. Dallas to New York is 1900 miles
    
27. Boston to Dallas is 1950 miles
    
28. New York to Boston 150 miles
    
29. Los Angeles to Dallas is 1400 miles
    
30. Los Angeles to Boston is 3150 miles
    
31. Los Angeles to New York is 3100 miles
    
32. 
    
33. your answer might be something like
    
34. 
    
35. The tour New York, Dallas, Boston, Los Angeles New York costs 7150.
    
36. 
    
37. which would represent the sum of 1900 (New York to Dallas), 1950 (Dallas to Boston),
    
38. 3150 (Boston to Los Angeles) and 3100 (Los Angeles to New York). However, we'll
    
39. "generalize" both our input and output to use consecutive integers, starting at 1,
    
40. to represent the cities of the tour.
    
41. 
    
42. NOTE: For the example data given, 7150 would not be the minimal cost tour. For
    
43. example, the tour Los Angeles, Dallas, Boston, New York, Los Angeles would
    
44. cost only 6600. However, for THIS program you're not required to come up
    
45. with a minimal cost tour, just a legal tour. Any legal tour will do.
    
46. 
    
47. Requirements:
    
48. 
    
49. Your C program should consist of the single file, X.c (or whatever
    
50. you decide to call your program.)
    
51. 
    
52. Your program will read an input file (from stdin) which includes
    
53. an unspecified number of command lines which describe the problem.
    
54. The input (file) will contain two types of commands,
    
55. and each command will be included on a single line of the file. The
    
56. commands are:
    
57. 
    
58. c W
    
59. a X Y Z
    
60. 
    
61. for Create a city and Add an edge between two cities. The symbols
    
62. W,X,Y,Z all stand for "arbitrary" integers. Each "city" will be
    
63. "named" with a distinct integer, specifically the one included in
    
64. the "c" command. In the "a" command (add an edge) the edge should
    
65. be From X To Y, with Cost Z. To make the program a bit easier,
    
66. all the "Create" commands will precede any "Add" commands in the input
    
67. file. If you wish you can assume an upper limit of 20 cities, "named"
    
68. 0-19, for this version of the program. You may also assume that the
    
69. "names" of the nodes will be consecutive integers starting at 1.
    
70. 
    
71. So, here is what the input file might look like for our problem including
    
72. Dallas, Los Angeles, Boston and New York above.
    
73. 
    
74. c 1
    
75. c 2
    
76. c 3
    
77. c 4
    
78. a 1 2 1400
    
79. a 1 3 1950
    
80. a 1 4 1900
    
81. a 2 3 3150
    
82. a 2 4 3100
    
83. a 3 4 150
    
84. 
    
85. Since we assume that the distance between cities X and Y is the same whether
    
86. we go from X to Y or Y to X, we don't need to list the distance for each
    
87. direction of travel between any pair of cities.
    
88. 
    
89. Output:
    
90. A single line which lists the nodes in a legal tour and the cost of that
    
91. tour. So, for our the input file provided and the example tour listed above
    
92. (New York, Dallas, Boston, Los Angeles New York) the actual output of your
    
93. program might be:
    
94. 
    
95. The tour 4 1 2 3 4 costs 7150.
    
96. 
    
97. Also, remember that we will (attempt to) compile your program using the command
    
98. 
    
99. gcc *.c

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.

Haha, right I honest to god do peoples homework just because I believe they've tried.. but omg haha, go away

To be fair, the OP hasn't asked us to do it, just for an estimate of how hard it is.

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.

You may want to spend a few hours reading up on the problem, and Dynamic programming.

[edit]
Did you know wiki has a page for this problem?
[/edit]

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?

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

Is that a program or poetry?

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

Quote:

---

Perhaps he was aiming at this?

---

Aiming a tad high aren't you?

Soma

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.

Quote:

---

Originally Posted by King Mir

I'm disappointed that that no longer compiles.

---

Consider it a challenge :D

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...

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