Пример. Для точки (1,1,0,0)

Вершины, у которых , называются конечными. При попадании в конечную вершину (КВ) выполняем шаг назад.

Пример. Конечные точки для : (0001), (0101).

Из полученного в примере куба для получим дерево

Опишем правила, сокращающие перебор.

Критерий недопустимости (КН). Позволяет выяснить, можно ли при движении вперёд из текущей точки найти допустимую точку и указывает, когда такое невозможно. Ограничения запишем в виде (каноническом):

,

Для допустимых точек все , для недопустимых существует.

Пример. В точке (1,1,0,0) . Первое и третье ограничения выполнены, второе – нет. Точка недопустима.

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

- множество номеров ограничений, невыполняющихся в точке x;

,

– множество индексов переменных, по которым из точки x еще можно сделать шаг вперед, и при которых коэффициенты в i -м ограничении отрицательны (только за счет увеличения переменных при этих коэффициентах можно добиться выполнения -го ограничения).

Дата добавления: 2014-01-07