Рассмотрим связный неориентированный граф с неотрицательными весами ребер и двумя выделенными вершинами . Ниже приведены некоторые задачи на пути, которые имеют следующую форму: найдите путь , чтобы некоторая функция весов ребер на пути была минимальной. В этом смысле все они являются «родственниками» проблемы кратчайшего пути; в последнем случае функция - это просто сумма.
Примечание. Мы ищем простые пути, то есть без повторяющихся вершин. Поскольку в литературе я не нашел стандартных названий этих проблем, я назвал их сам.
Траектория с минимальным разрывом в весе: найдите траекторию, чтобы разница между наибольшим и наименьшим весом ребер на трассе была минимальной.
Самый плавный путь: найдите путь , чтобы наибольший размер шага на пути был минимальным, где размер шага - это абсолютное значение разницы в весе между двумя последовательными ребрами.
Траектория с минимальной высотой. Давайте определим высоту трассы суммой размеров шагов вдоль пути (см. Определение размера шага выше). Найти путь с минимальной высотой.
Путь с минимальным простым весом: предполагая, что все веса ребер являются натуральными числами, найдите путь , чтобы его вес был простым числом. Если есть такой путь, найдите тот с наименьшим возможным основным весом.
Вопрос: что известно об этих проблемах пути? (И другие, которые можно было бы представить в том же духе, применяя другую функцию весов.) В целом, есть ли какое-либо указание, что какие функции весов ребер могут быть минимизированы за полиномиальное время, а какие являются NP-сложными?
источник
Плавный путь: НП завершен. Если бы мы разрешали самопересечения, это было бы разрешимо во времени , но для версии без самопересечений здесь приведено сокращение от 3-SAT с переменными. Иметь вершины , плюс вершины для каждого предложения. Для каждой переменной ( ) добавьте плавный путь (при необходимости используя дополнительные вершины) из в который проходит через все предложения с положительным вхождением , и аналогичный путь для предложений сO~(|E|) n s=v0,v1,...,t=vn xi i<n vi vi+1 xi ¬xi , Установите вес первого и последнего ребра каждого пути равным 1 (или другой константе), но в противном случае выбирайте веса так, чтобы другие пути не были гладкими. Наконец, продублируйте все вершины клаузулы и прилегающие ребра; таким образом, каждое предложение может быть просмотрено не более двух раз, что достаточно для 3-SAT.
источник