Эффективный алгоритм тупиковых управлений для решения задач комбинаторной оптимизации

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