Thread: Travelling salesman

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    2

    Question Travelling salesman

    Hi everybody,

    I have this matrix.

    - X Y Z Q
    X 0 5 3 2
    Y 5 0 4 1
    Z 3 4 0 6
    Q 2 1 6 0

    X,Y,Z,Q are citys, numbers are miles. example: X-Y: 5 mile

    My code must generate 3 random route (ex: XQZY, XYZQ, QZYX) and find min route.


    X-Q-Z-Y =2+6+4=12mile
    Y-Q-Z-X =1+6+3=10mile
    Q-Z-Y-X =6+4+5=15mile

    Min route is Y-Q-Z-X =10mile

    Can you help me?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    My code must generate 3 random route (ex: XQZY, XYZQ, QZYX) and find min route.
    (a) What is a "random route"? (NB: mathematical descriptions are not appropriately explained by example. What are the conditions you can/want to/have to work with? Do you work with all 2^n sub-tour elimination conditions in a polyhedral description? Or is the combinatorial description all you want to use?)
    (b) How do you want to generate a (random) construct defined as in (a)? Trying all (n-1)!/2 permutations? Solving a LP? Using a genetic algorithm? Using the approach you choose, how will your solutions distributed among all possible routes? Is it really random?

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    2
    I can generate 3 random route but i don't know how can i calculate routes. How can i take the miles from matrix? which codes? I don't have any information.

    My skill is beginner.

  5. #5
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    How would you, as a person, solve the task? Write down the matrix on a piece of paper, generate a random route, and then figure out how you would use the matrix before you try to figure out how to get the computer to use the matrix.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So you start with
    Code:
    int table[4][4] = {
      // numbers
    };
    Then you have something which turns the letters X Y Z Q into array indices 0 1 2 3

    Then take the first two letters (XQ) and discover that table[0][3] is ...
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Travelling salesman problem algorithm
    By Taturana182 in forum C++ Programming
    Replies: 19
    Last Post: 03-24-2010, 09:26 AM
  2. Travelling through Norway and northern Sweden
    By Shiro in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 07-13-2002, 09:20 AM
  3. travelling...
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 06-12-2002, 05:05 PM