Метод неявного перебора по векторной решетке

Векторной решеткой называют математическую структуру, определяющую расположение и взаимосвязь различных значений целочисленного n-мерного вектора х=(х1,..,хn), у которого каждая компонента хi может принимать целочисленные значения начиная с хi-min, и заканчивая хi-max.

Отдельные точки вектора х располагаются по уровням Хэмминга, которые определяются с помощью понятия расстояния Хэмминга.

Расстоянием Хэмминга между двумя векторами Х¹=(х1¹,..,хn¹) и Х²=(х1²,..,хn²) называется величина определяемая следующим образом

n

δ = Σ ׀ xi¹ – xi² ׀

і=1

Уровнем Хэмминга называют местоположение точек векторной решетки расстояние Хемминга до которых от одной точки к другой одинаковы.

При этом номер уровня принимают равным величине расстояния Хемминга.

Формирование векторной решетки завершает правило, согласно которому 2 ее точки, находящиеся на соседних уровнях и стоящие друг от друга на растоянии Хемминга равном единице соедененные дугой.

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

Шаг вперед это переход на уровень с большим номером.

Шаг назад – это обратное движение.

Для сокращения перебора по векторной решетке в методе исспользуется 3 критерия:

1. Критерий недопустимости

2. Критерий планомерного исключения альтернатив

3. Критерий предпочтительной переменной

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

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

Критерий предпочтительной переменной (КПП) – это критерий для упорядочения шагов вперед из каждой недопустимой точки не отсеяной по критерию недопустимости после 1-го прихода в нее.

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