Коммивояжеру нравится проблема

Question

При заданном наборе точек в евклидовой плоскости 2D: P = {V ₁ , V ₂ , .., V _n }, и мыПредположим, что существует K различных типов точек: T ₁ , T ₂ , .., T _K , каждая точка V _i в P принадлежит ровно одному из K типов.

Определение маршрута KTSP:
Учитывая произвольную точку местоположения V ₀ в той же 2D евклидовой плоскости (V ₀ не имеет типа), путь V* 0 * тысяча двадцать два * * один тысяча двадцать три -> V ₁ -> V _{2 * * тысяча тридцать один -> V * * тысяча тридцать-дв '* тысяча тридцать-три* 3 -> ....-> V ^' K -> V 0 называется тур KTSP, если V ^' i относится к типу I.}

Тур KTSP - это просто обычный тур, начинающийся и заканчивающийся в той же заданной произвольной точке, но с двумя дополнительными ограничениями: (1)Он проходит каждый тип точки один и только один раз.(2) Тип точки, которую проходит путь, имеет порядок.То есть сначала он начинается с точки V ₀ , затем сначала проходит точку типа T1, затем тип точки T2, затем тип точки T3 и т. Д., Пока не пройдет точку типа T _K ., после чего он возвращается на V ₀ .

. Вот мой вопрос:
когда указывается точка V ₀ , найдите кратчайший тур KTSP.

Например, на следующем рисунке каждый цвет представляет один тип точки, есть 3 различных типа точек, мы предполагаем, что точки синего цвета - это тип 1, красный тип 2, черный тип 3,
и маленький треугольник с желтым цветом - это заданное местоположение V ₀ , тогда кратчайший тур TSKP, соответствующий этому конкретному V ₀ , показан четырьмя синими стрелками.

Мне кажется, это вариант классической проблемы TSP, но я не могу придумать алгоритм, нужна помощь!

Answer 1

Это не tsp, а кратчайший путь.

Рассмотрим k слоев точек:

• на слое k у вас есть только все точки цвета k
• выиметь направленный край между каждой точкой слоя и каждой точкой следующего слоя
• добавить ребро между V0 и всеми точками слоя 1
• создать копию V0, V0 'и добавитьгрань между каждой точкой слоя k и V0 '

Теперь вам нужен кратчайший путь между V0 и V0', он пройдет на уровне 1, 2 ... k и, наконец, V0 ', учитывая ваш «кратчайший тур по ЦКП».

Answer 2

Я бы рекомендовал вернуться назад (если количество точек не слишком велико).

Это самый простой алгоритм из всех