Методы комбинаторного поиска. Дерево поиска без повторения ситуаций, страница 4

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

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

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

Допустим, например, что мы ищем корень алгебраического уравнения f(х) = 0 с непрерывной функцией f (x) и рассматриваем текущую ситуацию, заданную отрезком [x₁,x₂] с вычисленными значениями функции на его концах. Если эти значения оказываются разного знака, то очевидно, что на отрезке существует по крайней мере один корень. В этом случае текущая ситуация может быть редуцирована путем вычисления значения функции f(x) в средней точке отрезка [x₁,x₂], сравнения полученного значения со значениями f(x₁) и f(x₂) и заменой исходного отрезка той его половиной, на концах которого функция f(х) принимает значения снова разного знака. В данном случае упрощение ситуации заключается в сокращении отрезка, на котором, как нам известно, существует корень рассматриваемого уравнения.

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

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

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

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

Анализ троичной матрицы на вырожденность. Этa задача формулируется так: задана некоторая троичная матрица U, и требуется найти троичный вектор v, ортогональный каждой строке матрицы U, или убедиться в том, что такого вектора не существует (в этом случае матрица U называется вырожденной).

Напомним читателю, что два вектора ортогональны, если один из них обладает значением 0, а другой значением 1 некоторых одноименных компонент. Заметим также, что анализ троичной матрицы на вырожденность имеет массу полезных интерпретаций. Например, если матрица U задает ДНФ некоторой булевой функции f, то эта задача интерпретируется как известная в теории формального вывода задача проверки тождества f = 1. К этой задаче сводится решение и ряда других задач, рассматриваемых в настоящей книге.

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