Closed lutzzdias closed 8 months ago
I'll describe the logic I've done so far, the idea is to document, help myself, help Alexandre and maybe use this as reference for asking the professor for help.
Currently, we pre-calculate the lower bound when we create an empty solution, this is done in the problem:
For every city:
1.1. Get all distances in the same row of that city -> distance from current city to others
1.2. Sort the row distances and store the sorted ids of the cities in the shortest_out
matrix
1.3. Repeat, but for columns -> distance from other cities to current city
1.4. Sum the shortest possible value of in
and out
cities and store it in raw_lower_bound
divide raw_lower_bound
by 2 (for every city we are adding the in
and out
values, which results in 2x the actual bound)
return the result.
When we add a new component to the solution, we must update the lower_bound_value
. This is done in a separate function (_update_lower_bound
), these are the steps currently being taken:
shortest_in
value for the last city added (e.g. arc[1]
)shortest_out
value for the before last city (e.g. arc[0]
)shortest_in
(distance_matrix[shortest_in][arc[1]]
)shortest_out
(distance_matrix[arc[0]][shortest_out]
)(shortest_in_distance + shortest_out_distance) / 2
distance_matrix[arc[0]][arc[1]]
)arc[0]
as current_shortest_in
7.1. TODO - Update lower bound value
7.2. increment current_shortest_in
(will point to the next closest city)
7.3. TODO - verify if next closest city is valid for lbarc[1]
as current_shortest_out
lower_bound_value
This is (almost 100%) done. I'll not open a PR because, due to changes in the file structure, git stopped recognizing the original file. I'll create another issue for fixing this and adding the lower bound.
Current lower bound is equal to distance travelled. This issue relates to refactoring the current bound to follow this logic: