diff options
Diffstat (limited to 'src/CS340.TSP/TSP.cs')
-rw-r--r-- | src/CS340.TSP/TSP.cs | 72 |
1 files changed, 72 insertions, 0 deletions
diff --git a/src/CS340.TSP/TSP.cs b/src/CS340.TSP/TSP.cs new file mode 100644 index 0000000..a37ab3d --- /dev/null +++ b/src/CS340.TSP/TSP.cs @@ -0,0 +1,72 @@ +using System; +using System.Diagnostics; +using System.Linq; +using Graph; + +namespace TSP +{ + using City = Vertex<double>; + using Tour = Tour<double>; + + public static class TSP + { + static Tour BestTour = null; + static Graph<double> Map; + + public static Tour BruteForce(Graph<double> map, int init) + { + + Tour intialTour = new Tour(map.Vertices); + GenerateTour(intialTour[init], new Tour(map.Vertices), new Tour()); + + return BestTour; + } + + static void GenerateTour(City city, Tour tour, Tour visited) + { + // create local copy of Tour variables + Tour currTour = tour.DeepCopy(); + Tour currVisited = visited.DeepCopy(); + + // remove current City from tour + bool removed = currTour.Cities.Remove(city); + + //? verify that city was removed + Debug.Assert(removed, + $"Failed to remove a city from the tour. \nTour: {tour}\nCity: {city.Id}"); + + // add current City to visited + if (currVisited.Cities.Count > 0) + { + city.Parent = currVisited.Cities.Last().Id; + city.Key = Map.Vertices[city.Id].Edges + .Where(edge => edge.V == city.Parent) + .Last().Weight; + } + + currVisited.Cities.Add(city); + + //? verify that city was added + Debug.Assert(currVisited.Cities.Contains(city), + $"Failed to add a city to the tour. \nTour: {tour}\nCity: {city.Id}"); + + // 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); + + + if (currTour.Cities.Count == 0) + { + currVisited.Cities.First().Parent = currVisited.Cities.Last().Id; + + if (BestTour == null || currVisited.Weight < BestTour.Weight) + BestTour = currVisited.DeepCopy(); + // Debug.Print($"{currTour}"); + } + + + return; + } + } +} |