The Travelling Salesman Game

The  Travelling Salesman Problem can be represented by a graph, to start with as one specific simply formulated problem hopefully then generalised more and more. My idea comparing this type of problem with the game of chess is really just a hunch, but a strong one. You might have a similar situation in chess when the computer plays against itself.

Unfortunately this essay is a bit long, but if you are interested should be well worth reading.

We have here a  problem in combinatorics which usually is discussed in a final year undergraduate syllabus or honours material but the ideas are not hard to understand. 

To avoid confusion I have adopted my own system where both the official terms of mathematics, and my own informal names as more descriptive and understandable, are freely used. The correct formal mathematics terms given in brackets, words more suited to chess are in inverted commas. To be referred to where there may be doubt.

A Brief summary of some Terminology used:

cities (vertices) ; journey (circuit)
line/side (edge) ; (distance/weight)
the/a solution
configuration “possible/candidate position” //
/ candidate solution (permutation)
iteration/increment/small change “move”
series/sequence of changes //
\ “consecutive moves/game”

Technical Aspects and Mathematics

Graph theory explained very loosely, in essence in discrete mathematics a graph is a collection of points (vertices) some of which connected by lines (edges). 

To give an idea of concepts, definitions and terminology in Graph Theory (not much to do with the usual idea of a graph!) to describe a graph typically properties could be completeness, directed edge or not, a path a walk, length of a path, a closed path, a circuit and so on. These ideas mostly relate well to the intuition and experience.
-

The travelling salesman is an optimization problem in which cities (labelled vertices) are connected by directed routes (edges), where the length of an edge might indicate the distance between two cities.

Thus for a circuit cities are each visited once by the travelling salesman, returning to the beginning and all the distances travelled are added which is the length of the complete journey. We want what I would like to call the actual solution as a configuration of such a graph with the smallest possible total distance travelled.

NP-complete Problems

A problem effectively depends on the time needed to solve it, for a given increasing computational load where a polynomial might be feasible an exponential growth is not, thus even for larger more and more advanced computer ability it still is not practical at all, due to limitations of hardware and program algorithms for finding an actual solution. An exponential time problem kind of blows up I illustrate the idea in an addition to this essay.

You can experiment with exponential growth and factorial functions on your scientific calculator the growth is very impressive giving rapidly increasing values with increasing variable (integer) numbers, as illustrated in the examples. An exponential order function soon totally outperforms any polynomial. As a very basic concrete example, we enumerate permutations of number plates.

Our travelling salesman problem is an example of an NP-complete problem (from Non-Polynomial), for which no known efficient, a polynomial time algorithm exists. According to the Britannica the only known general solution algorithm that guarantees the shortest path requires a solution time that grows exponentially with the the number of cities. It is an example of an NP-complete problem. 

I am not so sure about this I propose a very simple algorithm in the examples that guarantees a solution, although the computational time is strictly larger than NP. This given method grows exponentially with the problem size. 

One very interesting fact is if one NP-complete problem can be solved, (and there are many) then every NP-complete problem can be solved. There has not been an example of such existence and it has not been proved nor disproved, but of course none such  is known so it is an open question.

Routing and Chess

Comparing all possible journeys the problem very alarmingly soon explodes in complexity and becomes unmanageable with increase in number of cities as a possible amount of possible journeys. To obtain the best journey, i.e. an actual solution very soon becomes infeasible due to the non-polynomial or an exponential growth with the number of cities. However we might find satisfactory candidate solutions.

The number of possibilities, configurations is comparable to the legal chess positions attained by the rules, and I would believe similar in analysis to a given depth.

Parallels with Chess

Chess can be formulated as a mathematical problem in which the ultimate possible game is to be found, this would be finding the best first move, the best reply then the best second move and reply etc. and then going back in reverse. It is a bit confusing but in theory there has to be one, although there might be more than one such perfect game. It would then also answer the question if in a perfect game whether white or black wins, or a draw.

The rules are formulated in terms of restrictions on moves, as well as of the setting in accordance to the game, and constraints such as the chessboard. As for our problem in the setting itself for example there has to be a general triangle inequality.

However I do think the two problems are in accordance to the same principles, there are fundamental parallels between routing and chess. One should make a very thorough analysis of a typical chess program and some reverse engineering is in order.

Evaluation of Configurations

Every allowable position must be theoretically reachable from the initial one, the opening position, within the rules in question, and called a “game” as a sequence of legal moves, in routing it is a sequence of achievable configurations. An inherent difference is that in chess you cannot return to the opening position whereas in our problem you eventually must have repetition.

In Chess, within the rules calculations and evaluations must be made to lead to the best available candidate solution, taking into account calculations as tactics and positional play also, as strategy, strategy comes from experience and usually is much more subtle.

We must have some evaluation of configurations, most obvious in the travelling salesman is of course just adding distances in a given journey and comparing journeys with each other. You want the journey with smallest value, the least total distance. In Chess the evaluation of positions is much more sophisticated and has been thoroughly tested, however for our problem you should save a lot of time here. 

Your Move!

In this case as a “chess move” an increment should be a small change of the journey, I propose as an iteration ideally just a small altering of the journey changing our configuration just a little while changing the total distance the minimum.

A chess move must be chosen with discretion, it corresponds to such a decision, as an iteration, a simple change of the journey within the rules and constraints.

Any possible move then would be a small allowable change of a given position. I have found a simple method of doing such an iteration of a journey that would be the analogy of a chess move. This I describe in my last of these essays consisting of examples and explanations of the mathematics related ideas. The material is not hard to understand and is without prerequisites.
-

Note: I believe I am entitled to copyright, and also own a share of intellectual property rights if of my ideas prove to be original and are implemented.