Поиск минимального количества туров по всем узлам

Question

Я столкнулся с проблемой ниже.

Заявление:

1. ряд узлов с их местоположений приведены
2. Существует центральный узел в середине которого его расположение также предусмотрено.
3. Маршрут определяется как путь, который начинается с центрального узла и посещает хотя бы один узел и заканчивается снова в центральном узле.
4. Длина маршрута должна быть короче заданного числа.

Как покрыть все узлы минимальным количеством маршрутов?

Я был бы признателен за любую помощь, которая может предоставить решение этой или подобной и известной проблемы, которая выглядит так, если есть что-нибудь.

Answer 1

Эта проблема NP-Hard с простым сокращением от TSP.

Во-первых, определить язык, на котором принимается эта проблема

L = { (G,x,i) | graph G, maximum length per path x, minimal number of travels required i } 

Легко видеть, что ваша проблема заключается в основном задача оптимизации для задачи существования, как определено выше.

TSP:
Учитывая экземпляр TSP в виде (G,x), нам нужно определить, есть ли циклический путь, который проходит через все точки длина короче/равняется x.

Сокращение:
Сокращение выглядит следующим образом. Учитывая экземпляр TSP (G,x), укажите экземпляр для вашей проблемы (G,x,1).

Корректность:

• Если есть циклический путь, который проходит через все точки длины x или менее в решении TSP, есть также решение вашей проблемы с 1 поездками требуется ,
• Если в задаче с длиной x или менее требуется 1 путешествие, это маршрут, найденный TSP.

Редукция, которую мы предложили, тривиально полиномиальна.

Из этого можно сделать вывод, что ваша проблема NP-Hard, поскольку TSP NP-Hard.