11481

Constrained Optimal Routes in 3D Space

Given a set of constraints, what is an optimal travel route between given points? Such problems are usually posed in 2D or on a surface; for example, finding the shortest path through a set of points on the surface of Earth. This Demonstration highlights a subset of such optimization problems in 3D, as might be needed in outer space or under water.
Imagine you need to travel on a spaceship to land on several different planets, exactly once each. This would be the traveling salesman problem if you were not subject to a constraint. For example, the more fuel you carry the less cargo you can have, so it is advantageous to limit the ship’s carrying fuel capacity. Therefore you might have to refuel on different planets, but remote planets might not be accessible. You will be able to traverse only a so-called "percolation network," where an edge exists only between planets close enough to travel between without refueling. An optimal tour on such a network is different (if possible at all) from the traveling salesman tour. This Demonstration visualizes the difference between these cases.
In the limit, for very large settings of the "range" control, the routes on the percolation network and traveling salesman route coincide.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Controls
“range” sets how far the spaceship can travel without refueling. Hence it defines which planets can be reached from a given one.
“new” generates a new random set of planets.
“number” defines how many planets are on the route.
“constrained” shows the shortest tour on the percolation network. If there is no route shown even with the control checked, then it does not exist.
“optimal” shows the traveling salesman route.
“network” shows the percolation network or distances between nearest-neighbor planets that you can travel to without refueling.
“nodes” shows the nodes of the network, in this case planets.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2017 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+