-
Notifications
You must be signed in to change notification settings - Fork 0
/
exercise4.py
139 lines (106 loc) · 4.11 KB
/
exercise4.py
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
"""
Exam 2 - MOS
Exercise 4
Made by:
Juan Andrés Romero C - 202013449
Juan Sebastián Alegría - 202011282
"""
import random
import math
def second_max_min(list, mode) -> object:
"""
Find the second max or min value in a list
Args:
list (list): List to be evaluated
mode (str): 'max' or 'min' to find the second max or min value
Returns:
object: Value found
"""
if mode == 'max':
temp_list = [x for x in list if x != max(list)]
return max(temp_list)
elif mode == 'min':
temp_list = [x for x in list if x != min(list)]
return min(temp_list)
class ZValues:
"""
Simple class to manage points and z values
"""
def __init__(self, point, z):
self.point = point
self.z = z
def __lt__(self, other):
return self.z < other.z
def __gr__(self, other):
return self.z > other.z
@classmethod
def find_z(cls, values, z):
counter = 0
for value in values:
if value.z == z.z:
return counter
counter += 1
def simplex(fev_list: list[tuple], graph: list[list], z: callable) -> tuple:
"""
Find the optimal solution for a problem with function z and
restrictions given as a list of points and their respective adjacences
Args:
fev_list (list[tuple]): List of intersections between restrictions
graph (list[list]): Adjacency matrix for the given intersections
z (callable): function to optimize
Returns:
tuple: Best point found and its respective z value
"""
selected_fev = random.choice(fev_list)
# Fill the connected nodes with the distance between them
for i in range(len(fev_list)):
for j in range(len(fev_list)):
if graph[i][j] == 1:
graph[j][i] = 1
distance = math.sqrt(
(fev_list[i][0] - fev_list[j][0])**2 + (fev_list[i][1] - fev_list[j][1])**2)
graph[i][j] = distance
graph[j][i] = distance
while True:
# Find the adjacent nodes to the selected one
index_selected_fev = fev_list.index(selected_fev)
selected_distances = graph[index_selected_fev]
closest_fev_distance = min(selected_distances)
second_closest_distance = second_max_min(selected_distances, 'min')
closest_index = selected_distances.index(closest_fev_distance)
second_closest_index = selected_distances.index(
second_closest_distance)
closest_fev = fev_list[closest_index]
second_closest_fev = fev_list[second_closest_index]
# Calculate the z value in each point
selected_z = z(selected_fev[0], selected_fev[1])
closest_z = z(closest_fev[0], closest_fev[1])
second_closest_z = z(second_closest_fev[0], second_closest_fev[1])
z_list = [ZValues(selected_fev, selected_z), ZValues(
closest_fev, closest_z), ZValues(second_closest_fev, second_closest_z)]
# Find the z value which has the best z value (greatest value)
best_z = max(z_list)
# Find the index of said z value and checking if it is the selected one, if it is, then the algorithm is done
index = ZValues.find_z(z_list, best_z)
if index == 0:
return selected_fev, selected_z
# If it is not, then the new selected node is the one with the best z value found and the process is repeated
selected_fev = best_z.point
def objective_function(x, y):
"""
Objective function to be evaluated (Specific to this problem)
"""
return 3*x + 2*y
if __name__ == "__main__":
intersection_points = [(0, 0), (40, 0), (40, 20), (20, 60), (0, 80)]
# Create graph
graph = [[9999 for _ in range(len(intersection_points))]
for _ in range(len(intersection_points))]
# Fill graph with connected nodes
graph[0][1] = 1
graph[0][4] = 1
graph[1][2] = 1
graph[2][3] = 1
graph[3][4] = 1
result = simplex(intersection_points, graph, objective_function)
print(f"The best point is: {result[0]} with a z value of {result[1]}")