TSP-python/greedy.py at master · justdodo27/TSP-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import numpy as np
from math import sqrt


def calc_dist(x1: float, y1: float, x2: float, y2: float):
    return sqrt((x1-x2)**2 + (y1-y2)**2)


# def find_min(ind, data): # to zakomentowane to raczej zle xD
#     for index in range(len(data)):
#         if not np.array_equal(data[ind], data[index]):
#             tmp_min = calc_dist(data[ind][0], data[ind][1], data[index][0], data[index][1])
#             tmp_index = index
#             break
#     for index in range(len(data)):
#         next_min = calc_dist(data[ind][0], data[ind][1], data[index][0], data[index][1])
#         if next_min < tmp_min and next_min != 0:
#             tmp_min = next_min
#             tmp_index = index
#     return tmp_min, tmp_index
#
#
# def main(data):
#     dist = 0
#     current_pos = 0
#     while len(data) > 1:
#         to_add, current_pos = find_min(current_pos, data)
#         dist += to_add
#         data = np.delete(data, current_pos, axis=0)
#     return dist
def find_min(curr_pnt, data, vis):
    for index in range(len(data)):
        if not np.array_equal(data[curr_pnt], data[index]) and index not in vis:
            tmp_min = calc_dist(data[curr_pnt][0], data[curr_pnt][1], data[index][0], data[index][1])
            tmp_index = index
            break
    for index in range(len(data)):
        next_min = calc_dist(data[curr_pnt][0], data[curr_pnt][1], data[index][0], data[index][1])
        if index not in vis and tmp_min > next_min > 0:
            tmp_min = next_min
            tmp_index = index
    return tmp_min, tmp_index


def main(data):
    pos = 0
    dist = 0
    vis = set()
    vis.add(pos)
    path = [pos+1]
    coordinates = [data[pos]]
    while len(vis) < len(data):
        to_add, pos = find_min(pos, data, vis)
        dist += to_add
        vis.add(pos)
        path.append(pos+1)
        coordinates.append(data[pos])
    dist += calc_dist(data[0][0], data[0][1], data[pos][0], data[pos][1])
    path.append(path[0])
    coordinates.append(data[0])
    coordinates = np.array(coordinates)
    coordinates = np.transpose(coordinates)
    return dist, path, coordinates


if __name__ == "__main__":
    cities = np.array([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]], dtype=np.float32)
    print(main(cities))