algorithm - 像旅行商一样的问题

Question

给定二维欧氏平面中的一组点:P={V₁,V₂,..,V_n} ，我们假设有 K 个不同类型的点:T₁,T₂,..,T_K，每个点 V< P 中的 sub>i 恰好属于 K 种类型之一。

KTSP巡演定义:
给定同一二维欧几里德平面中的任意位置点 V₀(V₀ 没有类型)，路径 V₀->V< sup>'₁->V^'₂->V^'₃->....->V^'_K->V₀ 称为 KTSP 巡演当且仅当 V^' _i 属于第 i 类。

KTSP 游览只是在同一给定任意点开始和结束的普通游览，但还要受到两个约束:(1)它通过每种类型的点一次且仅一次。(2)路径经过的点类型是有顺序的。即先从点V₀开始，然后先经过类型T1点，再经过类型T2点，然后类型T3点，以此类推，直到经过类型T_K 点，之后它回到 V₀。

这是我的问题:
当给定点位置 V₀ 时，找到最短的 KTSP 路径。

例如下图中，每种颜色代表一种类型的点，共有3种不同类型的点，我们假设蓝色的点是类型1，红色的类型2，黑色的类型3，
黄色的小三角形是给定的位置 V₀，然后用四个蓝色箭头显示对应于该特定 V₀ 的最短 TSKP 行程。

在我看来这是经典 TSP 问题的变体，但我想不出算法，需要帮助!

Answer 1

不是tsp，而是最短路径。

考虑 k 层点:

• 在第k层你只有所有颜色为k的点
• 在一层的每个点和下一层的每个点之间都有一条有向边
• 在V0和第1层的所有点之间添加一条边
• 创建V0、V0'的副本，并在k层和V0'的每个点之间添加一条边

现在您想要的是 V0 和 V0' 之间的最短路径，它将在第 1、2...k 层经过，最后经过 V0'，给定您的“最短 TSKP 行程”。