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
