Алгоритмизация труднорешаемых задач. Часть II. Более сложные эвристики

Аннотация

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