Recently, I have been studying TSP algorithms and I would like to ask how is it best to describe the nearest neighbour algorithm in the math formation.

The foundation of the algorithm is basic, start with required node and visit the closest non-visited node. Repeat till all the nodes are visited.

I have troubles how to describe this algorithm using the mathematic notation.

I would like to start with something like this:

Let's say we have n vertices as a input: $V=\{v_1, v_2, \dots, v_n\}$ and a set of edges $E$. Define A as set of unvisited nodes = $U = \{v_1, v_2, \dots, v_n\} = V$.

Then choose the starting node $v_i$ and change the sets in following way: $U = U - \{v_i\}$. Find the closest non-visited neighbor from the current node as x = $v_j \notin U | \min\{(v_i, v_j) \in E\}$ (this mathematical notation may not be totally correct, I will edit i).

So the question is, if I define the closest unvisited neighbor as $x$ for example, how should I start and expand the current path until solution is found?

Is something like this correct? $P = P1:P2:P3$ where $P1 = \{(v_1, v_2)\}$ etc.?

What do you recommend?


  • $\begingroup$ Recommend not trying to make up notation and just using words. $\endgroup$ – Misha Lavrov Jan 27 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.