C Program

**return0** · 02-10-2013

Hey guys, I was wondering how difficult of a Program this is and around how much time it would be expected to complete it.

Traveling Salesperson Problem
We have talked about the Traveling Salesperson Problem in class.
For this assignment, you are to read an input file that gives the
distances between each possible pair of "cities" for a traveling
sales problem and then compute the cost of a "legal" tour. Again,
as defined in class, a legal tour of N cities starts at any one of them
and visits each of the other cities exactly once before returning to
the original destination city. And the cost of a tour is the sum of
the "distances" between adjacent cities in the tour.
Your program output should print out the cost of the legal tour (or path) and
also list the "cities" (well the integers associated with those cities) in the
order visited. So, given data for a 4-city (Dallas, New York, Boston) the legal
tours are:
Dallas, New York, Los Angeles, Boston, Dallas
Dallas, Boston, New York, Dallas
New York, Dallas, Boston, New York
New York, Boston, Dallas, New York
Boston, New York, Dallas, Boston
Boston, Dallas, New York, Boston
and if we assume that the "cost" (or distance) or is represented as
Dallas to New York is 1900 miles
Boston to Dallas is 1950 miles
New York to Boston 150 miles
Los Angeles to Dallas is 1400 miles
Los Angeles to Boston is 3150 miles
Los Angeles to New York is 3100 miles
your answer might be something like
The tour New York, Dallas, Boston, Los Angeles New York costs 7150.
which would represent the sum of 1900 (New York to Dallas), 1950 (Dallas to Boston),
3150 (Boston to Los Angeles) and 3100 (Los Angeles to New York). However, we'll
"generalize" both our input and output to use consecutive integers, starting at 1,
to represent the cities of the tour.
NOTE: For the example data given, 7150 would not be the minimal cost tour. For
example, the tour Los Angeles, Dallas, Boston, New York, Los Angeles would
cost only 6600. However, for THIS program you're not required to come up
with a minimal cost tour, just a legal tour. Any legal tour will do.
Requirements:
Your C program should consist of the single file, X.c (or whatever
you decide to call your program.)
Your program will read an input file (from stdin) which includes
an unspecified number of command lines which describe the problem.
The input (file) will contain two types of commands,
and each command will be included on a single line of the file. The
commands are:
c W
a X Y Z
for Create a city and Add an edge between two cities. The symbols
W,X,Y,Z all stand for "arbitrary" integers. Each "city" will be
"named" with a distinct integer, specifically the one included in
the "c" command. In the "a" command (add an edge) the edge should
be From X To Y, with Cost Z. To make the program a bit easier,
all the "Create" commands will precede any "Add" commands in the input
file. If you wish you can assume an upper limit of 20 cities, "named"
0-19, for this version of the program. You may also assume that the
"names" of the nodes will be consecutive integers starting at 1.
So, here is what the input file might look like for our problem including
Dallas, Los Angeles, Boston and New York above.
c 1
c 2
c 3
c 4
a 1 2 1400
a 1 3 1950
a 1 4 1900
a 2 3 3150
a 2 4 3100
a 3 4 150
Since we assume that the distance between cities X and Y is the same whether
we go from X to Y or Y to X, we don't need to list the distance for each
direction of travel between any pair of cities.
Output:
A single line which lists the nodes in a legal tour and the cost of that
tour. So, for our the input file provided and the example tour listed above
(New York, Dallas, Boston, Los Angeles New York) the actual output of your
program might be:
The tour 4 1 2 3 4 costs 7150.
Also, remember that we will (attempt to) compile your program using the command
gcc *.c

**TheBigH** · 02-10-2013

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.

**0x47617279** · 02-10-2013

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

**TheBigH** · 02-10-2013

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

**Salem** · 02-11-2013

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.

**Click_here** · 02-11-2013

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]

**return0** · 02-15-2013

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?

**Crossfire** · 02-15-2013

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

**King Mir** · 02-16-2013

Is that a program or poetry?

**Salem** · 02-16-2013

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

**phantomotap** · 02-16-2013

Perhaps he was aiming at this?

Aiming a tad high aren't you?

Soma

**King Mir** · 02-16-2013

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.

**Salem** · 02-16-2013

Originally Posted by King Mir

I'm disappointed that that no longer compiles.

Consider it a challenge

**King Mir** · 02-16-2013

Originally Posted by Salem

Consider it a challenge

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

Course that's still not c11...

**phantomotap** · 02-16-2013

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

Thread: C Program

Thread Tools

Search Thread

Display

C Program

Similar Threads

Website where I can find CS 108 (Program solving and program design in C) chapter rev

Calling a program within a program within a program with redirected io streams

Get program to copy itself into program files, then start on startup.

Not opening multiple copies of a program & sending data to another program

Help Please - program to display file renders Windows Program Error