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

⇐ Предыдущая 123 4 Следующая ⇒

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

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

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

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

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

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

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

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

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

,

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

⇐ Предыдущая 123 4 Следующая ⇒

Поделиться с друзьями:

Дата добавления: 2014-01-07; Просмотров: 444; Нарушение авторских прав?; Мы поможем в написании вашей работы!
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

studopediasu.com - Студопедия (2013 - 2026) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление

Генерация страницы за: 0.009 сек.