У Вас когда-либо было бизнес-требование, которое оказалось Полной NP проблемой?
Если вы хотите три отдельных строки, вы можете использовать for loop.
Попробуйте следующий код:
x = ['nm0000131', 'nm0000432', 'nm0000163']
for value in x:
print(value)
Вывод будет выглядеть следующим образом:
nm0000131
nm0000432
nm0000163
Следующий код будет отображать вывод, подобный "nm0000131" ,"nm0000432" ,"nm0000163":
Как вы упомянули в комментарии, я хотел бы добавить еще несколько моментов к моему ответу. Если вы хотите получить пары ключ-значение, попробуйте следующий код.
y = {'131': 'a', '432': 'b', '163': 'c'}
w = []
for key, value in y.items():
w.append(value)
print(w)
Вывод:
['c', 'a', 'b']
9 ответов
Как другие заявили, ранец (для упаковки груза) и проблема коммивояжеров является, вероятно, наиболее распространенным "реальным миром" полные NP проблемы.
Я склонен сталкиваться с проблемами на работе, которая, как могут доказывать, не является NP, завершенным или неполным, потому что они очень хорошо не определяются.
Любой вид отображающегося инструмента, где необходимо найти оптимальные точки перемещения больше чем между двумя местами, может без любых изменений становиться Полной NP проблемой
Проблема оптимизации волны, выбирающей со склада, эквивалентна проблеме Коммивояжера.
Таким образом, у Вас есть N-заказы, ожидающие, чтобы быть выбранными, и Вы хотите найти, что n лучше всего заказывает для уменьшения путешествовавшего расстояния и различные местоположения выбора, которые посещает средство выбора.
Я недавно столкнулся с этой проблемой. Мы плыли на плоскодонке и использовали приближение, которое будет работать хорошо на средний случай, но может иногда обеспечивать субоптимальные результаты.
Проблемой коммивояжера является идеальный пример. Тот же вид логистических проблем относится к авиакомпаниям, почтовым отделениям и всем видам отраслей промышленности.
Кроме того, задача о ранце (который является NP-трудным) обнаруживается справедливо часто. Это - обольстительное прерывание для попытки оптимизировать вещи.
Несколько лет назад я работал над картографической программой, похожей на родную программу Google Maps. Я поместил на карту небольшие маркеры для местоположений, но многие маркеры были сгруппированы близко в определенных местах. Мой босс сказал: «Позвольте мне сделать это, чтобы я мог просто перетащить маркеры немного подальше» (и от маркера к фактическому местоположению будет идти линия или речевой пузырь-указатель)
. было глупо заставлять пользователя делать это, тем более что он тратил 5 минут на доведение до совершенства, а затем менял уровень масштабирования, и тогда все было бы неправильно.
Я решил попробовать написать функцию, чтобы найти способ для размещения этикеток таким образом, чтобы общее расстояние экрана от каждой этикетки до ее местоположения было минимальным. Думаю, в то время я убедил себя, что это было NP-полным, но что количество точек может быть достаточно небольшим, чтобы это было возможно, по крайней мере, во многих случаях. (Я помню, что думал, что мы слишком много времени в классе потратили на доказательства NP-полноты и недостаточно на альтернативные решения: если ваш босс хочет, чтобы что-то было сделано, вы не можете просто сказать: «NP сложно, не пойдет» - вы еще нужно придумать что-то .)
Затем появились Google Maps и просто расклеили все метки друг на друга, что полный отстой (и я проклинаю это каждый день), но я могу не конкурировать с их другими функциями, поэтому я сдался. : - (
Стоит отметить, что существуют методы эвристической аппроксимации для получения "достаточно хороших" ответов на NP-полные проблемы, такие как имитация отжига и отжиг со сжатием. Если вы можете свести проблему NP-complete к проблеме коммивояжера, вы можете использовать эти подходы. (Любая NP-полная проблема может быть сведена к любой другой NP-полной проблеме, но на самом деле это иногда становится головной болью.)
В любом случае, существуют реализации моделируемого отжига и сжатого отжига; одним из них является Djinni , который написан на C ++ и имеет привязки к Python.
Другой пример: компании с региональными распределительными центрами, особенно те, которые доставляют товары напрямую клиентам (например, Netflix), должны беспокоиться о семействе проблем NP-Complete, известных как location .
На самом деле идея о том, что NP-Complete задачи актуальны в реальном мире, подтверждается тем фактом, что аппроксимационные алгоритмы для них так часто появляются в журналах операционных исследований.
Я согласился написать программу для отца друга, когда был студентом первого курса колледжа. Это было для планирования ресурсов. Я не осознавал этого в то время, но это оказалось полной проблемой NP.
К счастью, просто найти решение было приемлемо - не нужно было искать оптимальное решение. Было весело писать эвристики - на самом деле их набор - которые можно было изменить, пока программа работала и пыталась решить проблему.
Летом у меня было решение, но потом каждый год работал над новыми версиями. Мои большие планы продать это рухнули. Я был лучшим разработчиком, чем маркетологом.
Это было очень весело и рано научило меня многому о реальном мире разработки - (конечные пользователи, сбор требований, тестирование и т. Д.) - многое из того, что вы ДОН' Я попадаю в бакалавриат CS)
Отвечая на ваш вопрос - это было для учителя, который должен был назначать студентов для специального обучения. Он был логопедом и аудиологом, но его можно было применить в любой подобной области. У него были существующие мероприятия для учителей, классов и учеников, над которыми он работал, и ему приходилось встречаться со студентами определенное количество раз в неделю. Это задача о ранце или любое количество других подобных / эквивалентных задач планирования.
Опять же, оказалось, что просто получить решение было нормально - нам не нужно было ничего максимизировать или минимизировать - нам просто нужно было приспособить всех студентов.
Я могу только вспомнить, что у меня не было возможности решать тестовые примеры, которые я использовал для запуска сценариев - все проблемы, которые он предлагал за годы, которые мы решили.
Я никогда не мог продавать его - в основном потому, что я понятия не имел, что делаю, и не знал, как выйти на свой рынок / покупателей.