Implement TSP - brute force

[DamianJaskolski95]

Create new directory for TSP algorithms. First one will be brute force up to 8 nodes (cities). Theory of TSP: https://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera https://en.wikipedia.org/wiki/Travelling_salesman_problem

How to approach the problem:

1. You need to create 'list of lists' (list[n][n]) where you can store values of passing from one node (city) to another nodes (cities). You can see structure in tsp_data/atsp/test4.atps or other files there. First line is number of cities (n). Then you can create list of lists (list[n][n]). In the above case its list[4][4]. Its best to implement reading from file, but you can generate this data. Value form city 1 to 1 is 0 (2 to 2 is also 0, 3 to 3 is 0, etc.)

2. You will need list[n] (list[4]) with boolean values, to track what city you already visited. You will start in first city, so list[0] always will be 0.

3. You will need current path, so another list[n] with number of the city you need to visit in order.

4. Remember to always count coming back from last city to first (value of list[x][0]).

Pseudocode:

4
0 2 8 50
23 0 44 12
35 67 0 12
21 51 2 04

1. Create list = [0] * 4 
~ values = [0, 0, 0, 0]
2. Create list of lists
for i in range(0, 4):
    values[i] = [0] * 4
~ list = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
3. Copy data to values
~ values = [[0, 2, 8, 50], [23, 0, 44, 12], [35, 67, 0, 12], [21, 51, 2, 0]]
4. Create list of booleans - visited[4]
visited = [False] * 4
~ visited =  [False, False, False, False]
5. Create first city as visited
visited[0] = True
6. Create order of the cities.
final_path = [0] * 5 (its one more city since you need to go back do city 0)

Above pseudocode will be valid to most of algorithms. Pseudocode for brute force:

1. Generate part_path:
part_path = [0, 1, 2, 3, 0]
2. Count part_result for part_path:
part_result = 0
0 -> 1 = values[0][1] = 2
part_result += values[0][1]
1 -> 2 = values[1][2] = 67
part_result += values[1][2]
2 -> 3 = values[2][3] = 2
part_result += values[2][3]
3 -> 0 = values[3][0] = 50
part_result += values[3][0]
part_result = 121
3. Check if final_result > part_result, if yes final_result = part_result, and final_path = part_path
4. Go to step one until you check all part_paths.

Amount of different paths will be (n-1)! In this case its (4-1)! = 6

0 1 2 3 0
0 1 3 2 0
0 2 1 3 0
0 2 3 1 0
0 3 1 2 0
0 3 2 1 0

So you need to count values for all these paths to find the best. In Brute Force there is no need to keep track of visited cities, since you will check all paths anyway.

[DamianJaskolski95]

I presented example of creating all different paths:

0 1 2 3 0
0 1 3 2 0
0 2 1 3 0
0 2 3 1 0
0 3 1 2 0
0 3 2 1 0

in https://github.com/matthias152/algorithms/tree/permutations branch. It's called permutations in math.