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

[Meng]

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

 

[John Bokma]

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.

 

[m.fangtao]

Thanks John. the number of nodes is <10.

 

[John Bokma]

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.

 

[m.fangtao]

wrote:


Ah, ok,

so that means creating 9! = 362880 paths (at most) and keeping the shortest
one.

Does anybody know the solution?

 

[John Bokma]

wrote:

Does anybody know the solution?

The solution is creating all possible paths and finding the shortest

 

[m.fangtao]

But how to do it by Perl Graph module?

 

[John Bokma]

wrote:

But how to do it by Perl Graph module?

Homework?

 

[Ted Zlatanov]

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

 

[John Bokma]

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.

 

[Ted Zlatanov]

On 17 Mar 2005, (e-mail address removed) wrote:

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

 

[John Bokma]

Or is there something else I have missed?

I remember the OP stating that the number of cities is less than 10, and
that makes it quite easy to get an exact solution (9!).