diff options
Diffstat (limited to 'src/CS340.TSP/Solve.cs')
-rw-r--r-- | src/CS340.TSP/Solve.cs | 71 |
1 files changed, 71 insertions, 0 deletions
diff --git a/src/CS340.TSP/Solve.cs b/src/CS340.TSP/Solve.cs new file mode 100644 index 0000000..dd3d306 --- /dev/null +++ b/src/CS340.TSP/Solve.cs @@ -0,0 +1,71 @@ +using System.Diagnostics; +using System.Linq; +using System.Text.RegularExpressions; +using Graph; +using Graph.IO; + +namespace TSP +{ + + using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>; + + public static class Solve + { + static Map Map { get; set; } + static Tour BestTour = null; + + public static Tour BruteForce(string file, int init) + { + Map = GraphFile.Read(new FileReader(file)); + 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 = new Tour(tour.Cities); + Tour currVisited = new Tour(visited.Cities); + City currCity = new City(city); + + // remove current City from tour + currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.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; + } + + currVisited.Cities.Add(currCity); + + //? 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}"); + + // 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 = new Tour(currVisited.Cities); + // Debug.Print($"{currTour}"); + } + + + return; + } + } +} |