Есть ли у кого-нибудь примеры из реальной жизни, когда они регулярно решают сложные задачи NP или сложные задачи NP (с помощью эвристики, или выбирая неоптимальное решение или что-то еще) в своей работе? Я знаю, что они встречаются в планировании, планировании, проектировании СБИС и т. Д., Но я пытаюсь понять основные отрасли, в которых сегодня работают программисты или инженеры, которые регулярно делают это. Если бы кто-то развивал опыт или библиотеку, скажем, комбинаторную оптимизацию, где можно было бы использовать это как часть работы по программированию?
Есть ли личные счета?
algorithms
optimization
высокая пропускная способность
источник
источник
Ответы:
Некоторые из вещей, о которых я могу думать (большинство из которых я принимал участие более или менее):
Существует множество стандартных примеров, таких как поиск кратчайшего маршрута, планирование работы медсестры и т. Д., Но если вы увлекаетесь комбинаторной оптимизацией, вы знаете о них все :)
источник
Я использовал ограниченный по времени имитационный отжиг, чтобы решить проблему, с которой сталкиваются коммивояжеры, в производстве сенсорных панелей. Каждую миллисекунду, которую мы могли бы сократить, используя время цикла лазерного травления каждой панели, будет увеличиваться производительность, коэффициент использования и, следовательно, рентабельность станка, поэтому я приложил немало усилий, чтобы минимизировать мертвое время (пути без разметки) между путями разметки (которые очевидно, не может быть оптимизирован).
Я использовал ограниченный по времени алгоритм, чтобы обойти сложность задачи с точки зрения NP, поскольку мы не могли позволить себе риск, что расчет оптимизации может занять больше времени, чем время, сэкономленное более оптимальным путем. Пока машина перемещала панель из положения загрузки в положение, в котором лазерная головка находилась над ближайшим углом, у меня было время провести некоторые симуляции. Алгоритм почти никогда не заканчивался в течение нескольких сотен миллисекунд после перемещения, но почти всегда возвращал лучший путь писца, чем любая из простых неадаптивных моделей, которые мы всегда использовали ранее (например, спиральные или змеиные пути).
источник
Я работаю (прямо сейчас) над проблемой биоинформатики множественного локального выравнивания последовательности ДНК. Дело в том, что если множество последовательностей из генов с некоторым общим свойством (схожий профиль экспрессии или связывание одного и того же фактора транскрипции в эксперименте с чип-чипом) в какой-то момент сильно совпадают, то вы, вероятно, нашли причину их общего свойство. Опять же, меня больше интересуют статистические аспекты проблемы. Несмотря на то, что это NP-хард, вы не теряете много, используя эвристику на практике. ИМХО интересная часть проблемы - проблема отношения сигнал / шум.
источник
Я на самом деле не знаю, что означает NP Complete / Hard, но я думаю, что автопланирование поставок является своего рода.
Вам необходимо составить план на 90 дней вперед для 100 наименований продукции: пиво! 100 наименований продукции поступают из:
Есть машинные «линии» для каждой операции: от заваривания до упаковки. Машины могут выполнять больше операций, скажем, некоторые упаковочные машины могут производить 6 и 3 упаковки, а другие могут делать только 6 упаковок. Есть ограничения, например, скорость, или большой варочный котел предназначен для варки мин. 6000, максимум, 8000 л пива (но если пиво светлого типа, то минимальное значение составляет 5000 л, а максимальное - 7000 л). И так далее, на каждом уровне.
Задача: как я уже говорил, есть план спроса на 100 уровень 5-го уровня (в бутылках, в упаковке). Составьте оптимальный план изготовления для всех 5 уровней, всех машин. Минимизируйте машинные выключатели (например, разлив в бутылки .5, .5, .5, .3, .3, .3 лучше, чем .3, .5, .3, .5, .3, .5, меньше меньше, меньше мертвого времени для разливочных машин). Расстановка приоритетов по заказу: некоторые клиенты требуют отгружать пиво только с более чем 50% срока годности. И т. Д.
Обнаружьте узкие места (ах), составьте альтернативные планы, добавив несуществующие машины к этим точкам, и тогда можно использовать лучший виртуальный сценарий, чтобы предложить купить новые машины.
Это достаточно сложно, или я должен рассказать вам, как работает текстильная фабрика ?
(Личное замечание: Интернет, банк и логистика - сложные области, но они - детские игрушки по сравнению с производственными проблемами.)
Отказ от ответственности: цифры искажены по соображениям безопасности, порядок величины является действительным.
источник