Коды Грея в задачах комбинаторной оптимизации

В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 0-1 задачи о ранце с...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автори:	Васянин, В.А., Ушакова, Л.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут телекомунікацій і глобального інформаційного простору НАН України 2019
Назва видання:	Математичне моделювання в економіці
Теми:	Математичні та інформаційні моделі в економіці
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/162110
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Коды Грея в задачах комбинаторной оптимизации / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2019. — № 1(14). — С. 63-69. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-162110
record_format	dspace
spelling	irk-123456789-1621102020-01-02T02:03:33Z Коды Грея в задачах комбинаторной оптимизации Васянин, В.А. Ушакова, Л.П. Математичні та інформаційні моделі в економіці В статье приводятся полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 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 http://dspace.nbuv.gov.ua/handle/123456789/162110 519.168 ru Математичне моделювання в економіці Інститут телекомунікацій і глобального інформаційного простору НАН України
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	http://dspace.nbuv.gov.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
first_indexed	2023-10-18T22:08:23Z
last_indexed	2023-10-18T22:08:23Z
_version_	1796154733169213440

Коды Грея в задачах комбинаторной оптимизации

Репозитарії

Схожі ресурси