Results 1 to 8 of 8

Math Help - TSP travelling salesperson problem

  1. #1
    Newbie
    Joined
    May 2009
    From
    Patchogue NY (Long Island)
    Posts
    21

    TSP travelling salesperson problem

    Can someone please point me in the direction of a GOOD explnation for how to do these when there is a matrix given? How to figure out the tour cost?I have googled for ages but nothing is explaining what is actually the process to find a solution, can someone please explain or just point me in the direction of an explanation.

    I dont understand what is being done to the matrix to arrive at the tour price?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by SydneyBristow View Post
    Can someone please point me in the direction of a GOOD explnation for how to do these when there is a matrix given? How to figure out the tour cost?I have googled for ages but nothing is explaining what is actually the process to find a solution, can someone please explain or just point me in the direction of an explanation.

    I dont understand what is being done to the matrix to arrive at the tour price?
    See here.

    If you have five cities A, B, C, D, E, then you'll have a 5 by 5 matrix with its entries are distance between them. Travel costs are predetermined. If you find a solution in a brute force manner, there are 5! cases described by permutations.

    For example,
    ABCDE,
    BACDE,
    ....

    n! is a really big number for a large n, so you might need to find an approximate solution of TSP by using heuristic algorithms.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    From
    Patchogue NY (Long Island)
    Posts
    21
    I read that wiki page, i still dont get it.

    I need to learn to do an Approximate TSP

    For example, given this matrix

    A B C D E F
    A ∞ 3 2 7 1 5
    B 3 ∞ 5 2 3 2
    C 2 5 ∞ 3 4 1
    D 7 2 3 ∞ 4 3
    E 1 3 4 4 ∞ 5
    F 5 2 1 3 5 ∞


    in what order are the vertices inserted into the algorithm (i dont understand what algorithm to be quite honest)


    . Steps:
    (a) T1 = A 􀀀 A
    (b) T2 = A 􀀀 E 􀀀 A
    (c) T3 = A 􀀀 E 􀀀 C 􀀀 A
    (d) T4 = A 􀀀 E 􀀀 F 􀀀 C 􀀀 A
    (e) T5 = A 􀀀 E 􀀀 B 􀀀 F 􀀀 C 􀀀 A
    (f) T6 = A 􀀀 E 􀀀 D 􀀀 B 􀀀 F 􀀀 C 􀀀 A
    2. Total cost is 1 + 4 + 2 + 2 + 1 + 2 = 12.

    I dont know why A-A =1 and then for t2 it is A-E-A??? Why? WHY!! I feel like i am going to go insane trying to figure this out.

    Please help me
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by SydneyBristow View Post
    I read that wiki page, i still dont get it.

    I need to learn to do an Approximate TSP

    For example, given this matrix

    A B C D E F
    A ∞ 3 2 7 1 5
    B 3 ∞ 5 2 3 2
    C 2 5 ∞ 3 4 1
    D 7 2 3 ∞ 4 3
    E 1 3 4 4 ∞ 5
    F 5 2 1 3 5 ∞


    in what order are the vertices inserted into the algorithm (i dont understand what algorithm to be quite honest)


    . Steps:
    (a) T1 = A �� A
    (b) T2 = A �� E �� A
    (c) T3 = A �� E �� C �� A
    (d) T4 = A �� E �� F �� C �� A
    (e) T5 = A �� E �� B �� F �� C �� A
    (f) T6 = A �� E �� D �� B �� F �� C �� A
    2. Total cost is 1 + 4 + 2 + 2 + 1 + 2 = 12.

    I dont know why A-A =1 and then for t2 it is A-E-A??? Why? WHY!! I feel like i am going to go insane trying to figure this out.

    Please help me
    I think it depends on what algorithm you use.

    A B C D E F
    A 0 3 2 7 1 5
    B 3 0 5 2 3 2
    C 2 5 0 3 4 1
    D 7 2 3 0 4 3
    E 1 3 4 4 0 5
    F 5 2 1 3 5 0

    There are 6! cases for the brute force method in your example.

    For example,

    The travel cost of the route for ACDFEB is

    A-C : 2
    C-D: 3
    D-F: 3
    F-E: 5
    E-B : 3
    B-A: 3

    If you sum up the whole number, then the total cost is 19.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    From
    Patchogue NY (Long Island)
    Posts
    21
    Ok here is what i dont get.

    How do you decide on that route? ... why cant its just be ABCDEF, why is it ACDFEB

    Why is your route different from the correct answer?

    How do i know what the algorithm options are. This is supposed to be approximate TSP. I read the explanation but it literally sounds like gibberish.

    this is the explanation:

    Pick any vertex as a starting circuit C1 consisting
    of 1 vertex.
    Given the k-vertex circuit Ck, k ≥ 1, find the
    vertex zk not on Ck that is closest to a vertex,
    call it yk , on Ck. (cost matrix C is symmetric)
    Let Ck+1 be the k+1-vertex circuit obtained by
    inserting zk immediately in front of yk in Ck.
    Repeat steps 2 and 3 until a Hamilton circuit
    (containing all vertices) is formed
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by SydneyBristow View Post
    Ok here is what i dont get.

    How do you decide on that route? ... why cant its just be ABCDEF, why is it ACDFEB

    Why is your route different from the correct answer?

    How do i know what the algorithm options are. This is supposed to be approximate TSP. I read the explanation but it literally sounds like gibberish.

    this is the explanation:

    Pick any vertex as a starting circuit C1 consisting
    of 1 vertex.
    Given the k-vertex circuit Ck, k ≥ 1, find the
    vertex zk not on Ck that is closest to a vertex,
    call it yk , on Ck. (cost matrix C is symmetric)
    Let Ck+1 be the k+1-vertex circuit obtained by
    inserting zk immediately in front of yk in Ck.
    Repeat steps 2 and 3 until a Hamilton circuit
    (containing all vertices) is formed
    Calculate cost ABCDE as I did in my previous post. Is it the same with ACDFEB? What I am saying is that the problem reduces to the permutation problem. Different permutation generates the different travel cost. Your first line seems to use the greedy algorithm. As I said, there are tons of algorithms to solve TSP problem using heuristics, and your algorithm is simply one of them.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2009
    From
    Patchogue NY (Long Island)
    Posts
    21
    ok it is sort of becoming more clear now. So using the greedy algorithm is to choose the closest point from the current point as the next point.

    So if i start at A the closest is E =1
    from E to B=3
    B to D (or F, but alphabetically first lets say D)=2
    D to C=3
    C to F=1
    F back to A =5

    So i get AEBDCFA which is going to be 1+3+2+3+1+5=15 which is the tour cost of that particular tour using the greedy algorithm, so it is one of many possible solutions for this problem?

    So i am looking at a practice exam problem, and the solution is 12 and the tour chosen is AEDBFCA which is a more optimal tour... how do i know when to choose what? is that some other algorithm that produced AEDBFCA?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by SydneyBristow View Post
    ok it is sort of becoming more clear now. So using the greedy algorithm is to choose the closest point from the current point as the next point.

    So if i start at A the closest is E =1
    from E to B=3
    B to D (or F, but alphabetically first lets say D)=2
    D to C=3
    C to F=1
    F back to A =5

    So i get AEBDCFA which is going to be 1+3+2+3+1+5=15 which is the tour cost of that particular tour using the greedy algorithm, so it is one of many possible solutions for this problem?

    So i am looking at a practice exam problem, and the solution is 12 and the tour chosen is AEDBFCA which is a more optimal tour... how do i know when to choose what? is that some other algorithm that produced AEDBFCA?
    If you use a permutaion method, you can get the correct answer for TSP all the time. However, it is not feasible to calculate all n! cases if n is a large number. For instance, if you have 100 cities, the time of computation might require more than billion years ( O(100!) > O(2^100) and 2^100 is an enormous number).

    My suggestion is, if n < 10, then use the permutation and find the exact answer.

    If n>10, use an heuristic algorithm to find the approximate solution of TSP problem.

    1. Greedy algorith : it is very straight forward and easy to use. It does not generate a good performance though.
    2. Dynamic programming : You might consider this one using some tables.
    3. Genetic algorithm : It applies crossover, mutation, etc, to the permutations of cities. Instead of searching n!, it efficiently finds the approximate solution.
    ....

    I don't know much about other algorithms for TSP.

    There is no single algorithm that performs best all the time in all situations for TSP problems. It is up to you to choose the algorithm after examining the TSP problem you want to solve.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Asymmetric Travelling Salesman Problem - Particular case
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 17th 2011, 03:13 AM
  2. Travelling along...
    Posted in the Geometry Forum
    Replies: 2
    Last Post: July 29th 2010, 06:38 AM
  3. Travelling Salesman
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: April 27th 2009, 05:08 AM
  4. Discrete Math Traveling Salesperson
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 20th 2008, 03:11 AM
  5. travelling boat problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 15th 2007, 09:55 PM

Search Tags


/mathhelpforum @mathhelpforum