Help with TSP problem

This is a discussion on Help with TSP problem within the C Programming forums, part of the General Programming Boards category; Hey guys i'm fairly new to C and i'm need help on how to start reading the file and storing ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    7

    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.

  2. #2
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Are you in the same class as return0?: C Program

    What have you done yet?

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

    Bye, Andreas

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    at least return0 didn't jam the problem description into a single paragraph so that it was possible to read it.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 02-14-2013 at 11:45 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 01-06-2013, 07:49 AM
  2. Replies: 1
    Last Post: 12-07-2012, 10:00 AM
  3. Replies: 4
    Last Post: 10-16-2008, 08:30 PM
  4. Visual Studio Linker problem or my problem?
    By OOPboredom in forum C Programming
    Replies: 2
    Last Post: 04-13-2004, 01:32 AM
  5. syntax linked list problem & struct problem
    By beely in forum C Programming
    Replies: 5
    Last Post: 11-11-2002, 09:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21