diff options
Diffstat (limited to 'src')
| m--------- | src/CS340.Graph | 0 | ||||
| -rw-r--r-- | src/CS340.TSP/TSP.cs | 27 | ||||
| -rw-r--r-- | src/CS340.TSP/Tour.cs | 14 |
3 files changed, 19 insertions, 22 deletions
diff --git a/src/CS340.Graph b/src/CS340.Graph -Subproject 798aec5e24b847ce9f56ef69793b3c407cbd2a6 +Subproject 63c57d1a602694ea94b23abc7c59e2779767b6a diff --git a/src/CS340.TSP/TSP.cs b/src/CS340.TSP/TSP.cs index a37ab3d..e4306e9 100644 --- a/src/CS340.TSP/TSP.cs +++ b/src/CS340.TSP/TSP.cs @@ -15,7 +15,7 @@ namespace TSP public static Tour BruteForce(Graph<double> map, int init) { - + Map = map; Tour intialTour = new Tour(map.Vertices); GenerateTour(intialTour[init], new Tour(map.Vertices), new Tour()); @@ -25,30 +25,31 @@ namespace TSP static void GenerateTour(City city, Tour tour, Tour visited) { // create local copy of Tour variables - Tour currTour = tour.DeepCopy(); - Tour currVisited = visited.DeepCopy(); + Tour currTour = new Tour(tour.Cities); + Tour currVisited = new Tour(visited.Cities); + City currCity = new City(city); // remove current City from tour - bool removed = currTour.Cities.Remove(city); + currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.Id)); //? verify that city was removed - Debug.Assert(removed, - $"Failed to remove a city from the tour. \nTour: {tour}\nCity: {city.Id}"); + 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) { - city.Parent = currVisited.Cities.Last().Id; - city.Key = Map.Vertices[city.Id].Edges - .Where(edge => edge.V == city.Parent) + currCity.Parent = currVisited.Cities.Last().Id; + currCity.Key = Map.Vertices[currCity.Id].Edges + .Where(edge => edge.V == currCity.Parent) .Last().Weight; } - currVisited.Cities.Add(city); + currVisited.Cities.Add(currCity); //? verify that city was added - Debug.Assert(currVisited.Cities.Contains(city), - $"Failed to add a city to the tour. \nTour: {tour}\nCity: {city.Id}"); + 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 @@ -61,7 +62,7 @@ namespace TSP currVisited.Cities.First().Parent = currVisited.Cities.Last().Id; if (BestTour == null || currVisited.Weight < BestTour.Weight) - BestTour = currVisited.DeepCopy(); + BestTour = new Tour(currVisited.Cities); // Debug.Print($"{currTour}"); } diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs index 456c944..80db19d 100644 --- a/src/CS340.TSP/Tour.cs +++ b/src/CS340.TSP/Tour.cs @@ -26,18 +26,14 @@ namespace TSP // indexer: get vertex where vertex.Id == index public Vertex<T> this[int index] { get => Cities.Find(vertex => vertex.Id == index); } - public Tour(List<Vertex<T>> cities) => Cities = cities; + public Tour(List<Vertex<T>> cities) => Cities.AddRange(cities.Select(city => new Vertex<T>(city))); public Tour() => Cities = new List<Vertex<T>>(); + public Tour(Tour<T> tour) : this(tour.Cities) { } + - public Tour<T> DeepCopy() - { - Tour<T> other = (Tour<T>)this.MemberwiseClone(); - other.Cities = Cities.ConvertAll(city => city.DeepCopy()); - return other; - } public override string ToString() => - $"tour: {String.Join(" -> ", Cities.Select(city => city.Id))}\n" + - $"distance: {Weight}"; + $"tour: {String.Join(" -> ", Cities.Select(city => city.Id))}\n" + + $"distance: {Weight}"; } } |