Связанные NP-полные проблемы с реальными проблемами

У меня есть достойное понимание NP Полные проблемы; это не проблема. То, что у меня нет, - это хорошее представление о том, где они появляются в "реальном" программировании. Некоторые (например, ранцы и коммивояжеры) очевидны, но другие, похоже, не связаны с "настоящими" проблемами.

У меня был опыт несколько раз бороться с трудной проблемой только для того, чтобы понять, что это хорошо известная проблема NP Complete, которая была исследована широко. Если бы я узнал соединение быстрее, я мог бы сэкономить немало времени на поиске существующих решений для моей конкретной проблемы.

Есть ли какие-либо ресурсы (онлайн или печать), которые специально связывают NP Complete с реальными экземплярами?

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

Ответ 1

Я обнаружил, что "Компьютеры и нецелесообразность" является окончательной ссылкой на эту тему.

Ответ 2

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

Этот отрывок не является тривиальным, так как вам нужно доказать, что вы можете превратить каждый экземпляр проблемы l из известной проблемы NP-Hard L в экземпляр c вашей проблемы C с использованием детерминированных полиномиальных алгоритмов.

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

Ответ 3

Вот ссылка на wiki: http://wapedia.mobi/en/List_of_NP-complete_problems Обратите внимание:

Этот список никоим образом не является исчерпывающим (существует более 3000 известных NP-полных проблем)

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

Теоретик должен попытаться понять/доказать NP-Complete/Hard проблему. Но программисту это не нужно. Ему нужен список.

Правильно ли я?

Я думаю, что вы должны google it. И прочитайте все ссылки. Добавьте новую проблему, найденную в ссылке к вашему списку.

Надеюсь, что это поможет

PS: Не забудьте опубликовать список, когда вы закончите: P

Ответ 4

Для более эффективной интуиции книга " Руководство по разработке алгоритмов, второе издание" от Skiena (выдержки из книг Google) просто великолепна.

Список в спину с проблемами (включая трудные проблемы), что включают иллюстрацию и обсуждение (часто) с реальным миром Пример.
Охватывает как теоретические и практическая сторона вещей, часто говоря о фактическом коде.

Прочтите за исключением онлайн здесь (см. некоторые примеры в главах 14): http://books.google.dk/books?id=7XUSn0IKQEgC&printsec=frontcover#v=onepage&q&f=false

В главе 16 (не в сети) обсуждаются некоторые сложные проблемы, в том числе разделение графов.