From 66ecdbf20f2a29af26e4bfefb255e7fbe1061eac Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Fri, 23 Apr 2021 16:34:12 -0500 Subject: implimented MSTApproximate --- src/CS340.TSP/TSPSolver.cs | 110 ++++++++++++++++++++++++++++++--------------- src/CS340.TSP/Tour.cs | 2 +- 2 files changed, 76 insertions(+), 36 deletions(-) (limited to 'src/CS340.TSP') diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs index e2ea98f..567c7de 100644 --- a/src/CS340.TSP/TSPSolver.cs +++ b/src/CS340.TSP/TSPSolver.cs @@ -1,3 +1,4 @@ +using System.Collections.Generic; using System.Diagnostics; using System.Linq; using Extensions; @@ -8,69 +9,108 @@ namespace TSP { using Map = Graph, double>, Edge, double>; + using Road = Edge; public static class TSPSolver { - static Map Map { get; set; } static Tour BestTour = null; public static Tour MST(string file, string coords, int init) { - Map mst = GraphFile.Read(new FileReader(file)).MST(0); - return new Tour(mst.Vertices.OrderBy(vertex => vertex.Id).ToList(), Coordinate.Parse(coords)); + Map map = GraphFile.Read(new FileReader(file)).MST(0); + return new Tour(map.Vertices, Coordinate.Parse(coords)); } - public static Tour BruteForce(string file, string coords, int init) + public static Tour Approximate(string file, string coords, int init) { - Map = GraphFile.Read(new FileReader(file)); - Tour intialTour = new Tour(Map.Vertices, Coordinate.Parse(coords)); - GenerateTour(intialTour[init], intialTour, new Tour()); + Map map = GraphFile.Read(new FileReader(file)).MST(0); + Tour mstTour = new Tour(map.Vertices, Coordinate.Parse(coords)); + + Tour approximateTour = PreOrder(mstTour[init], mstTour, new Tour()); + + Debug.WriteLine("\nApproximate Best Tour"); + Debug.WriteLine(BestTour); + + return approximateTour; + } + + public static Tour Solve(string file, string coords, int init) + { + Map map = GraphFile.Read(new FileReader(file)); + Tour intialTour = new Tour(map.Vertices, Coordinate.Parse(coords)); + + BestTour = null; + + BruteForce(intialTour[init], intialTour, new Tour()); + + Debug.WriteLine("\nTrue Best Tour"); + Debug.WriteLine(BestTour); return BestTour; } - static void GenerateTour(City city, Tour tour, Tour visited) + public static Tour PreOrder(City city, Tour mst, Tour visited) + { + // set parent of current city to previous city + if (visited.Cities.Count > 0) + city.Parent = visited.Cities.Last().Id; + + // add current City to visited + visited.Cities.Add(city); + + // loop through each child, and recursivly traverse + foreach (Road road in city.Edges) + if (mst[road.V].Parent == city.Id) + PreOrder(mst[road.V], mst, visited); + + // on the last node, set init node's parent to the last node + if (visited.Cities.Count == mst.Cities.Count) + visited.Cities.First().Parent = visited.Cities.Last().Id; + + return visited; + } + + static void BruteForce(City cityInput, Tour unvisitedInput, Tour visitedInput) { // create local copy of Tour variables - Tour currTour = new Tour(tour.Cities); - Tour currVisited = new Tour(visited.Cities); - City currCity = new City(city); + Tour unvisited = new Tour(unvisitedInput.Cities); + Tour visited = new Tour(visitedInput.Cities); + City city = new City(cityInput); // remove current City from tour - currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.Id)); + int removed = unvisited.Cities.RemoveAll(c => c.Id == city.Id); - //? verify that city was removed - Debug.Assert(currVisited.Cities.Find(city => city.Id == currCity.Id) == null, - $"Failed to remove a city from the tour. \nTour: {tour}\nCity: {currCity.Id}"); - - // add current City to visited - if (currVisited.Cities.Count > 0) - currCity.Parent = currVisited.Cities.Last().Id; + //? verify that a single city was removed + Debug.Assert(removed == 1, + $"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city.Id}"); - currVisited.Cities.Add(currCity); + // set parent of current city to previous city + if (visited.Cities.Count > 0) + city.Parent = visited.Cities.Last().Id; - //? verify that city was added - Debug.Assert(currVisited.Cities.Find(city => city.Id == currCity.Id) != null, - $"Failed to add a city to the tour. \nTour: {tour}\nCity: {currCity.Id}"); + // add current City to visited + visited.Cities.Add(city); // loop through each city. Each level of recursion has a one less city in currTour.Cities // leaving the base case - foreach (City neighbor in currTour.Cities) - GenerateTour(neighbor, currTour, currVisited); - + foreach (City neighbor in unvisited.Cities) + BruteForce(neighbor, unvisited, visited); - if (currTour.Cities.Count == 0) + // if we traversed all cities in the graph + if (unvisited.Cities.Count == 0) { - currVisited.Cities.First().Parent = currVisited.Cities.Last().Id; - - if (BestTour == null || currVisited.Weight < BestTour.Weight) - BestTour = new Tour(currVisited.Cities); - // Debug.Print($"{currTour}"); + // add the return home + visited.Cities.First().Parent = visited.Cities.Last().Id; + + // set as best if lower weight than previous best + if (BestTour == null || visited.Weight < BestTour.Weight) + { + BestTour = new Tour(visited.Cities); + Debug.WriteLine("*** Found new best tour ***"); + Debug.WriteLine(visited); + } } - - - return; } } } diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs index 99c0f5d..27ab5a5 100644 --- a/src/CS340.TSP/Tour.cs +++ b/src/CS340.TSP/Tour.cs @@ -17,7 +17,7 @@ namespace TSP } // indexer: get vertex where vertex.Id == index - public City this[int index] { get => Cities.Find(vertex => vertex.Id == index); } + public City this[int index] { get => Cities.Find(city => city.Id == index); } public Tour() => Cities = new List(); -- cgit v1.2.3-70-g09d2