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
|
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>;
public static class TSPSolver
{
static Map Map { get; set; }
static Tour BestTour = null;
public static Tour MST(string file, string coords, int init)
{
Map mst = GraphFile.Read(new FileReader(file)).MST(0);
return new Tour(mst.Vertices.OrderBy(vertex => vertex.Id).ToList(), Coordinate.Parse(coords));
}
public static Tour BruteForce(string file, string coords, int init)
{
Map = GraphFile.Read(new FileReader(file));
Tour intialTour = new Tour(Map.Vertices, Coordinate.Parse(coords));
GenerateTour(intialTour[init], intialTour, new Tour());
return BestTour;
}
static void GenerateTour(City city, Tour tour, Tour visited)
{
// create local copy of Tour variables
Tour currTour = new Tour(tour.Cities);
Tour currVisited = new Tour(visited.Cities);
City currCity = new City(city);
// remove current City from tour
currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.Id));
//? verify that city was removed
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)
currCity.Parent = currVisited.Cities.Last().Id;
currVisited.Cities.Add(currCity);
//? verify that city was added
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
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 = new Tour(currVisited.Cities);
// Debug.Print($"{currTour}");
}
return;
}
}
}
|
