Путаница с NP-трудным и NP-полным в задачах коммивояжера

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

Я дам краткий ответ, за которым последует более подробное объяснение связанных понятий.

Укороченная версия

Интуитивно (и неформально) проблема находится в NP, если ее решения легко проверить.

С другой стороны, проблема является NP-сложной, если ее трудно решить или найти решение.

Теперь задача является NP-полной, если она одновременно NP-сложная и NP-сложная. Следовательно, у вас есть два ключевых, интуитивно понятных свойства NP-полноты. Легко проверить, но трудно найти решения.

Хотя они могут показаться похожими, проверка и поиск решений — это две разные вещи. Когда вы используете редукционные аргументы, вы смотрите, сможете ли вы найти решение. В этом отношении и TSP, и TSP-OPT являются NP-трудными, и найти их решения сложно. Фактически, третий PDF-файл содержит решение для упражнения 8.1 вашего учебника, которое прямо показывает, что TSP и TSP-OPT одинаково сложно решить.

Итак, одно из основных различий между TSP и TSP-OPT заключается в том, что первое (как это называется в вашем учебнике) является задачей поиска, а второе — задачей оптимизации. Понятие проверки решения задачи поиска имеет смысл, а в случае TSP это легко сделать, поэтому оно является NP-полным. Для задач оптимизации понятие проверки решения становится странным, потому что я не могу придумать никакого способа сделать это без предварительного вычисления размера оптимального решения, что примерно эквивалентно решению самой задачи. Поскольку мы не знаем эффективного способа проверки решения для TSP-OPT, мы не можем сказать, что оно находится в NP, а значит, мы не можем сказать, что оно NP-полно. (Подробнее на эту тему в подробном объяснении.)

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

Подробнее

В вашем учебнике очень кратко упоминается, что такое проблема принятия решения. Формально понятия NP-полноты, NP-трудности, NP, P и т. д. разрабатывались в контексте проблем принятия решений, а не задач оптимизации или поиска.

Вот краткий пример различий между этими разными типами проблем.

Проблема принятия решения – это проблема, ответ на которую — ДА или НЕТ.

Проблема решения TSP

Входные данные: график G, бюджет b.

Вывод: допускает ли G тур веса не более b ? (ДА НЕТ)

Вот версия для поиска

Проблема поиска TSP

Входные данные: график G, бюджет b.

Вывод: найти обход G веса не более b, если он существует.

А теперь вариант оптимизации

Проблема оптимизации TSP

Входные данные: график G

Вывод: найти обход G с минимальным весом.

Вне контекста проблема TSP может относиться к любому из них. То, что я лично называю TSP, является версией решения. Здесь ваш учебник использует TSP для версии поиска и TSP-OPT для версии оптимизации.

Проблема здесь в том, что эти различные проблемы строго различны. Версия решения требует только существования, в то время как версия поиска требует большего, ей нужен один пример такого решения. На практике мы часто хотим иметь фактическое решение, поэтому более практичные подходы могут не упоминать проблемы принятия решений.

А как насчет этого? Определение NP-полной задачи предназначалось для задач принятия решений, поэтому технически оно не применимо непосредственно к задачам поиска или оптимизации. Но поскольку теория, лежащая в основе этого, хорошо определена и полезна, удобно по-прежнему применять термин NP-complete/NP-hard к задаче поиска/оптимизации, чтобы у вас было представление о том, насколько сложно решить эти проблемы. Поэтому, когда кто-то говорит, что задача коммивояжера является NP-полной, формально это должна быть версия проблемы решения проблемы.

Очевидно, что многие понятия можно расширить так, чтобы они также включали задачи поиска, и именно так это представлено в вашем учебнике. Различия между решением, поиском и оптимизацией — это как раз то, что вы пытаетесь осветить в упражнениях 8.1 и 8.2 в вашем учебнике. Эти упражнения, вероятно, предназначены для того, чтобы заинтересовать вас отношениями между этими различными типами проблем и тем, как они соотносятся друг с другом.

Укороченная версия

Задача принятия решения является NP-полной, потому что у вас может быть верификатор решения с полиномиальным временем, а также тот факт, что задача о гамильтоновом цикле сводится к TSP_DECIDE за полиномиальное время.

Однако задача оптимизации является строго NP-трудной, поскольку, хотя TSP_OPTIMIZE сводится к задаче гамильтонового цикла (HAM) за полиномиальное время, у вас нет полиномиального верификатора времени для заявленного гамильтонова цикла C, независимо от того, является ли он кратчайшим или нет, потому что вам просто нужно перечислить все возможности (что требует пространства и времени факториального порядка).

То, что определяет данная ссылка, является узким местом TSP.

Проблема коммивояжера с узким местом (узкое место TSP) — это задача дискретной или комбинаторной оптимизации. Задача состоит в том, чтобы найти гамильтонов цикл во взвешенном графе, который минимизирует вес самого тяжелого ребра цикла.

Известно, что задача является NP-трудной. Версия проблемы принятия решения: «Существует ли гамильтонов цикл в графе G для заданной длины x, в котором нет ребер длиннее x?», является NP-полной. NP-полнота следует непосредственно из проблемы нахождения гамильтонова цикла.

Эту проблему можно решить, выполнив бинарный поиск или последовательный поиск наименьшего x такого, что подграф ребер веса не выше x имеет гамильтонов цикл. Этот метод приводит к решениям, время выполнения которых лишь в логарифмический множитель превышает время нахождения гамильтонова цикла.

Длинная версия

Ошибка состоит в том, что говорят, что TSP является NP-полным. Правда в том, что TSP — это NP тяжело. Поясню немного:

TSP — это задача, определяемая набором городов и расстояниями между каждой парой городов. Задача состоит в том, чтобы найти схему, которая проходит через каждый город один раз и заканчивается там, где начинается. Это само по себе не сложно. Что делает задачу интересной, так это найти кратчайшую цепь среди всех возможных.

Решить эту проблему довольно просто. Нужно просто вычислить длину всех возможных цепей, а затем сохранить самую короткую. Проблема в том, что количество таких схем очень быстро растет вместе с количеством городов. Если есть n городов, то это число факториально от n-1 = (n-1)(n-2)... 3.2.

Проблема является NP, если можно легко (за полиномиальное время) проверить, что предлагаемое решение действительно является решением.

Вот в чем хитрость.

Чтобы убедиться, что предлагаемый тур является решением TSP, нам нужно проверить две вещи, а именно:

1. Что каждый город посещается только один раз
2. Что нет более короткого тура, чем тот, который мы проверяем

Мы не проверяли второе условие! Второе условие затрудняет решение проблемы. На сегодняшний день никто не нашел способа проверить условие 2 за полиномиальное время. Это означает, что TSP не находится в NP, насколько нам известно.

Следовательно, насколько нам известно, TSP не является NP-полным. Мы можем только сказать, что TSP — это NP hard.

Когда они пишут, что TSP является NP-полной, они имеют в виду, что следующая проблема решения (вопрос да/нет) является NP-полной:

TSP_DECISION : Учитывая число L, набор городов и расстояние между всеми парами городов, существует ли тур, который посещает каждый город ровно один раз, длина которого меньше L?

Эта проблема действительно является NP-полной, так как легко (полиномиальное время) проверить, что данный тур приводит к утвердительному ответу на TSPDECISION.