From 8b7289fddf3224710165e3ad73f15709ac331821 Mon Sep 17 00:00:00 2001 From: Skullheadx <704277@pdsb.net> Date: Wed, 28 Dec 2022 15:22:01 -0500 Subject: [PATCH] MST + explanation + lower bound + one tree added --- README.md | 28 ++++++++++++++++++++++ display.py | 64 ++++++++++++++------------------------------------ graph.py | 68 ++++++++++++++++++++++++++++++++++++------------------ main.py | 21 +++++++++-------- 4 files changed, 101 insertions(+), 80 deletions(-) diff --git a/README.md b/README.md index 97d518f..594d0c8 100644 --- a/README.md +++ b/README.md @@ -22,3 +22,31 @@ By checking every single possibility and calculating the distance of each route, **Method 2: Nearest Neighbor (NN) Heuristic** If we start at any town and find the closest town that we haven't been to yet and continue this until all the cities have been visited, this creates a complete tour. + +-------------------------------------------------------------------------------------------------------------- +**Lower Bound and the Optimal Solution** + +In the case of the TSP, finding the optimal solution for a large number of nodes can end up taking too much time to compute, meaning that we have nothing to compare our heuristic solutions to. +This is where the **Minimum Spanning Tree (MST)** comes in. +_The minimum spanning tree is the set of edges that connects all the nodes with the minimum cost (in the case of the TSP, the costs is the distance between nodes) and no cycles._ +**For example:** A graph with 4 nodes: A,B,C,D at (0,0), (0,10), (20,0), (20,10) respectively on the Cartesian Plane will have a MST of 40.0. +This is because the MST only needs to connect all the nodes in the shortest distance possible, which in this case would be the edges AB + BC + CD. There is also another MST that is equally good which is simply AB + AD + CD. + +![img_1.png](img_1.png) + +The usefulness of the MST lies in the fact that the optimal tour which in the case of the example above is highlighted in green, is always greater than the MST. +`MST Cost < Optimal Tour Cost` Since we are not trying to find the optimal, but a solution that is good enough and that we can calculate within a reasonable amount of time (heuristic solution) we can compare our solution to the minimum spanning tree and get an approximation ratio. + +Take this graph for instance. The grey circles represent nodes or towns in the TSP, the blue line represents the Nearest Neighbor heuristic solution and the red line represents the MST. +![](NN_Heuristic+MST.png) + +By calculating each of the distances in the MST, we can determine that the `length of the MST is approximately 1360.299` and the `length of the tour is approximately 1,994.528`. We can now determine the approximation ratio by simply dividing the tour distance by the MST distance. + +`1,994.528 / 1360.299 = 1.466` + +`1.466 * 100% - 100% = 46.6% ` + +By manipulating the result, we can determine how much our solution overshot the lower bound. +Of course this value does not represent to a high degree of accuracy how much we overshot the optimal solution, but it does give us ballpark numbers. +In this case, the approximation ratio is `46.6%` of the MST. +(As an exercise to the reader, can you determine why this is the MST?) diff --git a/display.py b/display.py index 3f3d5f0..d6ec8d5 100644 --- a/display.py +++ b/display.py @@ -1,7 +1,5 @@ import pygame import math -from graph import distance -from queue import PriorityQueue pygame.init() @@ -14,40 +12,6 @@ RED = (255, 0, 0) GREEN = (0, 255, 0) -def find_MST(route: list) -> list: - q = PriorityQueue() - head = route[0] - seen = set() - mst = [] - for town in route: - q.put((distance(town, head), head, town)) - while not q.empty(): - d, start, end = q.get() - if end in seen: - continue - seen.add(end) - - mst.append((start, end)) - - for town in route: - q.put((distance(town, end), end, town)) - - return mst - - -def find_one_tree(route: list): - removed_vertex = route[0] - mst = find_MST(route[1:-1]) - distances = [] - for town in route[1:-1]: - distances.append((distance(removed_vertex, town), town)) - distances.sort() - mst.append((distances[0][1], removed_vertex)) - mst.append((distances[1][1], removed_vertex)) - - return mst, removed_vertex - - class Node: background_colour = GRAY outline_colour = BLACK @@ -110,7 +74,7 @@ class Salesman: class Display: pygame.display.set_caption("Traveling Salesman Problem") - def __init__(self, path: str, route: list) -> None: + def __init__(self, path: str, route: list, mst=None, one_tree=None, removed_vertex=None) -> None: with open(path, "r") as f: contents = f.read().split("\n") if contents[-1] == "": @@ -123,8 +87,9 @@ class Display: self.route = route self.salesman = Salesman(self.route) - self.mst = find_MST(route[:-1]) - self.ot, self.ot_removed_point = find_one_tree(route) + self.mst = mst + self.one_tree = one_tree + self.removed_vertex = removed_vertex def update(self, delta: float) -> None: self.salesman.update(delta) @@ -142,19 +107,24 @@ class Display: self.salesman.update(delta) self.screen.fill(WHITE) - - pygame.draw.circle(self.screen, BLUE, self.ot_removed_point, 15) - - if len(self.route) > 1: - for line in self.ot: # One Tree + if self.one_tree is not None: + pygame.draw.circle(self.screen,BLUE,self.removed_vertex,15) + for line in self.one_tree: # One Tree start, end = line pygame.draw.line(self.screen, GREEN, start, end, 12) + if self.mst is not None: for line in self.mst: # Minimum Spanning Tree start, end = line - pygame.draw.line(self.screen, RED, start, end, 7) - pygame.draw.aalines(self.screen, BLUE, True, self.route) # Route + pygame.draw.line(self.screen, RED, start, end, 8) + + if len(self.route) > 1: + pygame.draw.lines(self.screen, BLUE, True, self.route, 3) # Route + for node in self.nodes: node.draw(self.screen) - self.salesman.draw(self.screen) + # self.salesman.draw(self.screen) + pygame.display.update() delta = clock.tick(60) / 1000 # Seconds + # pygame.image.save(self.screen, "NN Heuristic + MST.png") + # quit() diff --git a/graph.py b/graph.py index 9b95c4f..e6f24fa 100644 --- a/graph.py +++ b/graph.py @@ -84,7 +84,7 @@ def print_info(route: list, time: float, method_name: str, one_tree: float, one_ f""" Traveling Salesman Problem Method Used: {method_name} -Approximation ratio: {round(d/one_tree * 100 - 100,r)}% +Approximation ratio: {round(d / one_tree * 100 - 100, r)}% Time Used: {round(time, r):,} seconds Number of Nodes: {(len(route) - 1):,} Distance: {round(d, r):,} @@ -112,35 +112,57 @@ MST cost <= cost(T) """ -def find_MST(graph: list) -> float: - mst = 0.0 +def find_one_tree(graph: list, removed_vertex_index=0): + removed_vertex = graph[removed_vertex_index] + g = graph[:removed_vertex_index] + graph[removed_vertex_index + 1:] + mst_distance, mst = find_MST(g) + distances = [] + for town in g: + distances.append((distance(removed_vertex, town), town)) + distances.sort() + # Add the two closest nodes to the removed node + mst.append((removed_vertex, distances[1][1])) + mst.append((removed_vertex, distances[0][1])) + + one_tree_distance = mst_distance + distances[1][0] + distances[0][0] + return one_tree_distance, mst + + +def find_lower_bound(graph: list): + lower_bound = None + lowest_one_tree = [] + rm_vertex = None + + for removed_vertex_index in range(len(graph)): + one_tree_distance,one_tree= find_one_tree(graph,removed_vertex_index) + + if lower_bound is None or one_tree_distance > lower_bound: + lower_bound = one_tree_distance + lowest_one_tree = one_tree[:] + rm_vertex = graph[removed_vertex_index] + return lower_bound, lowest_one_tree, rm_vertex + + +def find_MST(graph: list): q = PriorityQueue() head = graph[0] - seen = set() + seen = {head} + mst = [] + mst_distance = 0.0 for town in graph: - q.put((distance(town, head), head, town)) - while not q.empty(): + if town != head: + q.put((distance(town, head), head, town)) + while not q.empty() and len(mst) < len(graph) - 1: d, start, end = q.get() if end in seen: continue seen.add(end) - mst += d - for town in graph: - q.put((distance(town, end), end, town)) - return mst + mst.append((start, end)) + mst_distance += d -def find_one_tree(graph: list) -> float: - lower_bound = None + for town in graph: + if town != end: + q.put((distance(town, end), end, town)) - for removed_vertex in graph: - g = graph[:graph.index(removed_vertex)] + graph[graph.index(removed_vertex) + 1:] - mst = find_MST(g) - distances = [] - for town in g: - distances.append(distance(removed_vertex, town)) - distances.sort() - d = mst + distances[1] - if lower_bound is None or d < lower_bound: - lower_bound = d - return lower_bound + return mst_distance, mst diff --git a/main.py b/main.py index c9bb496..fc2d7d5 100644 --- a/main.py +++ b/main.py @@ -1,4 +1,4 @@ -from graph import create, read, print_info, find_MST, find_one_tree +from graph import create, read, print_info, find_MST, find_one_tree, find_lower_bound from display import Display from brute_force import brute_force from nearest_neighbor import nearest_neighbor @@ -6,12 +6,11 @@ from time import perf_counter import os GRAPH_PATH = "graphs/" -DELETE_PREVIOUS_FILES = True -CREATE_NEW_GRAPHS = True +CREATE_NEW_GRAPHS = False def main(): - if DELETE_PREVIOUS_FILES: + if CREATE_NEW_GRAPHS: for root, dirs, files in os.walk("graphs/"): for name in files: path = os.path.join(root, name) @@ -22,7 +21,7 @@ def main(): print("The file does not exist") if CREATE_NEW_GRAPHS: - graph, filename = create(GRAPH_PATH, 640, 640, 50) + graph, filename = create(GRAPH_PATH, 640, 640, 10) else: filename = "graph1.txt" graph = read(GRAPH_PATH, filename) @@ -32,15 +31,17 @@ def main(): route = nearest_neighbor(graph) # 100 nodes in 0.5762094999663532 seconds. Distance = 6,270.568142156188 route_time_end = perf_counter() - # MST = find_MST(graph) + MST_distance, MST = find_MST(graph) + print("MST_DISTANCE:", MST_distance) one_tree_time_start = perf_counter() - one_tree = find_one_tree(graph) + # one_tree_distance, one_tree = find_one_tree(graph) + lower_bound, one_tree, removed_vertex = find_lower_bound(graph) one_tree_time_end = perf_counter() - print_info(route, route_time_end - route_time_start, "NN Heuristic", one_tree, - one_tree_time_end - one_tree_time_start, r=3) + print_info(route, route_time_end - route_time_start, "NN Heuristic", lower_bound, + one_tree_time_end - one_tree_time_start, r=3000) - display = Display(os.path.join(GRAPH_PATH, filename), route) + display = Display(os.path.join(GRAPH_PATH, filename), route, mst=MST, one_tree=None, removed_vertex = removed_vertex) display.show() -- 2.54.0