8.4. Методы комбинаторного поиска

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

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

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

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