У вас когда-нибудь было деловое требование, которое оказалось проблемой NP-Complete?

Question

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

Так что мне любопытно, сталкивался ли кто-нибудь с проблемой на работе, которая оказалась NP-полной, и что дизайн нужно было изменить, чтобы приспособиться к ней?

Answer 1

Как отмечали другие, проблема с рюкзаком (для упаковки груза) и коммивояжёром, вероятно, является наиболее распространенной проблемой "полного мира" в NP-полной ситуации.

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

Answer 2

Стоит отметить, что существуют эвристические методы аппроксимации для получения «достаточно хороших» ответов для задач с NP-завершением, таких как имитационный отжиг и сжатый отжиг. Если вы можете свести проблему NP-complete к проблеме Traveling Salesman, вы можете использовать эти подходы. (Любая NP-полная проблема может быть сведена к любой другой NP-полной проблеме, но на самом деле это иногда делает боль в заднице.)

В любом случае, есть моделируемый отжиг и сжатый отжиг; один из них - Джинни , написанный на C ++ и имеющий привязки Python.

Answer 3

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

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

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

Это было очень весело и рано научило меня многому о реальном мире разработки - (конечные пользователи, сбор требований, тестирование и т. Д. - многое из того, что вы НЕ получаете в старших классах CS)

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

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

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

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

Answer 4

Кроме того, проблема с рюкзаком (которая NP-сложная) проявляется довольно часто. Это соблазнительная ловушка для попыток оптимизировать вещи.

Answer 5

Задача оптимизации комплектации волн со склада эквивалентна Задаче коммивояжера .

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

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

Answer 6

Любой вид картографического инструмента, где вам нужно найти оптимальные точки перемещения между более чем двумя точками, может без каких-либо изменений стать проблемой NP-Complete

Answer 7

Я работал над картографической программой несколько лет назад, как родной Google Maps. Я поместил на карту маленькие маркеры для местоположений, но в некоторых местах было тесно сгруппировано много маркеров. Мой босс сказал: «Позвольте мне сделать так, чтобы я мог немного отодвинуть маркеры» (и у него была бы линия или речевой пузырь-указатель-штука, идущий от маркера к фактическому месту).

Я думал, что было бы глупо заставлять пользователя делать это, тем более что он потратил 5 минут, чтобы сделать его идеальным, а затем изменил уровень масштабирования, и тогда все было бы неправильно.

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

Потом появились Карты Google и просто высыпали все метки друг на друга, что полностью отстой (и я проклинаю это каждый день), но я не могу конкурировать с их другими функциями, поэтому я сдался. : - (

Answer 8

Другим примером является то, что компаниям с региональными распределительными центрами, особенно тем, которые поставляют напрямую клиенту (например, Netflix), нужно беспокоиться о семействе проблем NP-Complete, известных как расположение объекта .

Фактически, идея, что задачи NP-Complete актуальны в реальном мире, подтверждается тем фактом, что алгоритмы аппроксимации для них так часто появляются в журналах по оперативным исследованиям.

Answer 9

Задача коммивояжера - прекрасный пример. Те же самые проблемы логистики относятся к авиакомпаниям, почтовым отделениям и всем видам промышленности.