ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 12 May 2020 23:30:46 +0200Traveling Salesman Problemhttps://ask.sagemath.org/question/51378/traveling-salesman-problem/ Hello!
I'm a new user of SageMath, and I have a project that have 340 different places and I want to find a route to travel across the graph but, I don't want to travel trough the 340 places.
For example, if I want to find the TSP between just 5 points, I want to use de graph to find the shortest rout for just the 5 points I want passing trough the points it need, but no the 340, only the needed ones.
Anyone can help me with that?Tue, 12 May 2020 01:35:32 +0200https://ask.sagemath.org/question/51378/traveling-salesman-problem/Comment by slelievre for <p>Hello!</p>
<p>I'm a new user of SageMath, and I have a project that have 340 different places and I want to find a route to travel across the graph but, I don't want to travel trough the 340 places.</p>
<p>For example, if I want to find the TSP between just 5 points, I want to use de graph to find the shortest rout for just the 5 points I want passing trough the points it need, but no the 340, only the needed ones.</p>
<p>Anyone can help me with that?</p>
https://ask.sagemath.org/question/51378/traveling-salesman-problem/?comment=51400#post-id-51400Can you provide the graph?Tue, 12 May 2020 23:30:46 +0200https://ask.sagemath.org/question/51378/traveling-salesman-problem/?comment=51400#post-id-51400Answer by tmonteil for <p>Hello!</p>
<p>I'm a new user of SageMath, and I have a project that have 340 different places and I want to find a route to travel across the graph but, I don't want to travel trough the 340 places.</p>
<p>For example, if I want to find the TSP between just 5 points, I want to use de graph to find the shortest rout for just the 5 points I want passing trough the points it need, but no the 340, only the needed ones.</p>
<p>Anyone can help me with that?</p>
https://ask.sagemath.org/question/51378/traveling-salesman-problem/?answer=51379#post-id-51379Here is a hint : if `V` denotes your set of 5 vertices., construct a graph whose vertices is `V` and for every par of vertices `u` and `v` of `V`, label the edge `(u,v)` with the length of the shortest path between `u` and `v` in the original graph (use the `shortest_path` method). What you want is a TSP in that reduced graph (use the `traveling_salesman_problem` method, with the option `use_edge_labels=True`.
Tue, 12 May 2020 02:44:56 +0200https://ask.sagemath.org/question/51378/traveling-salesman-problem/?answer=51379#post-id-51379Comment by raefsjo for <p>Here is a hint : if <code>V</code> denotes your set of 5 vertices., construct a graph whose vertices is <code>V</code> and for every par of vertices <code>u</code> and <code>v</code> of <code>V</code>, label the edge <code>(u,v)</code> with the length of the shortest path between <code>u</code> and <code>v</code> in the original graph (use the <code>shortest_path</code> method). What you want is a TSP in that reduced graph (use the <code>traveling_salesman_problem</code> method, with the option <code>use_edge_labels=True</code>.</p>
https://ask.sagemath.org/question/51378/traveling-salesman-problem/?comment=51382#post-id-51382Thank you for answer me!
I get what you said, and the only way I know to do that is by hand.
There's a way in which Sage made this automatically?Tue, 12 May 2020 08:45:27 +0200https://ask.sagemath.org/question/51378/traveling-salesman-problem/?comment=51382#post-id-51382