Про універсальність методу структурно-алфавітного пошуку

Про універсальність методу структурно-алфавітного пошуку

Наводяться ознаки подібності задач комбінаторної оптимізації, завдяки якій вони розв’язуються одним методом або модифікацією одного і того ж алгоритму. Ця властивість показана на прикладі задач, цільову функцію в яких задано на перестановках. Показано, що методом структурно-алфавітного пошуку одним...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2016
1. Verfasser: Тимофієва, Н.К.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Schriftenreihe:Індуктивне моделювання складних систем
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/125060
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:Про універсальність методу структурно-алфавітного пошуку / Н.К. Тимофієва // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2016. — Вип. 8. — С. 185-193. — Бібліогр.: 9 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-125060
record_format dspace
spelling irk-123456789-1250602017-10-14T03:03:43Z Про універсальність методу структурно-алфавітного пошуку Тимофієва, Н.К. Наводяться ознаки подібності задач комбінаторної оптимізації, завдяки якій вони розв’язуються одним методом або модифікацією одного і того ж алгоритму. Ця властивість показана на прикладі задач, цільову функцію в яких задано на перестановках. Показано, що методом структурно-алфавітного пошуку одним і тим же алгоритмом розв’язується задача комівояжера, розміщення одногабаритних об’єктів, задача про призначення. Приводятся признаки сходства задач комбинаторной оптимизации, благодаря которой они решаются одним методом или модификацией одного и того же алгоритма. Это свойство показано на примере задач, целевая функция в которых задана на перестановках. Показано, что методом структурно-алфавитного поиска одним и тем же алгоритмом решается задача коммивояжера, размещение одногабаритных объектов, задача о назначениях. The signs of similarity of problems of combinatorial optimization due to which they are untied one method or modification of the same algorithm are pointed. This property is illustrated on the example by the problems, the objective function which is defined on permutations. It is shown that by a structure-alphabetical search method the same algorithm is untie the problem of traveling salesman, a location problem for objects of the same size, the problem of the appointment. 2016 Article Про універсальність методу структурно-алфавітного пошуку / Н.К. Тимофієва // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2016. — Вип. 8. — С. 185-193. — Бібліогр.: 9 назв. — укр. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/125060 519.816 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 2016
url http://dspace.nbuv.gov.ua/handle/123456789/125060
citation_txt Про універсальність методу структурно-алфавітного пошуку / Н.К. Тимофієва // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2016. — Вип. 8. — С. 185-193. — Бібліогр.: 9 назв. — укр.
series Індуктивне моделювання складних систем
work_keys_str_mv AT timofíêvank prouníversalʹnístʹmetodustrukturnoalfavítnogopošuku
first_indexed 2025-07-09T02:30:03Z
last_indexed 2025-07-09T02:30:03Z
_version_ 1837134729267118080
fulltext Про універсальність методу структурно-алфавітного пошуку Індуктивне моделювання складних систем, випуск 8, 2016 185 УДК 519.816 ПРО УНІВЕРСАЛЬНІСТЬ МЕТОДУ СТРУКТУРНО-АЛФАВІТНОГО ПОШУКУ Н.К.Тимофієва Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Tymnad@gmail.com Наводяться ознаки подібності задач комбінаторної оптимізації, завдяки якій вони розв’язуються одним методом або модифікацією одного і того ж алгоритму. Ця властивість показана на прикладі задач, цільову функцію в яких задано на перестановках. Показано, що методом структурно-алфавітного пошуку одним і тим же алгоритмом розв’язується задача комівояжера, розміщення одногабаритних об’єктів, задача про призначення. Ключові слова: подібність задач комбінаторної оптимізації, комбінаторна конфігурація, цільова функція, метод структурно-алфавітного пошуку. The signs of similarity of problems of combinatorial optimization due to which they are untied one method or modification of the same algorithm are pointed. This property is illustrated on the example by the problems, the objective function which is defined on permutations. It is shown that by a structure-alphabetical search method the same algorithm is untie the problem of traveling salesman, a location problem for objects of the same size, the problem of the appointment. Keywords: Similarity of problems of combinatorial optimization, combinatorial configuration, objective function, structure-alphabetical search method. Приводятся признаки сходства задач комбинаторной оптимизации, благодаря которой они решаются одним методом или модификацией одного и того же алгоритма. Это свойство показано на примере задач, целевая функция в которых задана на перестановках. Показано, что методом структурно-алфавитного поиска одним и тем же алгоритмом решается задача коммивояжера, размещение одногабаритных объектов, задача о назначениях. Ключевые слова: Сходство задач комбинаторной оптимизации, комбинаторная конфигурация, целевая функция, метод структурно-алфавитного поиска. Вступ В статті наведено універсальний алгоритм розв’язання задач комбінатор- ної оптимізації, які подібні за аргументом цільової функції. Описаний алгоритм розроблено на основі методу структурно-алфавітного пошуку. Показано, що оптимальний розв’язок для задачі комівояжера, розміщення одногабаритних об’єктів, задачі про призначення знаходиться на множині перестановок. За цією ознакою вони подібні, а тому і розв’язуються за однією і тією ж обчислюваль- ною схемою. 1. Постановка задачі В комбінаторній оптимізації можна навести багато прикладів, коли задачі з різних класів розв’язуються за однією і тією ж обчислювальною схемою, на- приклад [1–5]. Таке явище пов’язане з подібністю задач цього класу. В [6] на- Тимофієва Н.К. Індуктивне моделювання складних систем, випуск 8, 2016 186 ведено деякі ознаки, за якими можна встановлювати подібність задач як в ком- бінаториці так і в комбінаторній оптимізації. За цими ознаками розробляються універсальні алгоритми як для розв’язання задач комбінаторної оптимізації так і для генерування комбінаторних множин. Тому однією з проблем в теорії ком- бінаторної оптимізації є виявлення властивості подібності цих задач з метою узагальнення та використання для їхнього розв’язання ефективних підходів, які дають можливість знаходити глобальний або наближений до глобального ре- зультат. Нижче наведено універсальний алгоритм розв’язання задачі комівояжера, задачі про призначення, розміщення одногабаритних об’єктів, які подібні за ар- гументом цільової функції. В основі цього алгоритму покладено метод структу- рно-алфавітного пошуку. Виявлення різноманітних ознак, за якими визначається подібність задач комбінаторної оптимізації різних класів, що дозволяє узагальнювати та викори- стовувати для їхнього розв’язання ефективні методи та алгоритми. 2. Загальна математична постановка задачі комбінаторної оптимізації Наведемо загальну постановку задачі комбінаторної оптимізації [7]. Задачі цього класу, як правило, задаються однією або кількома множинами, на- приклад A та B , елементи яких мають будь-яку природу. Назвемо ці множини базовими. Наявні два типи задач. В першому типі кожну з цих множин подамо у вигляді графа, вершинами якого є її елементи, а кожному ребру поставлено у відповідність число Rclt , яке називають вагою ребра ( R – множина дійсних чисел); },...,1{ nl , }~,...,1{ nt , n – кількість елементів множини A , n~ – кількість елементів множини B . Покладемо, що nn ~ . Між елементами цих множин існують зв'язки, числове значення яких назвемо вагами. Величини ltc назвемо вхідними даними та задамо їх матрицями. В другому типі задач між елементами заданої множини зв'язків не існує, а вагами є числа Rv j , },...,1{ nj , яким у відповідність поставлено деякі властивості цих елементів, числові значення яких задаються скінченними послідовностями, що також є вхідними даними. Ці величини визначають значення цільової функції. Для обох типів задач із елементів однієї або кількох із заданих множин, наприклад Aal , },...,1{ nl , утворюється комбінаторна множина W – сукупність комбінаторних конфігурацій певного типу (перестановки, вибірки різних типів, розбиття тощо). На елементах w комбінаторної множини W вводиться цільова функція )(wF . Необхідно знайти елемент * w множини W , для якого )(wF набуває екстремального значення при виконанні заданих обмежень. Про універсальність методу структурно-алфавітного пошуку Індуктивне моделювання складних систем, випуск 8, 2016 187 Подамо елементи h наддіагоналей симетричної комбінаторної матриці )( k wQ комбінаторною функцією ,...),)1(((|),)(( 11 kmk wfwjf )),)((..., k m wmf , а елементи h наддіагоналей симетричної матриці C – фу- нкцією натурального аргументу ))(...,),1((|)( 1 mj m , де 2 )1(nn m – кількість елементів h наддіагоналей матриць C та )( k wQ , 1,1 nh . Верхній індекс k ( },...,1{ qk ) у k w позначає порядковий номер k w у W , q – кількість k w у W . Якщо матриці )( k wQ та C – несиметричні, то mk wjf 1|),)(( та m j 1|)( містять усі їхні елементи, а 2 nm (або nnm ~ ). Сумарне значення функції цілі )( k wF запишемо як )(),)(()( 1 jwjfwF k m j j k . (1) 3. Метод структурно-алфавітного пошуку Метод структурно-алфавітного пошуку ґрунтується на розпізнаванні вхі- дної інформації та певному впорядкуванні комбінаторних конфігурцій. В ньому використано відомий розв’язний випадок, який задано двома системами пере- становок )(d і )(e , на яких уведено цільову функцію de [8]. Для цих систем визначено перестановки, для яких de набуває найбільшого або найменшого значень. Якщо елементи перестановки із системи )(d впорядковані від більшого елемента до меншого, а із )(e – від меншого елемента до більшого, то значення de є глобальним мінімумом. Якщо елементи обох таких перестано- вок упорядковані від меншого елемента до більшого, то значення de є гло- бальним максимумом. Цей розв'язний випадок не належить жодному класу із класів задач комбінаторної оптимізації. З метою використання оговореного розв'язного випадку для розв'язання задач комбінаторної оптимізації методом структурно-алфавітного пошуку вста- новимо зв'язок між прикладними задачами і оговореним вище розв'язним ви- падком, увівши системи комбінаторних функцій H і ' H , де Hwjf mk 1|),)(( – комбінаторна функція, аргументом якої є перестановка Ww k , утворена з елементів базової множини },...,{ 1 nn aaA , ' 1 ' |),)(( Hwjf mi – комбінаторна функція, аргументом якої є перестановка '' Ww i , утворена з елементів базової множини }~,...,~{ ~ 1 mm aaA . Якщо mm wjfwjf 1 1' 1 1 |),)((|),)(( , де 1'1 , ww – перші перестановки в W , ' W і Hwjf m 1 1 |),)(( , ' 1 1' |),)(( Hwjf m , то ' HH . Задачу комбінаторної Тимофієва Н.К. Індуктивне моделювання складних систем, випуск 8, 2016 188 оптимізації, вхідні дані в якій задано функціями mk wjf 1|),)(( та m j 1|)( , назвемо базовою (або задачею системи H ). Задачу, вхідні дані в якій задано функціями mt wjf 1 ' |),)((  ), де ),)1((),)(( '' tt wjfwjf  , та m j 1|)(  , де )1()( jj  , утворених із mk wjf 1|),)(( та m j 1|)( , назвемо упорядкова- ною (або задачею системи ' H ). Зв’язок між базовою та упорядкованою задачами сформулюємо у вигляді таких теорем. Теорема 1 [9]. Якщо вхідні дані в задачі системи ' H задано комбінаторною та числовою функціями Rjjfj )(),,)(( 1' , причому )1()( jj , ),)1((),)(( 1' 1 1' wjfwjf jj , то найбільшого значення цільова функція (1) набуває для перестановки )1,...,( 1' mw , а найменшого – для )1,...,( ' mw k . Теорема 2 [9]. Значення цільової функції для задач комбінаторної оптимізації, аргументом якої є перестановка, знаходиться в межах: )(min)()(max '' '''' t Ww ki Ww wFwFwF ti , }!,..,1{ nk , ti , }!,..,1{, mti , Ww k , ''' , Www ti . У разі мінімізації значення цільової функції знаходиться в межах *' )()(min '' FwFwF kt Ww t . У разі максимізації – в межах )(max)( '* '' i Ww k wFwFF i , де )(min)(max )(min '' '* '''' '' t Ww i Wwt Ww wFwF wFF ti t , – коефіцієнт зменшення області пошуку оптимального значення, який уточнюється в процесі розв'язання певної задачі. Методом структурно-алфавітного пошуку за розробленими правилами за функціями mt wjf 1 ' |),)((  та m j 1|)(  знаходимо послідовність локальних оптимумів ))(),...,(( *1 k wFwFF таких, що )()( * k Ww k wFextrglobwF k , де max}{min,extr , Www kk * , – перестановки, }!...,1{, * nkk . 4. Подібність задач комбінаторної оптимізації, цільова функція в яких визначена на множині перестановок. До загальної математичної постановки задачі комбінаторної оптимізації, аргументом цільової функції в якій є перестановка, зводяться задача комівояжера, задача про призначення, задача розміщення одногабаритних Про універсальність методу структурно-алфавітного пошуку Індуктивне моделювання складних систем, випуск 8, 2016 189 об’єктів на поверхні та ін. Цільова функція для них моделюється виразом (1), за яким проводиться оцінка результату. Завдяки цій властивості задачі комбінаторної оптимізації, аргументом цільової функції в яких є перестановка і на підмножині ізоморфних комбінаторних конфігурацій (задача кластеризації) розв’язуються універсальними методами, зокрема методом структурно- алфавітного пошуку, за однією і тією ж схемою. В задачі кластеризації на дея- ких ізоморфних підмножинах цільова функція змінюється так як і в задачі комівояжера. Розглянемо задачу комівояжера, задачу про призначення та задачу роз- міщення одногабаритних модулів. Задача розміщення одногабаритних об’єктів задається на двох множи- нах: },...,{ 1 naaA , елементи la відповідають модулям, які необхідно розміс- тити на заданій поверхні, та },...,{ ~1 nbbB , кожен елемент sb якого визначає по- садочне місце для розміщення Aal , nn ~ . Покладемо, що nn ~ . Зв'язки існують між елементами Aaa lr , , кількісне значення яких задамо симетричною матрицею C (відповідно функцією m j 1|)( ), та між елементами Bbb ts , , зна- чення яких опишемо комбінаторною симетричною матрицею транспозиції )( k wQ (або функцією mk wjf 1|),)(( ). В результаті, значення цільової функції зводиться до виразу (1), а її аргумент – перестановка. Задача про призначення задається на двох множинах: },...,{ 1 naaA , де Aa j відповідає j -му претенденту, та },...,{ 1 nbbB , де Bbl відповідає l -й посаді. Між елементами Aa j та Bbl визначено зв'язки. Задамо їх несимет- ричною матрицею транспозиції )( k wQ (функцією mk wjf 1|),)(( ). Для визна- чення належності ja -го претендента на lb -ту посаду для k w -го варіанту розв'язку задачі уведемо несиметричну (0,1)-матрицю C (функція m j 1|)( ). Звідси випливає, що цільова функція зводиться до виразу (1), а її аргумент – пе- рестановка. Задача комівояжера задається на одній множині, яку позначимо },...,{ 1 naaA , де елемент ja відповідає j -му місту. Зв'язки між Aaa lj , задамо симетричною матрицею транспозиції )( k wQ (функція mk wjf 1|),)(( ). Уведемо симетричну (0,1)-матрицю C (функція m j 1|)( ), у якій елемент 1jlc , якщо елементи lj aa , для варіанту розв'язку задачі k w мають між со- бою зв'язки, та 0ljc в іншому випадку. Цільова функція в цій задачі задається Тимофієва Н.К. Індуктивне моделювання складних систем, випуск 8, 2016 190 виразом (1). Пошук оптимального розв'язку проводиться на множині переста- новок. Наведемо обчислювальну схему пошуку глобального мінімуму для задачі комівояжера, задачі про призначення та розміщення одногабаритних модулів. Глобальний максимум знаходиться аналогічно. 1. Задання вхідної інформації. 1.1. Якщо необхідно розв'язати задачу комівояжера, то вхідні дані зада- ються симетричною матрицею )( k wQ . Уведемо (0,1)-матрицю C . За описаними вище правилами утворюються скінченні послідовності (функція mk wjf 1|),)(( та функція m j 1|)( ). Перехід до п. 2. В іншому разі – перехід до п. 1.2. 1.2. Якщо необхідно розв'язати задачу розміщення одногабаритних об’єктів, вхідні дані задаються симетричною матрицею )( k wQ , та симетричною матрицею C . За описаними вище правилами утворюються скінченні послідов- ності (функція mk wjf 1|),)(( та функція m j 1|)( ). Перехід до п. 2. В іншому разі – перехід до п. 1.3. 1.3. Якщо необхідно розв'язати задача про призначення, вхідні дані зада- ються двома несиметричними матрицями )( k wQ , та матрицею C . За описаними вище правилами утворюються скінченні послідовності (функція mk wjf 1|),)(( та функція m j 1|)( ). Перехід до п. 2. В іншому разі – вважаємо, що вхідні дані не задано, переходимо до п. 10. 2. Базову задачу комбінаторної оптимізації зведемо до упорядкованої, за- давши в ній вхідні дані функціями mt wjf 1 ' |),)((  та m j 1|)(  . Перейдемо до п. 3. 3. Уведемо множини F , J , P , де F – множина значень локальних міні- мумів, P – множина побудованих перестановок, l -му елементу якої відповідає l -те значення локального мінімуму із F , J – множина номерів позицій значень комбінаторної функції, для яких знайдено локальний мінімум. Покладемо 1k , 1l . Величина k вказує на порядковий номер перестановки Ww k , що будується, а l – порядковий номер перестановки у множині P (відповідно зна- чення локального мінімуму у множині F та номера позицій значень комбінаторної функції у множині J ). Перехід до п. 4. 4. За функцією mt wjf 1 ' |),)((  за розробленими правилами будуємо пе- рестановку Ww k . Якщо Ww k не змінила порядок значень у Про універсальність методу структурно-алфавітного пошуку Індуктивне моделювання складних систем, випуск 8, 2016 191 mt wjf 1 ' |),)((  , у множину F заносимо знайдену за виразом (1) величину )( k wF , а в P – відповідно k l wP , переходимо до п. 6. В іншому разі покладаємо )( * k wFF , kk ww * . Перехід до п. 5. 5. Знайдемо поточний локальний мінімум. Покладаємо 1j , 1 ~ j , 1s , jjs , 0p . Величина j – номер позиції значення ),)(( 't wjf  , з якої продовжується побудова перестановки, sj – номер позиції значення комбінаторної функції, з якої починається будуватися чергова перестановка, j ~ – номер позиції значення комбінаторної функції, для якої знаходиться локаль- ний мінімум, p – коефіцієнт, який визначає перехід до пошуку чергового ло- кального мінімуму. Переходимо до п. 6. 6. Покладаємо 1kk . Побудова чергової перестановки проводиться за значеннями комбінаторної функції, починаючи з ),)(( 't r wjf  за правилами, описаними нижче у п. п. 6.1–6.3. Якщо 1l , то sr jj , в іншому разі rr Jj , JJ r , 1,1 lr . 6.1. Якщо розв’язується задача розміщення одногабаритних модулів, пе- рехід до п. 6.2. Якщо розв’язується задача комівояжера – перехід до п. 6.3. Як- що розв’язується задача про призначення, перехід до п. 6.4. 6.2. Для задачі розміщення визначаємо адресу yx, матриці )( k wQ , де знаходиться значення ),)(( 't wjf  . Величини yx, – елементи перестановки Ww k . Номери позицій цих елементів у перестановці визначаються номерами стовпця та рядка, де знаходиться значення )( j  , на яке перемножується зна- чення ),)(( 't wjf  . Переходимо до п. 6.5. 6.3. Для задачі комівояжера номери рядка і стовпця матриці )( k wQ , на перетині яких знаходиться ),)(( 't wjf  , є елементами перестановки. Перехо- димо до п. 6.5. 6.4. У задачі про призначення транспозиція проводиться або рядків або стовпців, тому x вважаємо елементом перестановки, а y – номером позиції елемента перестановки. Переходимо до п. 6.5. 6.5. Покладаємо 1jj . Якщо mj або перестановка уже побудована, переходимо до п. 7. В іншому разі – до п. 6.6. Тимофієва Н.К. Індуктивне моделювання складних систем, випуск 8, 2016 192 6.6. Якщо для значення ),)(( 't wjf  елементи перестановки k w уже визначено, переходимо до п. 6.5, в іншому разі – до п. 6.1. 7. Для одержаної перестановки k w знаходимо значення цільової функції )( k wF . Якщо * )( FwF k і 2 2 nk , переходимо до п. 6. Якщо * )( FwF k і 2 2 nk , покладаємо 1pp . Якщо p , переходимо до п. 8 ( – коефіцієнт, що визачає глибину пошуку оптимального розв'язку). В іншому разі покладаємо 1ss jj , переходимо до п. 6. Якщо * )( FwF k і 2 2 nk , покладаємо )( * k wFF , kk ww * , sjj ~ , 1ss jj , 1sjj , 0p , перехо- димо до п. 6. 8. Якщо досліджено околи знайдених локальних мінімумів, переходимо до п. 9. В іншому разі покладаємо *FFl , *k l wP , jJ l ~ , 1ll , 2sjj , )1( pjj ss , 1ss , 0p . Переходимо до п. 6. 9. За оптимальний розв'язок, який може збігатися з глобальним, приймаємо Ww k , для якої цільова функція із множини F набуває найменшо- го значення. 10. Кінець роботи алгоритму. Висновки. Отже, універсальність методів та алгоритмів визначається подібністю задач комбінаторної оптимізації. Для її встановлення при моделюванні прикладних задач необхідно виявити спільні для них ознаки. Це дозволяє розв’язувати задачі різних класів одним і тим же методом або модифікацією одного і того ж алгоритму. Так, методом структурно-алфавітного пошуку за однією і тією ж обчислювальною схемою розв’язуються задача комівояжера, задача про призначення та задача розміщення одногабаритних об’єктів. Вони подібні за аргументом цільової функції, яким є для них перестановка. Виявлення ознак, за якими встановлюється подібність задач комбінаторної оптимізації різних класів дозволить значну їхню частину звести до невеликого числа стандартних схем, можливо канонічних форм. Це дасть змогу розробляти адекватні математичні моделі та вибирати або розробляти для їхнього розв'язання ефективні універсальні методи та алгоритми. Про універсальність методу структурно-алфавітного пошуку Індуктивне моделювання складних систем, випуск 8, 2016 193 Література 1. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Пер. с англ. / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М.: Мир, 1980. – 476 с. 2. Липский В. Комбинаторика для программистов / Пер. с польск. / В. Липский – М.: Мир, 1988.– 213 с. 3. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Пер. с англ. / Х. Пападимитриу, К. Стайглиц. – М.: Мир, 1985.– 510 с. 4. Сергиенко И.В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации / И.В. Сергиенко, М.Ф. Каспшицкая. – К.: Наук. думка, 1981.– 281 с. 5. Беллман Р. Динамическое программирование / Пер. с англ. / Р. Беллман –М.: Изд-во иностранной литературы, 1960. – 400 с. 6. Тимофієва Н.К. Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. – 2013. – № 4. – С. 27–37. 7. Тимофієва Н.К. Теоретико-числові методи розв'язання задач комбінаторної оптимізації. Автореф. дис... докт. техн. наук / – Ін-т кібернетики ім. В.М. Глушкова НАН України, Київ. – 2007. – 32 с. 8. Харди Г.Г. Неравенства / Пер. с англ. / Г.Г. Харди, Дж.Е. Литтль- вуд, Г. Полиа. – М.: Гос. из-во иностр. лит., 1948. – 456 с. 9. Тимофеева Н.К. Определение множества значений целевой функ- ции в задачах дискретной оптимизации // Кибернетика и вычислительная техника. Сложные системы управления: Сб. науч. тр. – К., 1998 .– Вып. 120. – С. 37–43.

Ähnliche Einträge