Greedy Algorithm and Travelling Salesman Problem Using Octave GNU Tool
.
1. Introduction
A greedy algorithm is the search for the optimal solution to a given problem, which can be divided into many steps and the optimal solution can be found only for the current step, which greatly simplifies calculations. In this case all options that are not optimal for this local step are discarded, which often leads to the loss of the present optimal solution. The traveling salesman problem cannot be solved using a greedy algorithm, but it is possible to obtain an approximate solution that is still better than none. The algorithm is simple and requires less computational effort than for an exact solution such as the branch and bound method or dynamic programming.
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.
Formulas (1) and (2) are similar to Bellman’s dynamic programming equations but the greedy algorithm does not iterate through all combinations at each step, as in dynamic programming, but only those that are optimal at this local step. See bellow for more information.
.
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!
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 Greedy Algorithm 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 TravellingSalesmanProblemGreedyAlg.m
-
As mentioned above, a greedy algorithm does not always give the right solution. In this example we were lucky and got optimal solutions, but we lost several of them:
1 => 3 => 4 => 2 => 1
2 => 4 => 3 => 1 => 2
3 => 4 => 2 => 1 => 3
.
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 [1]:
Solving this problem, described above by the method and using Octave Script from TravellingSalesmanProblemGreedyAlg.m, we get:
Table 3-1: Optimal Tracks for the Matrix (7)
.
2). As mentioned above, a greedy algorithm does not always give the right solution. In this example an incorrect result was found for Start City 2. The right decision:
2 => 5 => 4 => 1 => 6 => 3 => 2 with petrol 102
.
3). 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, greedy algorithm gives a win and iterates only:
If N=6 then:
4). 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, greedy algorithm also gives a win and iterates only:
If N=6 then:
.
4. Octave GNU file TravellingSalesmanProblemGreedyAlg.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)
.