Traveling Salesman Problem and Quantum Gravity

Traveling Salesman Problem and Quantum Gravity
Andre Willers
19 Nov 2010

Synopsis:
A short , fast solution to the Traveling Salesman Problem (TSP) is deduced and a potential application to quantum Gravity proposed .

Discussion :
1.Traveling Salesman Problem (TSP)
While I solved this problem in May 2005 , it was a curiosity until I saw the article in NewScientist of 25 Sept 2010 " Dimensions vanish in quantum gravity" (p14) , which can easily be related to the Suburban solution of the TSP . Hence this article .

2.TSP :
A salesman travels from city to city . Calculate his minimum route .

This is described as a Hard Problem , since the brute-force approach involves all possible combinations of n cities . In other words , the PowerSet of n .
This approaches Aleph(1) as n grows large
(see http://andreswhy.blogspot.com "Problems with Randomization" , "Randomness2" et al)
This is normally translated as uncomputable (though I do not agree) .

Constraints :
2.1 The salesman and the cities are delineated . ie Have boundaries
2.2 The salesman arrives and departs only once per city .
2.3 The salesman ends up in his starting city (the classical , circular form)

Algorithm :
Overview :
Calculate distances between pairs of all cities .
Sort the pairs of connected cities in ascending order (The Trick !).
This is only n*(n+1)/2 in speed-size . Sort algorithms are very fast .

This is a reduced PowerSet .
Do you see why our universe runs on a reduced PowerSet ?
Reducing to pairs (which the constraint or Axiom of Delineation makes possible) enables us to keep things below Aleph(1) levels .
That is why the Algorithm below is possible .
Notice the cunning use of this by Nature in Sex , DNA pairing , immune systems et al.
Anywhere you see a pairing system , it means the PowerSet is reduced and humans can understand it .

Each city can have only one Arrival and one Departure . Go down the list of increasing distances , eliminating impossibilities until all Arrival and Departure slots are filled . Then stop . The cities not eliminated are the minimum route .
The arrival and departure slots are analogous to quantum states .
Only one available is analogous to the Pauli-principle .

Detail :
Let there be n cities .
Calculate the distances between pairs of cities .
Constraint 2.3 means there are only n-1 cities for calculation purposes because city(begin)=city(end) .
There are thus numL1 = (n-1)C2 = n*(n-1)/2 combinations .
These are distances between cities .
Sort them in ascending order , smallest first .
Every Length L has a city at each end .
Let each city have a dimension City(nID1,nID2 ,nArrivalFrom , nDepartureTo)
Total of dimensions required is numL1* n^4 = of order n^6

The simple algorithm :
Let every length be different . The cities are at different distances from each other . Then the solution is simple (which is why we mention it) :
Start with the shortest length L .
Eliminate all subsequent cities with the same departure ID as first Departure city .
Eliminate all subsequent cities with the same arrival ID as first Arrival city .

Proceed to the second length and iterate .

Stop when all Arrival and Departure slots have been filled .
Identify route You have it in a very short time , as the list reduces .

This can be considerably shortened , but I keep it simple to show the principle .

More complicated :
Aha !
What if there are multiple duplications in the distances between the cities ?
Then we can easily be stuck back in the brute-force approach . If the ratio's are wrong , we might even be stuck in a Aleph(1) situation .

The Suburban Solution .The elegant Solution .
We use the constraint as set out above :
"2.1 The salesman and the cities are delineated . ie Have boundaries"

Instead of traveling from city-center to city-center , our Salesman only needs to travel to a Suburb . We arbitrarily assign the distance of the suburb from the center , so we can have unique distances . We can then use the sorting mechanism .
This is The Trick !

We know what the minimum distance between any of the cities are (we calculated it at step one) . We know how many cities there are .

We can then calculate a distance dBurbMax from the city center that , no matter what distance we assign the Salesman's suburban target offset from the city-center , the sum of these n distances cannot exceed the minimum distance between any of the cities .
Recommended :use Random walk , but make sure it is Random !

We then simply iterate the Simple Algorithm above , which gives a boundaried solution , but the biggest boundary is smaller than smallest distance between cities .

Computations :
This leads to problems if dBurbMax < Planck length or number capability of computer .

Thinking out of the circle .
(The box is so passé)
Sub-Planck lengths can be approximated by looking at elements outside the circle , but that interact inside the sub-planck circle .
Shades of the Mach principle !

Which , of course brings us to Quantum-inertia and quantum-gravity .

Inertia :
This should be manipulable by letting dBurbMax straddle the Planck-length .
Be careful of the radiation release !
(A form of Hawking radiation)

However , gravity would need manipulation of dBurbMax at sub-Planck lengths and in Beth(1+) modes .

FTL communication :
This is implied by the above . Manipulation of inertia .

FTL travel :
Maybe a bit further . A higher order of technology required .

For literary worrywarts :
Death of the Salesman will really knock things asunder .
What happens if the Postman only knocks pi times ?

Pity .
I was hoping for easy anti-gravity .

Oh well ,

Andre .

xxxxxxxxxxxxxxxxxx


Appendix A
From AW VB program TSP.vbp dated 24/5/2005
Rough programming notes for the Simple Algorithm.

Public Sub s_Doc()
'Symmetrical Travelling Salesman Problem Documentation
'1. Problem: n Nodes (Cities) are given .
'Find the minimum distances from any point returning
'to the same point,visiting each node once only.
'Symmetrical means A->B = B->A .
'Returning to the same point means that every node must have one
'arrival and one departure.
'There are m=n*(n-1)/2 links between nodes .
'For the minimum distance , n links must be chosen , ie n arrivals
'and n departures , one each per node .

'2. Algorithm
'2.1 Calc distances of links .(=set L1)
'2.2 Sort links in ascending order, keeping track of nodes involved.(=set L2)
'2.3 starting at left-hand(smallest link) , proceed link by link
'until every departure- and arrival node has been included at least once .
'2.4 This is the collection of minimum round-trips possible .(=set L3)
'2.5 The trick is now to eliminate as many of the longest distances possible.
'2.6 Starting at the right-hand of the collection L3 formed in para 2.3 above,
'goto the left hand (smallest)of L3 . If node(x) is in arrival at the
'furthest right-hand , try to find departures for the same node in the
'left-hand . Do the same for departures .
'Loop to the right-hand until number of arrival and departure
'nodes in RH are 1 or bigger.
'2.7 Goto the next one on the left of L3 and repeat .
'This gives set=L4
'2.6 The end result is the minimum distance by going from node 1 to n
'in collection L4
'2.7 Duplicate possible pathways means there are duplicate minimum lenghts.
'2.8 This is exact .
'2.9 Calculation time :
'Minimum:if there are no duplicate distances betwen any two nodes ,
'the calculation time is the sort time of L1 (para 2.2)
'Maximum:if maximum duplicate distances in every instance in L3.
'This has upper limit of ~n^4 using para's 2.6 onwards , plus minimum
'sorting time.

End Sub
xxxxxxxxxxxxxxxx