Згуровский М.З., Павлов А.А.

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

Загрузить (pdf)