How to use Perl Graph module to solve travel salesperson problem (TSP)?

Discussion in 'Perl Misc' started by Meng, Mar 17, 2005.

  1. Meng

    Meng Guest

    Hi All,
    I'm designing a project to solve TSP issue with Perl. I found Graph
    module is quite helpful but it's not good enough. I want to create a
    undirected graph,each node can connect each other with different
    weights in the graph. I can set up the start ('a') and end ('e')
    points,the routine should start from 'a' and pass every node,finish at
    'e'. The script can find the shortest routine at last, for example
    a->c->b->d->e. I can use APSP_Floyd_Warshall and
    $SP->path_vertices('a','e') functions. But it will only return the
    shortest way between 2 points, such as a->e,it doesn't pass and count
    every node. Does anybody can help me?

    Thank you very much.

    David Meng

    -------------------Start-----------
    #!/usr/bin/perl -w

    use strict;

    use Graph::Undirected;
    my $g = new Graph::Undirected->new;

    $g->add_weighted_edge('a', 'b', 1);
    $g->add_weighted_edge('a', 'c', 2);
    $g->add_weighted_edge('a', 'd',3);
    $g->add_weighted_edge('a', 'e',4);
    $g->add_weighted_edge('b', 'c',5);
    $g->add_weighted_edge('b', 'd',6);
    $g->add_weighted_edge('b', 'e',7);
    $g->add_weighted_edge('c', 'd',8);
    $g->add_weighted_edge('c', 'e',9);
    $g->add_weighted_edge('d', 'e',10);

    my $SP = $g->APSP_Floyd_Warshall;

    $path = $SP->path_length('a', 'e');

    print " The shortest path from a to e is $path \n";
    @pp= $SP->path_vertices('a','e');
    print "path=@pp\n";
    --------------END--------
    output :

    The shortest path from a to e is 4
    path=a e
    Meng, Mar 17, 2005
    #1
    1. Advertising

  2. Meng

    John Bokma Guest

    Meng wrote:

    > Hi All,
    > I'm designing a project to solve TSP issue with Perl.


    You probably want an approximation since if the number of cities is big you
    can drink quite some coffee.

    Look for flexmap [1] (easy to implement). I have no idea how good it is
    nowadays (i used it over 10 years ago)

    I also found this one: http://portal.acm.org/citation.cfm?id=965276

    [1] Fritzke, B., & Wilke, P. (1991). FLEXMAP--A neural network for the
    traveling salesman problem with linear time and space complexity.

    --
    John Small Perl scripts: http://johnbokma.com/perl/
    Perl programmer available: http://castleamber.com/
    Happy Customers: http://castleamber.com/testimonials.html
    John Bokma, Mar 17, 2005
    #2
    1. Advertising

  3. Meng

    Guest

    Thanks John. the number of nodes is <10.
    , Mar 17, 2005
    #3
  4. Meng

    John Bokma Guest

    John Bokma, Mar 17, 2005
    #4
  5. Meng

    Guest

    , Mar 18, 2005
    #5
  6. Meng

    John Bokma Guest

    wrote:

    >
    > John Bokma wrote:
    >> wrote:
    >>
    >> > Thanks John. the number of nodes is <10.

    >>
    >> Ah, ok,
    >>
    >> so that means creating 9! = 362880 paths (at most) and keeping the

    > shortest
    >> one.

    >
    > Does anybody know the solution?


    The solution is creating all possible paths and finding the shortest

    --
    John Small Perl scripts: http://johnbokma.com/perl/
    Perl programmer available: http://castleamber.com/
    Happy Customers: http://castleamber.com/testimonials.html
    John Bokma, Mar 18, 2005
    #6
  7. Meng

    Guest

    But how to do it by Perl Graph module?
    , Mar 18, 2005
    #7
  8. Meng

    John Bokma Guest

    John Bokma, Mar 18, 2005
    #8
  9. Meng

    Ted Zlatanov Guest

    On 17 Mar 2005, wrote:

    > But how to do it by Perl Graph module?


    Read the documentation. This is verbatim from the Graph module's
    documentation. I hope you understand the algorithms involved (read
    about them in an algorithms book or online) instead of just blindly
    using them. Graph programming is 90% algorithms and data structures
    and 10% actual programming :) If you try to just do the programming
    without understanding the theory, it will be hard for you to produce
    good code, even if you use a library such as the Graph module.

    "Minimum Spanning Trees (MST)

    Minimum Spanning Trees or MSTs are tree subgraphs derived from an undirected graph. MSTs "span the graph" (covering all the vertices) using as lightly weighted (hence the "minimum") edges as possible.

    MST_Kruskal

    $mstg = $g->MST_Kruskal;

    Returns the Kruskal MST of the graph.
    MST_Prim

    $mstg = $g->MST_Prim(%opt);

    Returns the Prim MST of the graph.

    You can choose the first vertex with $opt{ first_root }.
    MST_Dijkstra
    minimum_spanning_tree

    $mstg = $g->MST_Dijkstra;
    $mstg = $g->minimum_spanning_tree;

    Aliases for MST_Prim."

    HTH
    Ted
    Ted Zlatanov, Mar 18, 2005
    #9
  10. Meng

    John Bokma Guest

    Ted Zlatanov wrote:

    > On 17 Mar 2005, wrote:
    >
    >> But how to do it by Perl Graph module?

    >
    > Read the documentation. This is verbatim from the Graph module's
    > documentation. I hope you understand the algorithms involved (read
    > about them in an algorithms book or online) instead of just blindly
    > using them. Graph programming is 90% algorithms and data structures
    > and 10% actual programming :) If you try to just do the programming
    > without understanding the theory, it will be hard for you to produce
    > good code, even if you use a library such as the Graph module.
    >
    > "Minimum Spanning Trees (MST)


    Which is not TSP. So you are right: one must understand the difference
    between TSP and MST before one replies :-D.

    The only way to get an exact solution to TSP is measuring each path that
    visits each node (each city), and keep the shortest path.

    E.g. for n cities, n! steps.

    --
    John Small Perl scripts: http://johnbokma.com/perl/
    Perl programmer available: http://castleamber.com/
    Happy Customers: http://castleamber.com/testimonials.html
    John Bokma, Mar 18, 2005
    #10
  11. Meng

    Ted Zlatanov Guest

    On 18 Mar 2005, wrote:

    Ted Zlatanov wrote:
    > On 17 Mar 2005, wrote:


    >>> But how to do it by Perl Graph module?

    >>
    >> Read the documentation. This is verbatim from the Graph module's
    >> documentation. I hope you understand the algorithms involved (read
    >> about them in an algorithms book or online) instead of just blindly
    >> using them. Graph programming is 90% algorithms and data structures
    >> and 10% actual programming :) If you try to just do the programming
    >> without understanding the theory, it will be hard for you to produce
    >> good code, even if you use a library such as the Graph module.
    >>
    >> "Minimum Spanning Trees (MST)

    >
    > Which is not TSP. So you are right: one must understand the difference
    > between TSP and MST before one replies :-D.
    >
    > The only way to get an exact solution to TSP is measuring each path that
    > visits each node (each city), and keep the shortest path.
    >
    > E.g. for n cities, n! steps.


    Of course MST is not TSP. One is a data structure, the other is a
    well-known intractable problem with only one exact solution: the
    exhaustive search method. But thanks for pointing that out.

    According to "Mastering Algorithms with Perl" by Orwant, Hietaniemi,
    and Macdonald; first edition, chapter 8, page 351:

    "[an approximate TSP solution is to] grow a MST of the vertices using
    Prim's algorithm, list the vertices in preorder, and make a cyclic
    path out of the list. This approximation is known to be no more than
    twice the length of the minimal path."

    I neglected to mention preorder, that it's not an optimal solution,
    and that you have to make the path cyclic, but those are all minor
    issues IMHO, considering the OP's needs were mainly to use the Graph
    module on a small data set.

    Or is there something else I have missed?

    Thanks
    Ted
    Ted Zlatanov, Mar 21, 2005
    #11
  12. Meng

    John Bokma Guest

    John Bokma, Mar 21, 2005
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. VB Programmer

    Travel site - travel data availability?

    VB Programmer, Nov 4, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    544
    VB Programmer
    Nov 4, 2004
  2. Replies:
    12
    Views:
    642
  3. Emilio Mayorga
    Replies:
    6
    Views:
    328
    Martien Verbruggen
    Oct 8, 2003
  4. IRR
    Replies:
    2
    Views:
    395
  5. Sean
    Replies:
    1
    Views:
    311
Loading...

Share This Page