Коды Грея в задачах комбинаторной оптимизации
В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 0-1 задачи о ранце с...
Saved in:
| Published in: | Математичне моделювання в економіці |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут телекомунікацій і глобального інформаційного простору НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/162110 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2019. — № 1(14). — С. 63-69. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862577518051065856 |
|---|---|
| author | Васянин, В.А. Ушакова, Л.П. |
| author_facet | Васянин, В.А. Ушакова, Л.П. |
| citation_txt | Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2019. — № 1(14). — С. 63-69. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичне моделювання в економіці |
| description | В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 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.
|
| first_indexed | 2025-11-26T16:43:10Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-162110 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2409-8876 |
| language | Russian |
| last_indexed | 2025-11-26T16:43:10Z |
| publishDate | 2019 |
| publisher | Інститут телекомунікацій і глобального інформаційного простору НАН України |
| record_format | dspace |
| spelling | Васянин, В.А. Ушакова, Л.П. 2020-01-01T18:58:27Z 2020-01-01T18:58:27Z 2019 Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 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 В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 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. ru Інститут телекомунікацій і глобального інформаційного простору НАН України Математичне моделювання в економіці Математичні та інформаційні моделі в економіці Коды Грея в задачах комбинаторной оптимизации Коди Грея в задачах комбінаторної оптимізації Gray codes in combinatorial optimization problems Article published earlier |
| spellingShingle | Коды Грея в задачах комбинаторной оптимизации Васянин, В.А. Ушакова, Л.П. Математичні та інформаційні моделі в економіці |
| title | Коды Грея в задачах комбинаторной оптимизации |
| title_alt | Коди Грея в задачах комбінаторної оптимізації Gray codes in combinatorial optimization problems |
| title_full | Коды Грея в задачах комбинаторной оптимизации |
| title_fullStr | Коды Грея в задачах комбинаторной оптимизации |
| title_full_unstemmed | Коды Грея в задачах комбинаторной оптимизации |
| title_short | Коды Грея в задачах комбинаторной оптимизации |
| title_sort | коды грея в задачах комбинаторной оптимизации |
| topic | Математичні та інформаційні моделі в економіці |
| topic_facet | Математичні та інформаційні моделі в економіці |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/162110 |
| work_keys_str_mv | AT vasâninva kodygreâvzadačahkombinatornoioptimizacii AT ušakovalp kodygreâvzadačahkombinatornoioptimizacii 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 |