Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
Sterten
Posts:
65
Registered:
12/13/04
|
|
traveling salesmen problem
Posted:
Oct 18, 2012 10:17 PM
|
|
this is a variation of the traveling salesman problem which I think
is more practical and more important. Maybe it is known under
a different name ?
In the original problem, suppose (equivalent descriptions)
----------------------------
the salesman is always allowed
to return to a previously visited city at zero cost
at which time the cities visited between these 2
events are removed from the list
-----------------------------
Or the transportation of the thing that he sells is much more
expensive than transporting himself.
-----------------------------------
Or he can hire a sub-salesman at any point who visits
one remote region while he visits the rest. The sub-salesman
needn't return, just deliver the product and can recruit
sub-sub-salesmen etc
----------------------------------------------------------
or connect every city from a list with the oil-source
by a pipeline and minimize the total length of pipelines
-----------------------------------------------------------------
or trying to sort genetic sequences
into an evolution tree : giving n sequences with known mutual
genetic distances, find a tree whose vertices are the sequences
such that the sum of the distances of joined vertices is minimal.
---------------------------------------
is that problem known ? What's the name,
where to find something about it ?
|
|
|
|
