Насколько распространены алгоритмы экспоненциального времени общего случая в производственном программном обеспечении?

11

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

Мировой инженер
источник
1
У меня сложилось впечатление, что для таких вещей, как задача коммивояжера, каждый исключает алгоритм экспоненциального времени и вместо этого использует гораздо лучшую эвристику (в случае коммивояжера они довольно хороши)
soandos
Многие проблемы решаются с помощью «экспоненциальных» алгоритмов. (TSP, CDS, ILP и т. Д.) Просто экспоненциальные алгоритмы имеют хорошую эвристику, поэтому они разумно работают с большим количеством реальных данных. Возможно, лучше задать вопрос: «Насколько распространены алгоритмы экспоненциального времени общего случая в производственном программном обеспечении?»
user541686
Скорректирован вопрос
Мировой инженер
Коммивояжером является n !, не экспоненциально.
user281377
1
@ user281377: Это также в O (n ^ 2 2 ^ n), так что да, это экспоненциальная проблема. Это также ясно, потому что это может быть сопоставлено с SAT за многократное время, которое может быть решено за 2 ^ n раз - это работает для всех проблем NP.
Рафаэль

Ответы:

7

То, что не в программном обеспечении производства, а в программном обеспечении, является формальной проверкой . Вероятно, он не принят для большинства пользовательских программных продуктов, но получает преимущество для встроенных систем и драйверов, то есть для аппаратного и программного обеспечения, правильность которого важна (и поддается проверке).

Эти проблемы verficiation , которые на самом деле являются расчетными (барьер # 1) часто EXPTIME -Жесткими, в более удачных случаях вы получите PSPACE -полные проблемы (барьерные # 2). Оба класса (предположительно) сложнее, чем NP-полные задачи, которые легко сравнимы. Вдвойне экспоненциальные задачи также легко получаются.

В этих случаях эвристика (в смысле конечного результата) не сокращает ее, поскольку вам нужны определенные результаты; поэтому вам нужны большие машины и время. Существуют эвристики (в смысле альтернативного выбора), которые часто приводят к сокращению времени выполнения (т. Е. Разумное исследование пространства поиска при поиске состояний ошибок), но в худшем случае ожидание - это все, что вы можете сделать. Или вы можете сделать ручное и бумажное доказательство и проверить его на машинах , что вычислительно проще.

Рафаэль
источник
5

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

Vartec
источник
5

Интерпретаторы языка программирования хуже экспоненциального времени (по длине их ввода, то есть по длине интерпретируемой программы), и они довольно распространены. Другой пример - автоматическое доказательство теорем / решение ограничений / насыщенное решение / целочисленное линейное программирование. И еще один пример - символическое дифференцирование, реализованное, например, в Maple / Mathematica (хотя можно проводить символическое дифференцирование за линейное время, если вам разрешено делиться подвыражениями между узлами).

Жюль
источник
1

Позвольте мне взять пример проблемы коммивояжера. Я работал над этим несколько раз.

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

Вот как они работали. Каждый инженер получал бы список вещей для обслуживания на портативном устройстве каждый день. Когда они заканчивают каждую задачу обслуживания, они должны закрыть дело. Случаи, которые пропущены, объединяются с случаями, которые должны быть запланированы на следующий день, с чуть более высоким приоритетом, поскольку к тому времени клиент уже выразил некоторое недовольство. Был большой набор причин, по которым инженер не посещал дело. Проблемы с дорожным движением были наиболее распространенными.

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

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

vpit3833
источник