The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
In this puzzle not necessarily the shortest route is the answer but an approximation using a greedy algorithm (which in fact could be the shortest route as well).
This greedy algorithm starts at the first input given and always chooses the nearest point from the current point. This continues until no points are left and the last point is connected to the first point.
Use the euclidian distance, i.e. sqrt(deltaX^2 + deltaY^2), as the distance between two cities. If there are points with the same distance, always pick the one occurring first in the list.
In general, the greedy algorithm does not find the optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
In this puzzle not necessarily the shortest route is the answer but an approximation using a greedy algorithm (which in fact could be the shortest route as well).
This greedy algorithm starts at the first input given and always chooses the nearest point from the current point. This continues until no points are left and the last point is connected to the first point.
Use the euclidian distance, i.e. sqrt(deltaX^2 + deltaY^2), as the distance between two cities. If there are points with the same distance, always pick the one occurring first in the list.
In general, the greedy algorithm does not find the optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
Input
Line 1: An integer N for the number of points.
Next N lines: Two space separated integers x and y for the coordinates.
Next N lines: Two space separated integers x and y for the coordinates.
Output
Line 1: The rounded distance calculated using the greedy algorithm.
Constraints
5 ≤ N ≤ 14
0 ≤ x, y ≤ 100
0 ≤ x, y ≤ 100
Solution
The problem statement already gives the algorithm to approximate the TSP problem. So, given a vertex set \(G\), a function to find the shortest path to the closest vertex can be formulated according to the problem statement:
function shortestPath(G, c) {
let minDist = Infinity;
let min = null;
for (let i = 0; i < G.length; i++) {
const dist = Dist(c, G[i]);
if (minDist > dist) {
minDist = dist;
min = i;
}
}
return {ndx: min, dist: minDist};
} Now looping over the vertex set again, sum over each minimal distance and delete the found vertex implements the desired algorithm to approximate the TSP:
const N = +readline();
const G = [];
const Dist = (a, b) => Math.hypot(a[0] - b[0], a[1] - b[1]);
for (let i = 0; i < N; i++) {
G.push(readline().split(' ').map(Number));
}
const first = G.shift();
let sum = 0;
let cur = first;
while (G.length > 0) {
const {ndx, dist} = shortestPath(G, cur);
sum+= dist;
cur = G.splice(ndx, 1)[0];
}
print(Math.round(sum + Dist(cur, first)));