diff options
-rw-r--r-- | src/CS340.TSP/City.cs | 2 | ||||
-rw-r--r-- | src/CS340.TSP/TSPSolver.cs | 121 |
2 files changed, 60 insertions, 63 deletions
diff --git a/src/CS340.TSP/City.cs b/src/CS340.TSP/City.cs index f60cc92..4889bdb 100644 --- a/src/CS340.TSP/City.cs +++ b/src/CS340.TSP/City.cs @@ -13,7 +13,7 @@ namespace TSP public partial class City : Vertex, IVertex, IComparable<INode> { - public new double Key { get => this[Parent].Weight; set => Key = value; } + public new double Key { get => this[Parent].Weight; } public Coordinate Location { get; set; } diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs index e5fd45a..24e28c2 100644 --- a/src/CS340.TSP/TSPSolver.cs +++ b/src/CS340.TSP/TSPSolver.cs @@ -14,10 +14,6 @@ namespace TSP public static class TSPSolver { - static List<int> BestTour; - static double BestWeight; - - public static Tour MST(string file, string coords, int init) { Map map = GraphFile.Read(new FileReader(file)).MST(0); @@ -35,15 +31,37 @@ namespace TSP Debug.WriteLine(approximateTour); return approximateTour; + + 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; + } } + public static Tour Solve(string file, string coords, int init) { Map map = GraphFile.Read(new FileReader(file)); Tour bestTour = new Tour(map.Vertices, Coordinate.Parse(coords)); - BestWeight = double.MaxValue; - BestTour = new(); + double BestWeight = double.MaxValue; + List<int> BestTour = new(); BruteForce(map, init, map.Vertices.Select(city => city.Id).ToList(), new List<int>(), 0); @@ -60,71 +78,50 @@ namespace TSP Debug.WriteLine(bestTour); return bestTour; - } - 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(Map map, int city, List<int> unvisitedInput, List<int> visitedInput, double weight) - { - // create local copy of Tour variables - List<int> unvisited = new(unvisitedInput); - List<int> visited = new(visitedInput); - - // remove current City from tour - int removed = unvisited.RemoveAll(c => c == city); + void BruteForce(Map map, int city, List<int> unvisitedInput, List<int> visitedInput, double weight) + { + // create local copy of Tour variables + List<int> unvisited = new(unvisitedInput); + List<int> visited = new(visitedInput); - //? verify that a single city was removed - Debug.Assert(removed == 1, - $"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city}"); + // remove current City from tour + int removed = unvisited.RemoveAll(c => c == city); - // set parent of current city to previous city - if (visited.Count > 0) - weight += map[city][visited.Last()].Weight; + //? verify that a single city was removed + Debug.Assert(removed == 1, + $"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city}"); - // add current City to visited - visited.Add(city); + // set parent of current city to previous city + if (visited.Count > 0) + weight += map[city][visited.Last()].Weight; - if (weight > BestWeight) - return; + // add current City to visited + visited.Add(city); - // 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 (int neighbor in unvisited) - BruteForce(map, neighbor, unvisited, visited, weight); + if (weight > BestWeight) + return; - // if we traversed all cities in the graph - if (unvisited.Count == 0) - { - // add the return home - weight += map[visited.First()][visited.Last()].Weight; + // 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 (int neighbor in unvisited) + BruteForce(map, neighbor, unvisited, visited, weight); - // set as best if lower weight than previous best - if (weight < BestWeight) + // if we traversed all cities in the graph + if (unvisited.Count == 0) { - BestTour = visited; - BestWeight = weight; - Debug.WriteLine("*** Found new best tour ***"); - Debug.WriteLine(String.Join(" -> ", visited)); - Debug.WriteLine(weight); + // add the return home + weight += map[visited.First()][visited.Last()].Weight; + + // set as best if lower weight than previous best + if (weight < BestWeight) + { + BestTour = visited; + BestWeight = weight; + Debug.WriteLine("*** Found new best tour ***"); + Debug.WriteLine(String.Join(" -> ", visited)); + Debug.WriteLine(weight); + } } } } |