Open manjikian opened 3 years ago
See below how PI and S were counted:
// Solves the traveling salesman problem and caches solution.
public void solve() {
if (ranSolver) return; // PI = 1; Exit points = 1
final int END_STATE = (1 << N) - 1;
Double[][] memo = new Double[N][1 << N];
// Add all outgoing edges from the starting node to memo table.
for (int end = 0; end < N; end++) { // PI = 2
if (end == start) continue; // PI = 3
memo[end][(1 << start) | (1 << end)] = distance[start][end];
}
for (int r = 3; r <= N; r++) { // PI = 4
for (int subset : combinations(r, N)) { // PI = 5
if (notIn(start, subset)) continue; // PI = 6
for (int next = 0; next < N; next++) { // PI = 7
if (next == start || notIn(next, subset)) continue; // PI = 8; PI = 9
int subsetWithoutNext = subset ^ (1 << next);
double minDist = Double.POSITIVE_INFINITY;
for (int end = 0; end < N; end++) { // PI = 10
if (end == start || end == next || notIn(end, subset)) continue; // PI = 11; PI = 12; PI = 13
double newDistance = memo[end][subsetWithoutNext] + distance[end][next];
if (newDistance < minDist) { // PI = 14
minDist = newDistance;
}
}
memo[next][subset] = minDist;
}
}
}
// Connect tour back to starting node and minimize cost.
for (int i = 0; i < N; i++) { // PI = 15
if (i == start) continue; // PI = 16
double tourCost = memo[i][END_STATE] + distance[i][start];
if (tourCost < minTourCost) { // PI = 17
minTourCost = tourCost;
}
}
int lastIndex = start;
int state = END_STATE;
tour.add(start);
// Reconstruct TSP path from memo table.
for (int i = 1; i < N; i++) { // PI = 18
int bestIndex = -1;
double bestDist = Double.POSITIVE_INFINITY;
for (int j = 0; j < N; j++) { // PI = 19
if (j == start || notIn(j, state)) continue; // PI = 20; PI = 21
double newDist = memo[j][state] + distance[j][lastIndex];
if (newDist < bestDist) { // PI = 22
bestIndex = j;
bestDist = newDist;
}
}
tour.add(bestIndex);
state = state ^ (1 << bestIndex);
lastIndex = bestIndex;
}
tour.add(start);
Collections.reverse(tour);
ranSolver = true;
}
Data from Lizard tool:
./src/main/java/com/williamfiset/algorithms/graphtheory/TspDynamicProgrammingIterative.java
Data JaCoCo: