diff options
Diffstat (limited to 'src/CS340.TSP')
-rw-r--r-- | src/CS340.TSP/Program.cs | 23 | ||||
-rw-r--r-- | src/CS340.TSP/TSP.cs | 72 | ||||
-rw-r--r-- | src/CS340.TSP/Tour.cs | 43 | ||||
-rw-r--r-- | src/CS340.TSP/graphs/graph1.txt | 13 | ||||
-rw-r--r-- | src/CS340.TSP/graphs/test.txt | 6 |
5 files changed, 139 insertions, 18 deletions
diff --git a/src/CS340.TSP/Program.cs b/src/CS340.TSP/Program.cs index 3dfe855..ef9e211 100644 --- a/src/CS340.TSP/Program.cs +++ b/src/CS340.TSP/Program.cs @@ -9,6 +9,7 @@ using Interfaces; namespace TSP { using Graph = Graph<double>; + using Tour = Tour<double>; class Program { @@ -18,11 +19,23 @@ namespace TSP foreach (var item in Directory.GetFiles("graphs/")) { Graph graph = GraphFile.Read(new FileReader(item)); - Graph mst = graph.MST(0); - GraphFile.Print(mst, new ConsoleWriter()); - Console.WriteLine( - graph.Vertices.Sum(vertex => - vertex.Edges.FirstOrDefault(edge => edge.V == vertex.Parent).Weight)); + // Graph mst = graph.MST(0); + // GraphFile.Print(mst, new ConsoleWriter()); + // Console.WriteLine( + // graph.Vertices.Sum(vertex => + // vertex.Edges.FirstOrDefault(edge => edge.V == vertex.Parent).Weight)); + + Tour bruteForce = TSP.BruteForce(graph, 0); + Console.WriteLine(bruteForce); + // mst.Vertices.ForEach(vertex => + // { + // Console.Write($"{vertex.Id}"); + // vertex.Edges.ForEach(edge => Console.Write($" {edge.V} {edge.Weight.ToString("F1")}")); + // Console.WriteLine(); + // }); + // Console.WriteLine(mst.Vertices + // .Sum(vertex => vertex.Edges + // .FirstOrDefault(edge => edge.V == vertex.Parent).Weight)); } } } 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; + } + } +} diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs new file mode 100644 index 0000000..456c944 --- /dev/null +++ b/src/CS340.TSP/Tour.cs @@ -0,0 +1,43 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using Graph; + +namespace TSP +{ + + public class Tour<T> where T : IComparable<T> + { + public List<Vertex<T>> Cities { get; set; } = new List<Vertex<T>>(); + public T Weight + { + get + { + dynamic _weight = default(T); + Cities.Where(city => city.Parent != -1).ToList() + .ForEach(city => + _weight += city.Edges + .Where(edge => edge.V == city.Parent) + .First().Weight); + return _weight; + } + } + + // 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() => Cities = new List<Vertex<T>>(); + + 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}"; + + } +} diff --git a/src/CS340.TSP/graphs/graph1.txt b/src/CS340.TSP/graphs/graph1.txt deleted file mode 100644 index f31c4fd..0000000 --- a/src/CS340.TSP/graphs/graph1.txt +++ /dev/null @@ -1,13 +0,0 @@ -0 1 78.85429601486528 2 64.62197768561404 3 59.135437767890075 4 71.84705978674423 5 54.08326913195984 6 8.602325267042627 7 50.695167422546305 8 75.69015788066504 9 46.09772228646444 10 79.37883848986453 11 19.209372712298546 12 83.18653737234169 -1 0 78.85429601486528 2 93.47726996441435 3 21.095023109728988 4 28.635642126552707 5 102.55242561733974 6 72.69112738154499 7 46.861498055439924 8 76.21679604916491 9 50.20956084253277 10 9.219544457292887 11 89.02246907382428 12 55.08175741568164 -2 0 64.62197768561404 1 93.47726996441435 3 85.23496934944014 4 67.89698078707183 5 21.840329667841555 6 69.6419413859206 7 47.01063709417264 8 28.442925306655784 9 44.77722635447622 10 99.98499887483122 11 83.19254774317228 12 54.62600113499065 -3 0 59.135437767890075 1 21.095023109728988 2 85.23496934944014 4 33.54101966249684 5 90.21086409075129 6 52.392747589718944 7 39.05124837953327 8 74.10802925459562 9 40.496913462633174 10 20.248456731316587 11 68.11754546370561 12 59.77457653551382 -4 0 71.84705978674423 1 28.635642126552707 2 67.89698078707183 3 33.54101966249684 5 80.45495634204272 6 68.41052550594829 7 25.298221281347036 8 47.92702786528704 9 30.083217912982647 10 37.21558813185679 11 86.97700845625813 12 27.16615541441225 -5 0 54.08326913195984 1 102.55242561733974 2 21.840329667841555 3 90.21086409075129 4 80.45495634204272 6 61.032778078668514 7 56.22277118748239 8 49.01020301937138 9 52.40229002629561 10 107.62899237658968 11 70.61161377563892 12 72.78049189171504 -6 0 8.602325267042627 1 72.69112738154499 2 69.6419413859206 3 52.392747589718944 4 68.41052550594829 5 61.032778078668514 7 49.39635614091387 8 77.80102827083971 9 45.221676218380054 10 72.53275122315436 11 18.788294228055936 12 82.37718130647589 -7 0 50.695167422546305 1 46.861498055439924 2 47.01063709417264 3 39.05124837953327 4 25.298221281347036 5 56.22277118748239 6 49.39635614091387 8 36.345563690772494 9 5.0 10 53.0 11 68.09552114493287 12 33.015148038438355 -8 0 75.69015788066504 1 76.21679604916491 2 28.442925306655784 3 74.10802925459562 4 47.92702786528704 5 49.01020301937138 6 77.80102827083971 7 36.345563690772494 9 37.36308338453881 10 84.20213774008353 11 94.847245611035 12 27.80287754891569 -9 0 46.09772228646444 1 50.20956084253277 2 44.77722635447622 3 40.496913462633174 4 30.083217912982647 5 52.40229002629561 6 45.221676218380054 7 5.0 8 37.36308338453881 10 55.80322571321482 11 63.812224534175265 12 37.21558813185679 -10 0 79.37883848986453 1 9.219544457292887 2 99.98499887483122 3 20.248456731316587 4 37.21558813185679 5 107.62899237658968 6 72.53275122315436 7 53.0 8 84.20213774008353 9 55.80322571321482 11 87.69264507357501 12 64.00781202322104 -11 0 19.209372712298546 1 89.02246907382428 2 83.19254774317228 3 68.11754546370561 4 86.97700845625813 5 70.61161377563892 6 18.788294228055936 7 68.09552114493287 8 94.847245611035 9 63.812224534175265 10 87.69264507357501 12 101.01980003939822 -12 0 83.18653737234169 1 55.08175741568164 2 54.62600113499065 3 59.77457653551382 4 27.16615541441225 5 72.78049189171504 6 82.37718130647589 7 33.015148038438355 8 27.80287754891569 9 37.21558813185679 10 64.00781202322104 11 101.01980003939822 diff --git a/src/CS340.TSP/graphs/test.txt b/src/CS340.TSP/graphs/test.txt new file mode 100644 index 0000000..113fb4f --- /dev/null +++ b/src/CS340.TSP/graphs/test.txt @@ -0,0 +1,6 @@ +0 1 78.85429601486528 2 64.62197768561404 3 59.135437767890075 4 71.84705978674423 5 54.08326913195984 +1 0 78.85429601486528 2 93.47726996441435 3 21.095023109728988 4 28.635642126552707 5 102.55242561733974 +2 0 64.62197768561404 1 93.47726996441435 3 85.23496934944014 4 67.89698078707183 5 21.840329667841555 +3 0 59.135437767890075 1 21.095023109728988 2 85.23496934944014 4 33.54101966249684 5 90.21086409075129 +4 0 71.84705978674423 1 28.635642126552707 2 67.89698078707183 3 33.54101966249684 5 80.45495634204272 +5 0 54.08326913195984 1 102.55242561733974 2 21.840329667841555 3 90.21086409075129 4 80.45495634204272
\ No newline at end of file |