The travelling salesman problem 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?"
If someone hands us a solution, then we can check easily that it does lead to the value it claims and is it a valid ordering. This property makes the TSP a member of the class known as NP, consisting of all problems for which we can check the correctness of a solution in polynomial time. The pair of letters stands for non-deterministic polynomial. The unusual name aside, this is a natural class of problems: when we make a computational request, we ought to be able to check that the result meets our specifications.
Nearest Neighours (NN) is one of the simplest search heuristics out there. It is part of the family of constructive search heuristics, meaning that it gradually builds a route. Starting with one city and stopping only when all cities have been visited. It is greedy in nature; at each step it chooses the location that is closest to the current location.
Some graph related terms for understanding:
A sequence : ${\displaystyle v_{0},e_{1},v_{1},e_{2},\dots ,v_{n-1},e_{n},v_{n}}$ where $v_{i}$ are vertices, ${\displaystyle e_{i}}$ are edges, and for all ${\displaystyle i}$ the edge ${\displaystyle e_{i}}$ connects the vertices ${\displaystyle v_{i-1}}$ and ${\displaystyle v_{i}}$ and such a sequence is called a walk.
A walk with no repeated edges is called a tour.
A walk with no repeated vertices is called a path.
A walk or a tour where ${\displaystyle v_{0}=v_{n}}$ is called closed.
A circuit is path that begins and ends at the same vertex.
Euler tour is defined as a way of traversing tree such that each vertex is added to the tour when we visit it (either moving down from parent vertex or returning from child vertex). We start from root and reach back to root after visiting all vertices.
Hamilton Circuit: a circuit that must pass through each vertex (except the first vertex is obviously visited twice) of a graph once and only once.
In other words, Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex.
Now that the terminology was clear, the actual approximation can be talked about.