научная статья по теме ОСНОВНЫЕ СВОЙСТВА РЕШЕТОК КУБОВ, АЛГОРИТМЫ ИХ ПОСТРОЕНИЯ И ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ В ДИСКРЕТНОЙ ОПТИМИЗАЦИИ Математика

Текст научной статьи на тему «ОСНОВНЫЕ СВОЙСТВА РЕШЕТОК КУБОВ, АЛГОРИТМЫ ИХ ПОСТРОЕНИЯ И ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ В ДИСКРЕТНОЙ ОПТИМИЗАЦИИ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 1, с. 121-134

УДК 519.7

ОСНОВНЫЕ СВОЙСТВА РЕШЕТОК КУБОВ, АЛГОРИТМЫ ИХ ПОСТРОЕНИЯ И ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ В ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

© 2015 г. Р. В. Хачатуров

(119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: rv_khach@yahoo.ie Поступила в редакцию 25.04.2012 г.

Переработанный вариант 16.06.2014 г.

Описаны основные свойства нового типа решеток — решетки кубов. Показано, что множество всех субкубов N-мерного куба при соответствующем выборе для них операций объединения и пересечения образует решетку, названную решеткой кубов. Описываются алгоритмы построения таких решеток, иллюстрируются результаты работы этих алгоритмов для различных размерностей решеток. Доказано, что решетка кубов является решеткой с дополнениями, что позволяет решать на ней задачи минимизации и максимизации супермодулярных функций. Приводятся некоторые примеры таких функций. Показана возможность применения ранее разработанных эффективных алгоритмов оптимизации, постановки и решения новых классов задач на решетках кубов. Библ. 8. Фиг. 12.

Ключевые слова: конечные решетки, решетка кубов, булеан, гиперкуб, супермодулярные функции, субмодулярные функции, дискретная оптимизация, комбинаторная оптимизация, математическое программирование, супермодулярное программирование.

DOI: 10.7868/S004446691501010X

1. ВВЕДЕНИЕ

Решеткой называется непустое множество K, в котором для любых двух его элементов определены операции объединения и и пересечения п, причем результаты этих операций также являются элементами этого множества, а сами эти операции обладают следующими четырьмя свойствами (см. [1]):

1) идемпотентность: a n a = a, a u a = a;

2) коммутативность: a n b = b n a, a u b = b u a;

3) ассоциативность: (a n b) n c = a n (b n c), (a u b) u c = a u (b u c);

4) тождества поглощения: a n (a u b) = a, a u (a n b) = a.

При этом для разных типов решеток понятия объединения и пересечения могут вводиться по-разному. Например, для булевых решеток (гиперкубов) эти понятия эквивалентны теоретико-множественным объединению и пересечению. Для нового типа решеток — решетки кубов, свойства которой исследуются в данной работе, эти понятия вводятся более сложно. Показано, что число всех субкубов гиперкуба размерности N равно 3N. Множество всех таких субкубов при соответствующем выборе для них операций объединения и пересечения образует решетку, названную решеткой кубов (см. [2], [3]). Общее число узлов этой решетки равно (3N + 1). Описываются два алгоритма построения такой решетки и перебора ее элементов. Приводятся примеры задач оптимизации супермодулярных функций на решетках кубов.

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

1. Построение эффективных алгоритмов перебора всех элементов решетки, основанных на свойствах конкретной решетки.

2. Разработка (на основе этих алгоритмов) методов оптимизации функции, заданной на этой решетке.

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

/(X) + /(У) - /(X и У) - /(X п 7) < 0.

Используя это свойство, для других типов решеток (булевых решеток, решеток с дополнениями, решеток разбиения, решеток векторных подпространств, геометрических решеток, решеток прямого произведения цепей) были построены эффективные методы и алгоритмы, исключающие полный перебор, было получено много важных теоретических результатов в этой области, решено большое количество конкретных задач (см. [3], [4]). Например, задачи по оптимальному размещению различных предприятий, освоению и развитию нефтегазодобывающих регионов и т.д. В данной работе рассматриваются возможности применения этих методов для оптимизации супермодулярных функций на решетках кубов.

2. АВТОМАТИЗИРОВАННАЯ ВИЗУАЛИЗАЦИЯ РЕШЕТОК БОЛЬШОЙ РАЗМЕРНОСТИ

НА ПРИМЕРЕ БУЛЕАНОВ (ГИПЕРКУБОВ)

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

Для исследования структуры гиперкубов (булеанов) больших размерностей были разработаны алгоритмы и компьютерные программы для различного представления гиперкубов в пространстве и на плоскости (см. [2], [3]—[6]). Эти алгоритмы позволяют вращать М-мерный гиперкуб в ^-мерном евклидовом пространстве N > M) вокруг любой из координатных осей и затем проецировать его на плоскость. Кроме того, эти проекции можно изменять, задавая соответствующий набор базисных векторов и получая различные изображения гиперкубов с сохранением их свойств как булевых решеток.

Приведем примеры проекций и диаграмм кубов различных размерностей, полученные с помощью разработанных алгоритмов и компьютерных программ, одновременно демонстрирующие сложность структуры и красоту многомерных гиперкубов для m = 4, 8, 16 (см. фиг. 1—5).

Из фиг. 3 и фиг. 4 видно, что в случае ортогональной симметричной проекции 16-мерного гиперкуба на плоскость ни одна из проекций его вершин не закрывает другую.

3. МНОЖЕСТВО СУБКУБОВ МНОГОМЕРНОГО КУБА

Пусть Ст — куб размерности m. Известно, что количество субкубов размерности ноль (вершин

куба) в кубе Ст равно 2т . Сколько субкубов различных размерностей (меньших или равных m)

содержится в кубе Ст ? Аналогичные вопросы уже ставились в виде комбинаторных задач, и ответы были даны в [7], [8]. В следующих лемме и теореме дано подробное решение этой задачи (см. [2], [6]).

Обозначим буквой К множество всех субкубов куба Ст, их число равно |К|. Через Кг обозначим множество всех субкубов размерности г, их число равно \КГ\.

Лемма 1. Количество \КГ\ всех субкубов размерности г (0 < г < т) в кубе Ст равно

\КГ\ = 2т-г ■ Сгт = 2т-г--т-.

г!(т - г)!

Доказательство. Количество всех вершин куба Ст равно 2т .

Количество всех субкубов размерности г, содержащих в себе какую-либо фиксированную вершину куба Ст , равно числу сочетаний из m по г (Сгт).

Фиг. 1. Представление 4-мерного куба. Симметричная проекция и две геометрически различные диаграммы, полученные в результате выбора разных по длине и направлению базисных векторов.

Количество вершин в каждом субкубе размерности г равно 2г.

Следовательно, чтобы определить число всех субкубов размерности г в кубе Ст, необходимо умножить 2т (число всех вершин куба Ст) на Сгт (число всех субкубов размерности г, содержащих в себе какую-либо фиксированную вершину куба Ст), и разделить результат на 2г (число вершин в кубе размерности г), чтобы убрать повторение одних и тех же кубов размерности г, так

как в величине 2т ■ Сгт каждый г-мерный куб учитывается 2г раз, как содержащий в себе 2г собственных вершин.

Исходя из этого, получаем

Кг\ = = 2т-г • СГт .

Лемма доказана.

Теорема 1. Суммарное число субкубов всех размерностей в кубе размерности т равно 3 т. Доказательство. Из леммы 1 следует, что в кубе Ст число всех субкубов |К| равно:

т т

К = XI Кг\ = X 2т-г. Ст.

г=0 г=0

С другой стороны, в соответствии с формулой Бинома Ньютона, имеем

т

/ , т.\т X 1 т-г т г ^г

(а + Ь) = X а ■ Ь ■ Ст.

г=0

Из этой формулы для a = 2, Ь = 1 получаем

т т

3т = х 2т-г. 1г. Ст = х 2т-г • Ст.

г=0 г=0

Фиг. 3. Ортогональная симметричная проекция 16-мерного гиперкуба (показаны только вершины: 216 = = 65536 точек).

Сравнивая первое и третье уравнения, получаем |К| = 3т. Теорема доказана.

4. ПОЛУРЕШЕТКИ И РЕШЕТКИ КУБОВ: ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ, СВОЙСТВА Обозначим через С любой элемент множества К. Элемент С размерности г, обозначим через Сг, г = 0,1,2,..., т. Каждый С е К может описываться двумя подмножествами ю1,ю2 с I, где ю1 с ю2 I = {0,1,2,..., т}, ю1 — "нижняя", ю2 — "верхняя" вершины множества вершин куба С. Для куба Ст ю1 = 0, ю2 = I, Ст = (0; I). Для каждого конкретного куба С можно определить ю1 и ю2, ю1 с ю2, и представить С в виде С = (ю1; ю2). Например, кубы С1 = (ю1; ю2), где ю1 с ю2 и |ю2= 1, а для любого куба размерности г Сг = (ю1; ю2), где ю1 с ю2 и |ю2\ю^ = г, 0 < г < т. Количество вершин в кубе С = (ю1; ю2) равно 2 , а количество всех субкубов равно 3 .

Введем, для элементов С е К, определения объединения и и пересечения п. Пусть С1 =

= (ю1; ю2), С2 = (®2; ®2), ®1 с ®2; ®2 с ®2, тогда определим операцию объединения следующим образом:

С1 и С2 = С = (®1 п®2;ю2 и®2). (1)

Объединение верхних множеств вершин кубов всегда включает в себя пересечение нижних множеств вершин

(®2 и ®2) ^ (ю1 п ®2) откуда С = С1 и С2 е К, т.е. С — куб. Аналогично вводится определение пересечения:

1 2 1 2

С1 п С2 = С = (ю1 и ю1;ю2 п ю2), (2)

если (ю1 и ю2) с (ю2 п ю2), то С = С1 п С2 е К.

Фиг. 4. Центральная часть ортогональной симметричной проекции 16-мерного гиперкуба (показаны только вершины).

Например:

С1 = ({3}; {1,2,3,4}), С2 = ({2}; {2,3,4,5}), С и С2 = (0; {1,2,3,4,5}), С п С2 = ({2,3}, {2,3,4}).

Но не всегда (ю1 и ю2) с (ю2 п ю2). Например,

С1 = ({1,2};{1,2,3}), С2 = ({2,4};{1,2,4}), С = С пС2 = ({1,2,4};{1,2}).

Так как {1,2,4} <£. {1,2}, то ({1,2,4}; {1,2}) — не куб и не принадлежит К. Следовательно, множество К — не решетка, так как операция пересечения (2) на нем не определена. С операцией объединения (1) множество К — полурешетка, а именно, К является верхней полурешеткой (К, и).

Однако, можно ввести другую операцию пересечения для множества К следующим образом:

с п С = 1с(ю1 и ю2; ю2п ю2)' (ю1 и ю2)с (®2п ю2), (3)

12^ 12 12 [0, (Ю1 и®!) <£. (ю2 П ®2).

Тогда на множестве К выполняются 2 операции объединения (1) и пересечения (3). Нетрудно убедиться, что

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком