Коды Грея в задачах комбинаторной оптимизации
В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 0-1 задачи о ранце с...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут телекомунікацій і глобального інформаційного простору НАН України
2019
|
| Schriftenreihe: | Математичне моделювання в економіці |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/162110 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2019. — № 1(14). — С. 63-69. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-162110 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1621102025-02-09T14:09:34Z Коды Грея в задачах комбинаторной оптимизации Коди Грея в задачах комбінаторної оптимізації Gray codes in combinatorial optimization problems Васянин, В.А. Ушакова, Л.П. Математичні та інформаційні моделі в економіці В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 0-1 задачи о ранце с полным перебором вариантов решения. Представлены результаты экспериментального исследования, которые показывают, что коды Грея можно практически применять в схемах ветвления, например, в методе ветвей и границ, когда количество переменных в узлах ветвления решающего алгоритма не превышает 35. У статті наводяться корисні відомості для розробників алгоритмів і програм про використання кодів Грея для розв’язання комбінаторних задач з псевдобулевими функціями (поліномами від булевих змінних). Як приклад ефективності застосування цих кодів розглядається розв’язання 0-1 задачі про ранець з повним перебором варіантів розв’язку. Представлені результати експериментального дослідження, які показують, що коди Грея можна практично застосовувати в схемах розгалуження, наприклад в методі гілок і меж, коли кількість змінних у вузлах розгалуження вирішального алгоритму не перевищує 35. The article provides useful information for developers of algorithms and programs on the use of Gray codes for solving combinatorial problems with pseudoBoolean functions (polynomials from Boolean variables). As an example of the effectiveness of the use of these codes, the solution 0-1 of the knapsack problem with a full search of the solutions is considered. The results of an experimental study are presented, which show that Gray codes can be practically applied in branching schemes, for example, in the branch and bound method, when the number of variables in the branch nodes of the decision algorithm does not exceed 35. 2019 Article Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2019. — № 1(14). — С. 63-69. — Бібліогр.: 8 назв. — рос. 2409-8876 DOI: 10.35350/2409-8876-2019-14-1-63-69 https://nasplib.isofts.kiev.ua/handle/123456789/162110 519.168 ru Математичне моделювання в економіці application/pdf Інститут телекомунікацій і глобального інформаційного простору НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні та інформаційні моделі в економіці Математичні та інформаційні моделі в економіці |
| spellingShingle |
Математичні та інформаційні моделі в економіці Математичні та інформаційні моделі в економіці Васянин, В.А. Ушакова, Л.П. Коды Грея в задачах комбинаторной оптимизации Математичне моделювання в економіці |
| description |
В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 0-1 задачи о ранце с полным перебором вариантов решения. Представлены результаты экспериментального исследования, которые показывают, что коды Грея можно практически применять в схемах ветвления, например, в методе ветвей и границ, когда количество переменных в узлах ветвления решающего алгоритма не превышает 35. |
| format |
Article |
| author |
Васянин, В.А. Ушакова, Л.П. |
| author_facet |
Васянин, В.А. Ушакова, Л.П. |
| author_sort |
Васянин, В.А. |
| title |
Коды Грея в задачах комбинаторной оптимизации |
| title_short |
Коды Грея в задачах комбинаторной оптимизации |
| title_full |
Коды Грея в задачах комбинаторной оптимизации |
| title_fullStr |
Коды Грея в задачах комбинаторной оптимизации |
| title_full_unstemmed |
Коды Грея в задачах комбинаторной оптимизации |
| title_sort |
коды грея в задачах комбинаторной оптимизации |
| publisher |
Інститут телекомунікацій і глобального інформаційного простору НАН України |
| publishDate |
2019 |
| topic_facet |
Математичні та інформаційні моделі в економіці |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/162110 |
| citation_txt |
Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2019. — № 1(14). — С. 63-69. — Бібліогр.: 8 назв. — рос. |
| series |
Математичне моделювання в економіці |
| work_keys_str_mv |
AT vasâninva kodygreâvzadačahkombinatornojoptimizacii AT ušakovalp kodygreâvzadačahkombinatornojoptimizacii AT vasâninva kodigreâvzadačahkombínatornoíoptimízacíí AT ušakovalp kodigreâvzadačahkombínatornoíoptimízacíí AT vasâninva graycodesincombinatorialoptimizationproblems AT ušakovalp graycodesincombinatorialoptimizationproblems |
| first_indexed |
2025-11-26T16:43:10Z |
| last_indexed |
2025-11-26T16:43:10Z |
| _version_ |
1849871976188870656 |
| fulltext |
~ 63 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
УДК 519.168
https://orcid.org/0000-0003-4046-5243
https://orcid.org/0000-0002-9020-1329
В.А. ВАСЯНИН, Л.П. УШАКОВА
КОДЫ ГРЕЯ В ЗАДАЧАХ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ
Аннотация. В статье приводятся полезные сведения для
разработчиков алгоритмов и программ об использовании кодов Грея
для решения комбинаторных задач с псевдобулевыми функциями
(полиномами от булевых переменных). В качестве примера
эффективности применения этих кодов рассматривается решение
0-1 задачи о ранце с полным перебором вариантов решения.
Представлены результаты экспериментального исследования,
которые показывают, что коды Грея можно практически применять
в схемах ветвления, например, в методе ветвей и границ, когда
количество переменных в узлах ветвления решающего алгоритма не
превышает 35.
Ключевые слова: коды Грея, задачи комбинаторной оптимизации,
время решения задачи.
DOI: 10.35350/2409-8876-2019-14-1-63-69
Введение
В 1953 г. физик Фрэнк Грей (Frank Gray) изобрел коды Грея и получил на них
патент [1]. Изначально эти коды применялись в кодово-импульсной
модуляции для управления различными электромеханическими
переключателями и методе аналоговой передачи цифровых сигналов.
В настоящее время коды Грея используются для выявления и исправления
ошибок в системах связи, управления различными цифровыми датчиками,
кодирования номеров дорожек в жестких накопителях компьютеров и пр.
Кроме того, известно о применении кодов Грея для решения комбинаторных
задач «Ханойская башня» и «Китайские кольца» [2]. Подробнее о кодах Грея
можно узнать в книге Д. Кнута [3].
В данной статье показано, как можно применять коды Грея для
эффективного вычисления значения целевой функции и проверки
ограничений в различных схемах ветвления, например, в методах ветвей и
границ, динамического программирования и др., когда количество двоичных
(булевых) переменных в узлах ветвления невелико (менее 35). В этом случае
в узлах ветвления для каждого допустимого варианта решения можно
использовать частичный пересчет значений целевой функции и ограничений.
Рассматривается 0-1 задача о ранце (0-1 Knapsack Problems, 0-1 KP), на
примере которой показано, насколько уменьшается время решения задачи за
счет частичного пересчета значений целевой функции и ограничений по
сравнению с их полным пересчетом.
В.О. Васянін, Л.П. Ушакова, 2019
~ 64 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
1. 0-1 задача о ранце
Математическая формулировка задачи заключается в следующем. Задан
набор n предметов, для каждого из которых известна стоимость ic Z +∈ и
вес ia Z +∈ , 1,i n= . Требуется так загрузить ранец предметами, чтобы его
суммарная стоимость была максимальной
1
max
n
i i
i
c x
=
∑ , (1)
и выполнялось ограничение на суммарный размер ранца W Z +∈
1
n
i i
i
a x W
=
≤∑ , (2)
}1,0{∈ijx . (3)
Предполагается, что ia W≤ , 1,i n= и
1
n
i
i
a W
=
>∑ . Как известно,
сформулированная задача является NP-трудной, т.е. в общем случае для ее
решения не существует точного полиномиального алгоритма [4]. В книгах
[5, 6] можно найти описание трех точных псевдополиномиальных алгоритмов
решения задачи (1)-(3), основанных на методах ветвей и границ и
динамического программирования с использованием Лагранжевой и LP
релаксации. Листинги программ этих алгоритмов (expknap, minknap и
combo) на C++ приведены на странице D. Pisinger в Интернете
(www.diku.dk/~pisinger/). В этих же книгах приведены также полностью
полиномиальные приближенные схемы решения задачи 0-1 KP (FPTAS —
Fully Polynomial Time Approximation Scheme) — алгоритмы, которые за
полиномиальное время от размера входа задач и ε/1 позволяют получить
(1 )ε− гарантированное приближенное решение, где ε — сколь угодно
малое положительное число.
2. Алгоритм полного перебора на основе кодов Грея
Для полного перебора вариантов решения задачи (1)-(3) будем использовать
алгоритм генерации последовательности двоично-отраженных n -разрядных
кодов Грея, предложенный Эрлихом [7]. Алгоритм дает возможность
в процессе решения эффективно вычислять значения целевой функции (1)
и ограничения (2). Двоично-отраженный (зеркальный, рефлексивный) код
Грея определяется по следующим рекурсивным правилам:
0 ''B = , 1 0 1 r
n n nB B B+ = , 0,1, 2,3,...n = , (разряды добавляются слева) или
0 ''B = , 1 0 1r
n n nB B B+ = , 0,1, 2,3,...n = , (разряды добавляются справа),
~ 65 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
где 0 ''B = — пустая строка, nB — бинарная последовательность Грея,
состоящая из n битовых строк, 0 nB и 0nB — последовательность nB
с префиксом 0 в начале и конце каждой строки, 1 r
nB и 1r
nB —
последовательность nB в обратном порядке с префиксом 1 в начале и конце
каждой строки. Поскольку последняя строка в nB эквивалентна первой
строке в r
nB , то ясно, что на каждом шаге 1nB + изменяется ровно один бит,
если nB обладает тем же свойством. С каждым шагом длина строк
увеличивается на 1, а их количество — вдвое. Таким образом, n -разрядный
код Грея есть упорядоченная циклическая последовательность 2n
n -разрядных строк, в которой последовательные строки различаются только
одним битом (разрядом). В алгоритмах полного перебора для вычисления
значений различных функций с помощью кодов Грея удобно эти коды
представлять упорядоченным списком номеров разрядов, изменяющих свое
значение на противоположное при переходе от текущей строки к следующей.
Такую последовательность переходов nP можно определить по следующим
рекурсивным правилам: 1 1P = , 1 1, ,n n nP P n P− −= , 2,3, 4,...n = . Длина
последовательности nP равна 2 1n − , а нумерацию разрядов в
последовательности можно выполнять справа налево или наоборот.
Например, для 4n = и начальной строки 0000
4P =1,2,1,3,1,2,1,4,1,2,1,3,1,2,1, а ее длина равна 42 1 15− = .
Соответствующая последовательность бинарных строк при нумерации
разрядов слева направо имеет вид: 0000, 1000, 1100, 0100, 0110, 1110, 1010,
0010, 0011,1011, 1111, 0111,0101, 1101, 1001, 0001. При нумерации разрядов
справа налево получим перевернутую последовательность, соответствующую
первому рекурсивному определению 1nB + . Интересно заметить, что если
построить граф, вершины которого соответствуют бинарным
последовательностям длины n , а ребра соединяют две вершины,
отличающиеся только одним разрядом, то такой граф представляет двоичный
n -мерный куб. При этом построенная бинарная последовательность
соответствует гамильтонову пути в таком графе.
Для генерации последовательности переходов nP в бинарной строке
iB b= , 1, 1i n= + , определим вектор указателей iP p= , 1, 2i n= + ,
который имитирует стек для рекурсивного определения nP . Оптимальное
решение *
ix , 1,i n= будем сохранять в векторе opt opt
iB b= , 1, 1i n= + ,
где: если 0opt
ib = , то * 0ix = ; если 1opt
ib = , то * 1ix = ; 1,i n= . Размерности
векторов P , B и optB увеличены соответственно на две и одну единицу из-
за специфики работы алгоритма. Знак «←» означает операцию
присваивания.
~ 66 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
Алгоритм OPT1 с частичным пересчетом целевой функции и
ограничения
1. 1CSUM c← ; 1ASUM a← ; 0CSUMOPT ← ; 0B ← ; 0optB ← .
2. Для { 1, 2 }i i n= + выполнить ip i← .
3. 1i ← .
4. Пока 1i n< + выполнять шаги 5-7.
5. Если 0ib = , то iCSUM CSUM c← − ; iASUM ASUM a← − , иначе
iCSUM CSUM c← + ; iASUM ASUM a← + .
6. Если ASUM W≤ , то если CSUM CSUMOPT> выполнить:
CSUMOPT CSUM← ; optB B← ; ASUMOPT ASUM← .
7. 1i p← ; 1i ib b← − ; 1 1p ← ; 1i ip p +← ; 1 1ip i+ ← + .
8. Конец алгоритма. Вывести значения: *
1
max n
i ii
c x CSUMOPT
=
=∑ ;
*
1
n
i ii
a x ASUMOPT
=
=∑ ; W ; optB .
В варианте решения задачи с полным пересчетом целевой функции и
ограничения (алгоритм OPT2) шаг 1 заменится на
1. 0CSUMOPT ← ; 0B ← ; 0optB ← ,
а шаг 5 заменится на
5. 0CSUM ← ; 0ASUM ← . Для { 1, }j j n= выполнить
j jCSUM CSUM c b← + ∗ ; j jASUM ASUM a b← + ∗ .
3. Экспериментальное сравнение алгоритмов OPT1 И OPT2
Сравнение быстродействия алгоритмов OPT1 и OPT2 проводилось на
примерах, сгенерированных датчиком псевдослучайных чисел. Для всех
размерностей задачи, которая изменялась от 5n = до 36n = , стоимости
предметов ic и их веса ia генерировались в диапазоне от 5 до 10 и от 1 до 20
соответственно. При проведении эксперимента проверялась также точность
решения задачи (1)-(3) «жадным» эвристическим алгоритмом OPT3 с
временной сложностью ( log )O n n . Алгоритм основан на предварительном
упорядочении предметов в заданном наборе по невозрастанию их удельных
стоимостей /i ic a , 1,i n= с последующим выбором предметов в ранец до
тех пор, пока выполняется ограничение на размер ранца W . Хорошо
известно, см. например, [6, 8], что решения OPT3 = *
1
max n
i ii
c x
=∑ ,
полученные «жадным» алгоритмом, могут отличаться от оптимальных не
более чем в два раза, при выборе окончательной стоимости ранца из условия
* *
1 1
max {max ,max }n n
i i i i ii i
c x c x c
= =
=∑ ∑ , где max ic , 1,i n= —
максимальная стоимость предмета в заданном наборе.
~ 67 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
На рис. 1 показано время решения задачи (1)-(3) (с точностью до двух
знаков после запятой) на ПК с тактовой частотой 2.66 GHz для алгоритмов
OPT1 и OPT2 с частичным и полным пересчетом целевой функции и
ограничения. Как видно из рис. 1, алгоритм OPT1 может применяться для
практических расчетов в схемах ветвления, когда количество переменных
в узлах дерева ветвления не превышает 35 (для 35n = время счета около
8 минут). Алгоритм OPT1 для вариантов 5-10 быстрее алгоритма OPT2
в среднем в 7 раз.
Рисунок 1 – Время решения задачи в сек. с частичным (T1, алгоритм OPT1) и
полным (T2, алгоритм OPT2) пересчетом целевой функции и ограничений
На рис. 2 приведены результаты решения задачи (1)-(3) точным
алгоритмом OPT1 и «жадным» алгоритмом OPT3 (результаты решений
алгоритмов OPT1 и OPT2 естественно совпадают).
Рисунок 2 – Результаты оптимального (OPT1) и приближенного (OPT3)
решения задачи
~ 68 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
Значения *
1
n
i ii
a x ASUMOPT
=
=∑ показаны для алгоритма OPT1.
Значения целевой функции, полученные «жадным» алгоритмом, отличаются
от оптимальных в пределах DEL% от 0 до 12,5%. Алгоритм OPT3 имеет
полиномиальную оценку временной сложности и его можно применять на
практике для решения задачи (1)-(3) большой размерности, когда лицу,
принимающему решение, необходимо достаточно быстро получить
приближенное значение целевой функции при ограниченных
вычислительных ресурсах. Так, например, задача (1)-(3) была решена для
10000n = с теми же границами изменения значений ic и ia за 0,11 сек. При
этом OPT3 = 70598, ASUMOPT = 103985 при W = 104000.
Все программы написаны на языке Фортран в среде Microsoft Developer
Visual Studio и могут быть адаптированы для работы в системе параллельного
программирования Intel® Parallel Studio XE 2018, в которую вошли
последние версии компиляторов С/С++ и Фортран
(https://software.intel.com/ru-ru/try-buy-tools).
Заключение
1. В статье показано, как можно применять на практике двоично-отраженные
коды Грея для решения комбинаторных задач с псевдобулевыми функциями
(полиномами от булевых переменных), когда количество переменных в узлах
дерева ветвления решающего алгоритма не превышает 35.
2. На примере решения 0-1 задачи о ранце наглядно продемонстрирована
вычислительная эффективность предложенного алгоритма полного перебора
решений с ограниченным пересчетом значения целевой функции и
ограничения задачи.
3. Приведены результаты вычислительного эксперимента, которые
показали возможность использования «жадного» алгоритма решения
0-1 задачи о ранце на практике для инженерных расчетов в задачах большой
размерности ( 10000n = и более).
СПИСОК ЛИТЕРАТУРЫ
1. Gray F. Pulse code communication // U.S. Patent 2632058, March 17, 1953.
2. Гарднер М. Математические головоломки и развлечения: 2-е изд., испр. и дополн. /
Пер. с англ. — М.: «Мир», 1999, 447 с.
3. Knuth D.E. The Art of Computer Programming. Volume 4A / Combinatorial
Algorithms, Part 1. — Addison Wesley Longman, Inc., 2011. — 933 p.
4. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of
NP-Completeness. — W. H. Freeman & Co. New York, NY, USA, 1979. — 338 p.
5. Martelo S., Toth P. Knapsack problems: algorithms and computer implementations. —
Great Britain: Wiley, 1990. — 296 p.
6. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. — Springer-Verlag Berlin
Heidelberg, 2004. — 548 p.
7. Bitner J.R., Ehrlich G., Reingold E.M. Efficient Generation of the Binary Reflected
Gray Code and its Applications // Comm. ACM. — 1976. — 19. — P. 517-521.
8. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений. —
М: МФТИ, 2008. — 326 с.
~ 69 ~
Математичне моделювання в економіці, №1, 2019. ISSN 2409-8876
REFERENCES
1. Gray F. Pulse code communication // U.S. Patent 2632058, March 17, 1953.
2. Gardner M. Mathematical puzzles and diversions. — Penguin Press Science S., New
edition, 1991. — 160 p.
3. Knuth D.E. The Art of Computer Programming. Volume 4A / Combinatorial
Algorithms, Part 1. — Addison Wesley Longman, Inc., 2011. — 933 p.
4. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of
NP-Completeness. — W. H. Freeman & Co. New York, NY, USA, 1979. — 338 p.
5. Martelo S., Toth P. Knapsack problems: algorithms and computer implementations. —
Great Britain: Wiley, 1990. — 296 p.
6. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. — Springer-Verlag Berlin
Heidelberg, 2004. — 548 p.
7. Bitner J.R., Ehrlich G., Reingold E.M. Efficient Generation of the Binary Reflected Gray
Code and its Applications // Comm. ACM. — 1976. — 19. — P. 517-521.
8. Kuzyrin N.N., Fomin S.A. Effektivnie algoritmi i slognost vithisleni. — M: MFTI,
2008. — 326 s. (In Russian).
Стаття надійшла до редакції 20.12.2018.
2. Gardner M. Mathematical puzzles and diversions. — Penguin Press Science S., New edition, 1991. — 160 p.
|