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
|
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
{
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;
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;
}
}
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));
double BestWeight = double.MaxValue;
List<int> 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;
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);
}
}
}
}
}
}
|
