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
120
121
122
123
124
125
126
127
128
129
130
131
132
|
using System;
using System.Collections.Generic;
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 List<int> BestTour;
static double BestWeight;
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(approximateTour);
return approximateTour;
}
public static Tour Solve(string file, string coords, int init)
{
Map map = GraphFile.Read(new FileReader(file));
Tour bestTour = new Tour(map.Vertices, Coordinate.Parse(coords));
BestWeight = double.MaxValue;
BestTour = new();
BruteForce(map, init, map.Vertices.Select(city => city.Id).ToList(), new List<int>(), 0);
int parent = BestTour.Last();
foreach (int city in BestTour.Skip(1))
{
bestTour[city].Parent = parent;
parent = city;
}
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(Map map, int city, List<int> unvisitedInput, List<int> visitedInput, double weight)
{
// create local copy of Tour variables
List<int> unvisited = new(unvisitedInput);
List<int> visited = new(visitedInput);
// remove current City from tour
int removed = unvisited.RemoveAll(c => c == city);
//? verify that a single city was removed
Debug.Assert(removed == 1,
$"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city}");
// set parent of current city to previous city
if (visited.Count > 0)
weight += map[city][visited.Last()].Weight;
// add current City to visited
visited.Add(city);
if (weight > BestWeight)
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 (int neighbor in unvisited)
BruteForce(map, neighbor, unvisited, visited, weight);
// if we traversed all cities in the graph
if (unvisited.Count == 0)
{
// add the return home
weight += map[visited.First()][visited.Last()].Weight;
// set as best if lower weight than previous best
if (weight < BestWeight)
{
BestTour = visited;
BestWeight = weight;
Debug.WriteLine("*** Found new best tour ***");
Debug.WriteLine(String.Join(" -> ", visited));
Debug.WriteLine(weight);
}
}
}
}
}
|
