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

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

Завантажити (pdf)