diff options
Diffstat (limited to 'src/CS340.TSP/TSPSolver.cs')
| -rw-r--r-- | src/CS340.TSP/TSPSolver.cs | 12 |
1 files changed, 8 insertions, 4 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 ***"); |