Про способи зведення нерозв’язних задач комбінаторної оптимізації до розв’язних

Abstract

Показано, що для виділення підкласів розв’язних задач із класів нерозв’язних необхідно визначити їхню складність. За цією ознакою проведено класифікацію розв’язних задач, які виділяються за вибраною мірою подібності і способом моделювання цільової функції, за структурою вхідних даних і за структурою аргументу. На прикладі деяких нерозв’язних класів задач комбінаторної оптимізації описано способи їхнього зведення до розв’язних.

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

For the selection of subclasses of solvable problems from the classes of unsolvable ones the necessity to determine their complexity is shown in the article. On this basis the classification of solvable problems, which are allocated by the selected similarity degree and the way of modeling the objective function, according to the structure of the input data and the structure of its argument is carried out. On the example of some classes of unsolvable problems of combinatorial optimization methods their attempts to make them solvable are described.