blob: a26fe6c4211c13ed5c7e79c8fa8225b6673fed49 (
plain)
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
|
using System.Diagnostics;
using System.Linq;
using System.Text.RegularExpressions;
using Graph;
using Graph.IO;
namespace TSP
{
using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>;
public static class TSP
{
static Tour BestTour = null;
static Map Map;
public static Tour BruteForce(Map map, int init)
{
Map = map;
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 = 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;
currCity.Key = Map.Vertices[currCity.Id].Edges
.Where(edge => edge.V == currCity.Parent)
.Last().Weight;
}
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;
}
}
}
|
