Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних
На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибо...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/131446 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-131446 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1314462018-03-24T03:03:17Z Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних Чупов, С.В. На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибору множин, які аналізуються алгоритмом, так щоб вони утворювали розбиття множини допустимих розв’язків задачі. Проведені експериментальні дослідження з використанням відомого тестового набору задач. Результати експериментів свідчать про високу якість, отриманих за прийнятний час, розв’язків. На основе анализа структурных особенностей задачи о многомерном булевом ранце, представлен алгоритм лексикографического поиска, в процессе работы которого определение лексикографических максимумов отдельных множеств осуществляется параллельно. Обосновывается правило выбора множеств, которые анализируются алгоритмом, так чтобы они образовывали разбиение множества допустимых решений задачи. Проведены экспериментальные исследования с использованием известного тестового набора задач. Результаты экспериментов свидетельствуют о высоком качестве, полученных за приемлемое время решений. On the basis of an analysis of the structural features of the multidimensional boolean knapsack problem it is presented the algorithm of lexicographic search in the course of work of which the determination of lexicographic maxima of separate sets is carried out in parallel. The rule of the selection of the sets, which are analyzed by the algorithm, so that they form a partition of the set of feasible values of the problem, is substantiated. Experimental researches using the known test set of problems have been conducted. The results of the experiments testify to the high quality of solutions obtained within a reasonable time. 2017 Article Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/131446 519.854.33 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибору множин, які аналізуються алгоритмом, так щоб вони утворювали розбиття множини допустимих розв’язків задачі. Проведені експериментальні дослідження з використанням відомого тестового набору задач. Результати експериментів свідчать про високу якість, отриманих за прийнятний час, розв’язків. |
| format |
Article |
| author |
Чупов, С.В. |
| spellingShingle |
Чупов, С.В. Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних Теорія оптимальних рішень |
| author_facet |
Чупов, С.В. |
| author_sort |
Чупов, С.В. |
| title |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_short |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_full |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_fullStr |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_full_unstemmed |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_sort |
наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2017 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/131446 |
| citation_txt |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT čupovsv nabliženijalgoritmparalelʹnogoleksikografíčnogopošukudlâbagatovimírnoíbulevoízadačíproranecʹprifíksovanomuvporâdkuvannízmínnih |
| first_indexed |
2023-10-18T21:02:14Z |
| last_indexed |
2023-10-18T21:02:14Z |
| _version_ |
1796151757421674496 |