A traveling salesman like problem

Given a set of points in the 2D Euclidean plane: P={V₁,V₂,..,V_n}, and we assume that there are K different types of points:T₁,T₂,..,T_K, every point V_i in P belongs to exactly one of the K types.

Definition of KTSP tour:

Given an arbitrary location point V₀ in the same 2D Euclidean plane (V₀ has no type), a path V₀->V^'₁->V^'₂->V^'₃->....->V^'_K->V₀ is called a KTSP tour iff V^'_i belongs to type i.

A KTSP tour is just an ordinary tour starting and ending in the same given arbitrary point but subject to two more constraints: (1)It passes every type of point one and only once. (2)The type of point the path passes has order. That is, it first starts from point V₀, then first passes type T1 point, then type T2 point, then type T3 point, and so on until it passes type T_K point, after which it comes back at V₀.

Here is my question:

when the point location V₀ is given find the shortest KTSP tour.

For example, in the following figure, every color represents one type of point, 开发者_如何学Cthere are 3 different types of points, we assume blue colored points are type 1, red type 2, black type 3,

and the little triangle with yellow is the given location V₀, then the shortest TSKP tour corresponding to this particular V₀ is shown with the four blue arrows.

It seems to me this a variant of the classical TSP problem, but i can't think of an algorithm, need help!

It's not tsp, but shortest path.

Consider k layers of points :

• on layer k you only have all points of color k
• you have a directed edge between every point of a layer and every points of the next layer
• add an edge between V0 and all points of layer 1
• create a copy of V0, V0' and add an edge between every point of layer k and V0'

Now what you want is the shortest path between V0 and V0', it will pass at layer 1, 2...k and finally V0', given you your "shortest TSKP tour".

I would recommend backtracking (if the number of points isn't to large).

It's the easiest algorithm out there