Dynamic Programming and Travelling Salesman Problem Using Octave GNU Tool
.
1. Introduction
Dynamic programming was developed by Richard Bellman (see the [1], [2]) in the fifties of the twentieth century and occupies an important place for solving optimization problems, as well as problems of calculus of variations.
Dynamic programming is the search for the optimal solution to a given problem, which can be divided into many steps and search for the optimal solution only for the current step, which greatly simplifies calculations. Sometimes we can talk about a purposeful search of possible options with an assessment of their optimality, while the complexity of the task decreases compared to a complete search of all options.
Suppose there is a process of N steps. At each step the winning function (or cost function) is set: g(x,y), where x is the state at step (i–1), y is the state at step i. The calculation is performed using the formula:
where i = 2…N
In the first step the function f(x) is calculated using the formula:
The maximum in (1) is taken if g(x,y) is a winning function and it must be maximized, and the minimum is taken if g(x,y) is a cost function and it must be minimized. The function f(x) determines the optimal solution for the current step.
.
2. Travelling Salesman Problem
The traveling salesman problem is formulated as follows. There are N cities. Leaving one of the cities, the traveling salesman must visit each city once, and then return to the starting city. At the same time the total distance traveled should be minimal. If the starting city is fixed, then a complete search of all options is (N-1)! If the choice of the initial city is arbitrary, then a complete search of all the options will be N!
Note
The dynamic programming method reduces the iteration of options by dividing the task into steps. See below.
Let’s take for example 4 cities, the distance between which is shown in Figure 2-1:
Figure 2-1: Four Cities and the Distances between them
The distance between cities can be set as a matrix:
For Figure 2-1 the matrix will look like:
Now we will choose the first city as the starting city. Then:
Figure 2-2: Optimal Decision with Dynamic Programming for the Four Cities
From (2) we calculate the first step of the f(x):
To calculate the function f(x) for the next second step, the formula (1) is used.
Track: 1 => 2. From city 2 it is possible to go to city 3 or 4:
Track: 1 => 3. From city 3 it is possible to go to city 2 or 4:
Track: 1 => 4. From city 4 it is possible to go to city 2 or 3:
Now let’s move on to step 3.
Track: 1 => 2 => 4. From city 4 it remains possible to go only to city 3:
Track: 1 => 3 => 2. From city 2, it remains possible to go only to city 4:
Now let’s move on to the last step 4, returning to the first (initial) city:
Track: 1 => 2 => 4 => 3. From city 3 we return to the original city 1:
Track: 1 => 3 => 2 => 4. From city 4 we return to the original city 1:
Track: 1 => 4 => 2 => 3. From city 3 we return to the original city 1:
If we start from city 1, then go through all the cities and then go back to the first city. The optimal solution would be:
Note
If we repeat all these calculations for different starting cities, we will get the following optimal solutions:
Table 2-1: Optimal Tracks for the Matrix (4)
See also Octave Script from TravellingSalesmanProblem.m
.
3. Notes and Conclusions
1). In the traveling salesman problem (4) in the previous section a symmetric matrix was used. The elements of this matrix are the distance between cities i and j. It is clear that the distance between cities i and j is equal to the distance between cities j and i. The result is a symmetric matrix. Another assignment of this matrix is possible. For example, we will set the fuel consumption required for a trip from city i to j. In this case, the fuel consumption for the trip from city j to i will be different. This is due to the fact that the road from city i to city j, for example, goes uphill, and when driving from city j to city i, the road will go downhill and fuel consumption will be less. The result is an asymmetric matrix. Next I will use an asymmetric matrix for the traveling salesman problem from [3]:
Solving this problem, described above by the method and using Octave Script from TravellingSalesmanProblem.m, we get:
Table 3-1: Optimal Tracks for the Matrix (7)
2). If the starting city is fixed, then a complete search of all options:
(N-1)! (8)
In example (7): N=6, then (6 – 1)! = 120
At the same time, dynamic programming gives a win and iterates only:
If N=6 then:
3). If the starting city is not fixed, then a complete search of all options:
N! (10)
If N=6, then 6! = 720
In this case, dynamic programming also gives a win and iterates only:
If N=6 then:
.
4. Octave GNU file TravellingSalesmanProblem.m
The script solves the traveling salesman problem for a fixed and arbitrary starting city:
% Travelling Salesman Problem with Fixed Start Point
% Input:
% distanceMatrix – distance matrix between points
% startPoint – start point
% Output parameters:
% track – optimal point track
% distance – optimal distance
function [track distance] = TravellingSalesmanPrblmWithFixedStart(distanceMatrix, startPoint)
% Travelling Salesman Problem
% Input:
% distanceMatrix – distance matrix between points
% Output parameters:
% distance – optimal distance value
% y_output_result – optimal point track for each start points
% f_output_result – optimal distance for each start points
function [distance y_output_result f_output_result] = TravellingSalesmanPrblm(distanceMatrix)
.