8.2. Особенности оптимизационных комбинаторных задач

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

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

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

Комбинаторные задачи характерны еще тем, что множество, среди элементов которого отыскивается решение, всегда конечно. Реализовав полный перебор, либо найдем решение, либо убедимся в том, что решения нет. Таким образом, всякая подобная задача может быть решена за конечное время. Однако это не значит, что она может быть решена за практически приемлемое время даже с помощью самой быстродействующей вычислительной машины.