旅行推销员喜欢问题

Question

给定2D欧几里得平面中的一组点:P = {V ₁,V ₂,...,V _n },并且我们假设存在K种不同类型的点:T ₁,T ₂,...,T _K,P中的每个点V _i都属于K类型中的一个.

游解KTSP的定义:
给定一个任意位置点V ₀中相同的2D平面欧几里得(V ₀没有类型),一个路V ₀ > - V ^' ₁ > - V ^' ₂ > - V ^' ₃ - > ... .-> V ^' _ķ > - V ₀被称为游解KTSP当且仅当V ^' _我属于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之旅".