Help with TSP problem

Hey guys i'm fairly new to C and i'm need help on how to start reading the file and storing the strings. Here's the problem I need to solve.



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 thedistances between each possible pair of "cities" for a travelingsales 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 themand visits each of the other cities exactly once before returning tothe original destination city. And the cost of a tour is the sum ofthe "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, Bostonand 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 milesyour answer might be something like The tour New York, Dallas, Boston, Los Angeles New York costs 10100.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, 10100 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 1900 a 1 3 1950 a 1 4 1400 a 2 3 150 a 2 4 3100 a 3 4 3150 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 2 1 3 4 2 costs 10100.



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

Thanks for any help.

Are you in the same class as return0?: http://cboard.cprogramming.com/c-pro...c-program.html

What have you done yet?

For reading files you could start with reading about basic I/O in C.

Bye, Andreas

at least return0 didn't jam the problem description into a single paragraph so that it was possible to read it.

Quote:

---

Here's the problem I need to solve.

---

This is a VERY good problem. Show some respect for 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 man 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.

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.

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 10100.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, 10100 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 1900 a 1 3 1950 a 1 4 1400 a 2 3 150 a 2 4 3100 a 3 4 3150

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 2 1 3 4 2 costs 10100.

What a sweet problem. ;)