Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних
|
|
| Creator |
Чупов, С.В.
|
|
| Description |
На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибору множин, які аналізуються алгоритмом, так щоб вони утворювали розбиття множини допустимих розв’язків задачі. Проведені експериментальні дослідження з використанням відомого тестового набору задач. Результати експериментів свідчать про високу якість, отриманих за прийнятний час, розв’язків.
На основе анализа структурных особенностей задачи о многомерном булевом ранце, представлен алгоритм лексикографического поиска, в процессе работы которого определение лексикографических максимумов отдельных множеств осуществляется параллельно. Обосновывается правило выбора множеств, которые анализируются алгоритмом, так чтобы они образовывали разбиение множества допустимых решений задачи. Проведены экспериментальные исследования с использованием известного тестового набора задач. Результаты экспериментов свидетельствуют о высоком качестве, полученных за приемлемое время решений. 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. |
|
| Date |
2018-03-23T10:55:32Z
2018-03-23T10:55:32Z 2017 |
|
| Type |
Article
|
|
| Identifier |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр.
2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/131446 519.854.33 |
|
| Language |
uk
|
|
| Relation |
Теорія оптимальних рішень
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|