Связь Полных NP проблем к проблемам реального мира
У меня есть достойное схватывание NP Полные проблемы; это не проблема. То, что я не имею, является хорошим чувством того, где они поднимаются в "реальном" программировании. Некоторые (как ранец и коммивояжер) очевидны, но другие не кажутся, очевидно, подключенными к "реальным" проблемам.
У меня несколько раз был опыт попытки с трудной проблемой только понять, что это - известный NP Полная проблема, которая была исследована экстенсивно. Если бы я распознал соединение более быстро, то я, возможно, сэкономил довольно мало времени, исследуя существующие решения моей определенной проблемы.
Есть ли какие-либо ресурсы (онлайн или печать), которые конкретно подключают NP, Завершенный к экземплярам реального мира?
Править: Например, я работал над программой, которая пыталась разделить студентов на группы на основе возраста, класса и школы источника, который является по существу проблемой разделения графика. Это взяло меня некоторое время для понимания соединения.
3 ответа
Обычно соединение, о котором вы говорите, должно быть извлечено с помощью так называемого сокращения , например, вы сокращаете 3-SAT до проблемы, с которой работаете, а затем можете сделайте вывод, что ваша проблема имеет такую же сложность.
Этот отрывок нетривиален, так как вам нужно доказать, что вы можете превратить любой пример проблемы l известной NP-Hard проблемы L в экземпляр c вашей проблемы C с использованием детерминированных полиномиальных алгоритмов.
Таким образом, за исключением изучения основных корреляций общих NP-Hard проблем с использованием вашей памяти, невозможно быть уверенным в том, что проблема похожа на другую NP-Hard без предварительной проверки. пытаясь угадать, а затем доказать это, нужно быть умным.
Я обнаружил, что Computers and Intractability является окончательной ссылкой по этой теме.
вот ссылка на вики: http://wapedia.mobi/en/List_of_NP-complete_problems Обратите внимание, там сказано
Этот список ни в коем случае не является полным (существует более 3000 известных NP-полных проблем)
вероятно, это было бы большой задачей, если бы кто-нибудь смог составить такой список.
Теоретик должен попытаться понять/доказать NP-полную/трудную проблему. Но у программиста нет на это времени. Ему нужен список.
Я прав?
Я думаю, вам стоит погуглить. И прочитать все ссылки. Добавьте любую новую проблему, найденную в ссылке, в свой список.
Надеюсь, это поможет
PS: Не забудьте выложить список, когда закончите :P