Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Subject
- Posted on
posted on
March 17, 2005, 1:29 am
March 17, 2005, 1:29 am
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
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
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
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
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.
--
John Small Perl scripts: http://johnbokma.com/perl/
Perl programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
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.
>
> --
> John Small Perl scripts: http://johnbokma.com/perl/
> Perl programmer available: http://castleamber.com/
> Happy Customers: http://castleamber.com/testimonials.html
Does anybody know the solution?
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
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
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
wrote:
> But how to do it by Perl Graph module?
Homework?
--
John Small Perl scripts: http://johnbokma.com/perl/
Perl programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
On 17 Mar 2005, m.fangtao@genesis.co.nz 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
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
Ted Zlatanov wrote:
> On 17 Mar 2005, m.fangtao@genesis.co.nz 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
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
On 18 Mar 2005, postmaster@castleamber.com wrote:
Ted Zlatanov wrote:
> On 17 Mar 2005, m.fangtao@genesis.co.nz 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
Re: How to use Perl Graph module to solve travel salesperson problem (TSP)?
Ted Zlatanov wrote:
> 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!).
--
John Small Perl scripts: http://johnbokma.com/perl/
Perl programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
Site Timeline
- » FAQ 1.3 Which version of Perl should I use?
- — Next thread in » PERL Discussions
- » Regex - every character but "
- — Previous thread in » PERL Discussions
- » s suffix question
- — Newest thread in » PERL Discussions
- » SSD partition alignment revisited
- — The site's Newest Thread. Posted in » Computer Hardware