diff options
Diffstat (limited to 'src/CS340.TSP')
-rw-r--r-- | src/CS340.TSP/TSPSolver.cs | 12 | ||||
-rw-r--r-- | src/CS340.TSP/Tour.cs | 11 |
2 files changed, 16 insertions, 7 deletions
diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs index 159286a..2700bc2 100644 --- a/src/CS340.TSP/TSPSolver.cs +++ b/src/CS340.TSP/TSPSolver.cs @@ -12,7 +12,7 @@ namespace TSP public static class TSPSolver { - static Tour BestTour = null; + static Tour BestTour; public static Tour MST(string file, string coords, int init) @@ -39,7 +39,7 @@ namespace TSP Map map = GraphFile.Read(new FileReader(file)); Tour intialTour = new Tour(map.Vertices, Coordinate.Parse(coords)); - BestTour = null; + BestTour = new(); BruteForce(intialTour[init], intialTour, new Tour()); @@ -66,7 +66,7 @@ namespace TSP // 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; } @@ -91,6 +91,10 @@ namespace TSP // add current City to visited visited.Cities.Add(city); + + if (visited.Weight > BestTour.Weight) + return; + // loop through each city. Each level of recursion has a one less city in unvisited.Cities // so each loop is (n - 1)! down to n == 0 as the base case foreach (City neighbor in unvisited.Cities) @@ -103,7 +107,7 @@ namespace TSP visited.Cities.First().Parent = visited.Cities.Last().Id; // set as best if lower weight than previous best - if (BestTour == null || visited.Weight < BestTour.Weight) + if (visited.Weight < BestTour.Weight) { BestTour = new Tour(visited.Cities); Debug.WriteLine("*** Found new best tour ***"); diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs index 27ab5a5..a4ef10f 100644 --- a/src/CS340.TSP/Tour.cs +++ b/src/CS340.TSP/Tour.cs @@ -11,9 +11,14 @@ namespace TSP public List<City> Cities { get; set; } = new List<City>(); public double Weight { - get => Cities - .Where(city => city.Parent != -1) - .Sum(city => city.Key); + get + { + if (Cities.Count == 0) + return double.MaxValue; + + return Cities.Where(city => city.Parent != -1) + .Sum(city => city.Key); + } } // indexer: get vertex where vertex.Id == index |