1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
using System.Diagnostics;
using System.Linq;
using Extensions;
using Graph;
using Graph.IO;
namespace TSP
{
using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>;
using Road = Edge<double>;
public static class TSPSolver
{
static Tour BestTour;
public static Tour MST(string file, string coords, int init)
{
Map map = GraphFile.Read(new FileReader(file)).MST(0);
return new Tour(map.Vertices, Coordinate.Parse(coords));
}
public static Tour Approximate(string file, string coords, int init)
{
Map map = GraphFile.Read(new FileReader(file)).MST(0);
Tour mstTour = new Tour(map.Vertices, Coordinate.Parse(coords));
Tour approximateTour = PreOrder(mstTour[init], mstTour, new Tour());
Debug.WriteLine("\nApproximate Best Tour");
Debug.WriteLine(BestTour);
return approximateTour;
}
public static Tour Solve(string file, string coords, int init)
{
Map map = GraphFile.Read(new FileReader(file));
Tour intialTour = new Tour(map.Vertices, Coordinate.Parse(coords));
BestTour = new();
BruteForce(intialTour[init], intialTour, new Tour());
Debug.WriteLine("\nTrue Best Tour");
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(City cityInput, Tour unvisitedInput, Tour visitedInput)
{
// create local copy of Tour variables
Tour unvisited = new(unvisitedInput.Cities);
Tour visited = new(visitedInput.Cities);
City city = new(cityInput);
// remove current City from tour
int removed = unvisited.Cities.RemoveAll(c => c.Id == city.Id);
//? verify that a single city was removed
Debug.Assert(removed == 1,
$"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city.Id}");
// 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);
if (visited.Weight > BestTour.Weight)
return;
// 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 (City neighbor in unvisited.Cities)
BruteForce(neighbor, unvisited, visited);
// if we traversed all cities in the graph
if (unvisited.Cities.Count == 0)
{
// add the return home
visited.Cities.First().Parent = visited.Cities.Last().Id;
// set as best if lower weight than previous best
if (visited.Weight < BestTour.Weight)
{
BestTour = new Tour(visited.Cities);
Debug.WriteLine("*** Found new best tour ***");
Debug.WriteLine(visited);
}
}
}
}
}
|
