Про подібність задач комбінаторної оптимізації та універсальність алгоритмів

Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Тимофієва, Н.К.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2013
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Методи оптимізації, оптимальне управління і теорія ігор
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/85132
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 27-37. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85132
record_format	dspace
spelling	irk-123456789-851322015-07-20T03:02:37Z Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Тимофієва, Н.К. Методи оптимізації, оптимальне управління і теорія ігор Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці — за способом утворення та упорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією. Показано, що деякі задачі комбінаторної оптимізації, що відносяться до різних класів, розділяються на подібні підзадачі, які розв’язуються за однією обчислювальною схемою. Властивість подібності, яка характерна для задач цього класу, визначає їхню універсальність, завдяки якій вони розв’язуються за одним і тим же методом. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити нерозв’язні задачі до розв’язних. Рассмотрено свойство подобия, которое имеет место в комбинаторике и комбинаторной оптимизации. Выявлены различные признаки, по которым оно определяется для задач, относящихся к разным классам. Описаны задачи комбинаторной оптимизации, которые подобны по аргументу целевой функции, а в комбинаторике — по способу образования и упорядочения комбинаторных конфигураций. Благодаря этому свойству их множества генерируются одним и тем же алгоритмом или его модификацией. Показано, что некоторые задачи комбинаторной оптимизации, относящиеся к разным классам, разделяются на подобные подзадачи, решаемые по одной вычислительной схеме. Свойство подобия, которое характерно для задач этого класса, определяет их универсальность, благодаря которой они решаются одним и тем же методом. Изучение и использование этого свойства в комбинаторной оптимизации в дальнейшем позволит сводить неразрешимые задачи к разрешимым. A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of objective function, and in combinatorics – by the method of formation and ordering of combinatorial configurations, are described. Due to this property their sets are generated by the same algorithm or its modification. It is shown that some combinatorial optimization problems, which belong to different classes are divided into similar subproblems that are solved by the same calculable scheme. The property of similarity, which is typical for this class of problems, determines their universality by which they are solved by the same method. A study and use of this property in the combinatorial optimization in the future will reduce the insoluble problems to the solvables. 2013 Article Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 27-37. — Бібліогр.: 11 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/85132 519.816 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор
spellingShingle	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор Тимофієва, Н.К. Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Системні дослідження та інформаційні технології
description	Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці — за способом утворення та упорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією. Показано, що деякі задачі комбінаторної оптимізації, що відносяться до різних класів, розділяються на подібні підзадачі, які розв’язуються за однією обчислювальною схемою. Властивість подібності, яка характерна для задач цього класу, визначає їхню універсальність, завдяки якій вони розв’язуються за одним і тим же методом. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити нерозв’язні задачі до розв’язних.
format	Article
author	Тимофієва, Н.К.
author_facet	Тимофієва, Н.К.
author_sort	Тимофієва, Н.К.
title	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів
title_short	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів
title_full	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів
title_fullStr	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів
title_full_unstemmed	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів
title_sort	про подібність задач комбінаторної оптимізації та універсальність алгоритмів
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2013
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	http://dspace.nbuv.gov.ua/handle/123456789/85132
citation_txt	Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 27-37. — Бібліогр.: 11 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT timofíêvank propodíbnístʹzadačkombínatornoíoptimízacíítauníversalʹnístʹalgoritmív
first_indexed	2025-07-06T12:17:30Z
last_indexed	2025-07-06T12:17:30Z
_version_	1836899893838348288
fulltext	© Н.К. Тимофієва, 2013 Системні дослідження та інформаційні технології, 2013, № 4 27 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.816 ПРО ПОДІБНІСТЬ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ТА УНІВЕРСАЛЬНІСТЬ АЛГОРИТМІВ Н.К. ТИМОФІЄВА Розглянуто властивість подібності, яка має місце в комбінаториці та комбіна- торній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оп- тимізації, які подібні за аргументом цільової функції, а в комбінаториці — за способом утворення та упорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією. Показано, що деякі задачі комбінаторної оптимізації, що відносяться до різних класів, розділяються на подібні підзадачі, які розв’язуються за однією обчислювальною схемою. Властивість подібності, яка характерна для задач цього класу, визначає їхню універсальність, завдяки якій вони розв’язуються за одним і тим же методом. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити не- розв’язні задачі до розв’язних. ВСТУП У комбінаторній оптимізації можна навести багато прикладів, коли задачі з різних класів розв’язуються за однією і тією ж обчислювальною схемою, наприклад [1–6]. Цю властивість у літературі належним чином не висвітле- но, хоча існуючі універсальні методи орієнтовані на розв’язання різноманіт- них таких задач. Системний аналіз задач комбінаторної оптимізації з вико- ристанням цієї теорії показує, що деякі з них, які відносяться до різних класів, розділяються на підзадачі, що розв’язуються за однією обчислюваль- ною схемою або модифікацією одного й того ж алгоритму. Тобто, універ- сальність закладено саме в їхній природі. Цим можна пояснити, чому вони розв’язуються відомими універсальними методами. Це стосується і гене- рування комбінаторних множин, серед яких можна виділити такі, що гене- руються одним і тим же алгоритмом або його модифікацією. Тому однією з проблем цього наукового напряму є виявлення властивості універсальності задач комбінаторної оптимізації різних класів з метою узагальнення та ви- користання для їхнього розв’язання ефективних підходів, які дають можли- вість знаходити глобальний або наближений до глобального результат. Розглянемо цю властивість на прикладі деяких задач із комбінаторики та комбінаторної оптимізації. Н.К. Тимофієва ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 28 Мета роботи — Виявлення різноманітних ознак, за якими визначається подібність задач комбінаторної оптимізації різних класів, що дозволяє уза- гальнювати та використовувати для їхнього розв’язання ефективні методи та алгоритми. ПОДІБНІСТЬ ГЕНЕРУВАННЯ КОМБІНАТОРНИХ МНОЖИН Аргументом цільової функції в задачах комбінаторної оптимізації є комбі- наторні конфігурації (перестановки, сполучення, розбиття n -елементної множини на підмножини тощо). В таких задачах як задача комівояжера, роз- міщення об’єктів, задача про призначення аргументом цільової функції є перестановка. В задачі про рюкзак або задачах, які вимагають побудови блок-схем, пошук оптимального розв’язку проводиться на множині сполу- чень. Задачі про передачу сигналів, які мають місце в теорії інформатики, оптимальне розподілення оперативної пам’яті під час організації обчислю- вального процесу, вимагають знання властивостей розбиття числа. Аргумен- том цільової функції задач із теорії розкладів або задач, пов’язаних із вико- нанням кінцевих або проміжних комплексів операцій, виступають вибірки різних типів. Великий клас задач розбиття має місце у найрізноманітніших постановках: розбиття множини, розрізування графів, мереж, кластеризація, таксономія, класифікація. Вони полягають в упорядкуванні заданих об’єктів у порівнянно однорідні групи, тобто за розробленими правилами прово- диться пошук оптимального розбиття n -елементної множини на підмножи- ни. В задачах, що вимагають знаходження оптимальної укладки електрич- них схем на одній або кількох поверхнях, аргументом цільової функції виступає граф. Під комбінаторною конфігурацією розуміємо будь-яку сукупність еле- ментів, яка утворюється з усіх або з деяких елементів заданої базової множини },...,{ 1 naaA = . Позначимо її упорядкованою множиною ),...,( 1 kkk www η= , де },...,1{ n∈η — кількість елементів у kw (в подальшому η позначатимемо і як kη ), qkwW 1}{= — множина комбінаторних конфігу- рацій. Верхній індекс k ( }),...,1{ qk ∈ у kw позначає порядковий номер kw у ,W q — кількість kw у .W Рекурентним комбінаторним оператором назвемо сукупність правил, за допомогою яких з елементів базової множини A утворюється комбінаторна конфігурація kw . Різноманітні типи комбінаторних конфігурацій утворю- ються за допомогою трьох рекурентних комбінаторних операторів: виби- рання, транспозиція, арифметичний [7]. Означення 1. Дві нетотожні комбінаторні конфігурації ),...,( 1 kkk kwww η = та ),...,( 1 iii iwww η = назвемо ізоморфними, якщо .ik ηη = Означення 2. Підмножину WW k ⊂η назвемо підмножиною ізоморф- них комбінаторних конфігурацій, якщо її елементи — ізоморфні комбінатор- ні конфігурації. Розглянемо комбінаторні конфігурації, множину W яких утворено кіль- кома рекурентними комбінаторними операторами. В цьому випадку одним Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Системні дослідження та інформаційні технології, 2013, № 4 29 із операторів виступає або операція вибирання або арифметична. Вони утворюють як ізоморфні так і неізоморфні комбінаторні конфігурації. Тому множина ,W елементи якої утворено кількома рекурентними комбінаторни- ми операторами, складається з підмножин ізоморфних комбінаторних кон- фігурацій. Оскільки операція транспозиції змінює лише порядок слідування еле- ментів у ,Wwk∈ то множина перестановок W є множиною ізоморфних комбінаторних конфігурацій. У множині ,W елементи якої утворено кількома рекурентними комбі- наторними операторами, виділимо підмножину ,* WW ⊂ будь-який елемент якої утворюється одним типом оператора, і підмножини ,** WW ⊂ комбіна- торні конфігурації яких утворено іншим типом [7]. Назвемо WW ⊂* базо- вою підмножиною множини .W Означення 3. Назвемо подібними задачі з комбінаторики або задачі комбінаторної оптимізації різних класів, які розв’язуються за однією й тією ж обчислювальною схемою або модифікацією одного й того ж алгоритму. Лема 1. Комбінаторні конфігурації подібні, якщо вони утворюються одним і тим же рекурентним комбінаторним оператором, а їхні множини генеруються модифікацією одного й того ж алгоритму. Доведення. Для доведення цього твердження розглянемо утворення комбінаторних конфігурацій. За способом утворення вони розділяються на прості (утворюються одним і лише одним типом рекурентних комбінатор- них операторів) і комбіновані (утворюються кількома рекурентними комбі- наторними операторами) [7]. До простих комбінаторних конфігурацій відне- семо перестановки, розбиття числа, сполучення та бінарні послідовності. До комбінованих віднесемо розбиття множини на підмножини, розміщення з по- втореннями і без повторень. Сполучення як з повтореннями так і без повторення утворюються єди- ною операцією — вибиранням. Перестановки утворюються транспозицією або вибиранням. Розбиття числа утворюються однією операцією — арифме- тичною. Розбиття n -елементної множини на підмножини утворюються двома рекурентними комбінаторними операторами — арифметичним або транспозицією. Розміщення як з повтореннями так і без повторення утво- рюються двома операціями: вибиранням або транспозицією. Бінарні послі- довності можуть утворюватися двома операціями — арифметичною або операцією вибирання. До того ж, кількість бінарних послідовностей у їхній множині дорівнює ,2n а кількість сполучень без повторення — відповідно .12 −n Виходячи з цього, генерування розбиття n -елементної множини на підмножини проводиться алгоритмом розбиття числа і генеруванням пере- становок. Упорядкування розміщення без повторення та з повтореннями проводиться алгоритмами генерування сполучень і перестановок. Форму- вання бінарних послідовностей з використанням рекурентного комбінатор- ного оператора вибирання проводиться за тими ж правилами, що і утворен- ня сполучень без повтореннями. Н.К. Тимофієва ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 30 Таким чином, за способом утворення подібні такі комбінаторні кон- фігурації: бінарні послідовності та сполучення без повторення; розбиття n -елементної множини на підмножини і розбиття натурального числа та перестановки; розміщення без повторення (з повтореннями) і сполучення без повторень (з повтореннями) та перестановки. Ці множини подібні за способом генерування, оскільки вони упорядковуються одним і тим же ал- горитмом або його модифікацією (бінарні послідовності й сполучення без повторень генеруються модифікацією одного і того ж алгоритму, базова під- множина WW ⊂* розбиття n -елементної множини на підмножини і розбит- тя натурального числа генеруються одним і тим же алгоритмом). Тобто, на- ведені вище комбінаторні конфігурації подібні за способом їхнього утворення і упорядкування, що і доводить лему 1. ПОДІБНІСТЬ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ, ЦІЛЬОВУ ФУНКЦІЮ ЯКИХ ВИЗНАЧЕНО НА МНОЖИНІ ПЕРЕСТАНОВОК Сформулюємо загальну математичну постановку задачі комбінаторної оп- тимізації. Нехай задано одну A або кілька множин, наприклад A та B [8]. Вагою назвемо величину, яка визначає залежність, що існує між елементами Aas ∈ та Bbl ∈ або між елементами однієї і тієї ж множини — },,...,1{ ns ∈ },~,...,1{ nl ∈ n — кількість елементів множини ,A n~ — кількість елемен- тів множини .B Покладемо, що .~nn= Значення ваг між елементами мно- жин A та B задамо однією або двома симетричними або несиметричними матрицями C та ),( kwQ де )( kwQ — комбінаторна матриця, Wwk∈ — перестановка. Якщо значення ваг описуються однією матрицею ,C то для визначення наявності зв’язків між елементами заданих множин для k -го варіанту розв’язку задачі уведемо симетричну або несиметричну )1,0( -матрицю ).( kwQ Елемент ,1)( =k ls wg якщо між Aas∈ та Bbl ∈ або Aas∈ та Aal∈ для варіанту kw існує зв’язок, та 0)( =k ls wg в іншому разі; .)()( kk ls wQwg ∈ Подамо елементи h наддіагоналей симетричної комбінаторної мат- риці )( kwQ комбінаторною функцією ...,),)1(((\|),)(( 11 kmk wfwjf ββ = )),)((,... k m wmfβ , а елементи h наддіагоналей симетричної матриці C — функцією натурального аргументу )),(...,),1(()( 1 mj m ϕϕϕ = де =m 2 )1( − = nn — кількість елементів h наддіагоналей матриць C та )( kwQ , 1,1 −= nh . Якщо матриці )( kwQ та C — несиметричні, то mkwjf 1 )),((β та mj 1)(ϕ містять усі їхні елементи, а 2nm= (або nnm ~= ). Функція цілі )( kwF для цих задач набуває вигляду Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Системні дослідження та інформаційні технології, 2013, № 4 31 ).(),)(()( 1 jwjfwF k m j j k ϕβ∑ = = (1) До загальної математичної постановки задачі комбінаторної оптиміза- ції, аргументом цільової функції в якій є перестановка, зводяться задача ко- мівояжера, задача про призначення, задача розміщення одногабаритних об’єктів на поверхні тощо. Цільова функція для них моделюється виразом (1), за яким проводиться оцінка результату. Завдяки цьому задачі комбіна- торної оптимізації, аргументом цільової функції в яких є перестановка і на підмножині ізоморфних комбінаторних конфігурацій (задача кластеризації) розв’язуються універсальними методами, зокрема методом структурно- алфавітного пошуку за однією і тією ж схемою. В задачі кластеризації на деяких ізоморфних підмножинах цільова функція змінюється так як і в зада- чі комівояжера. Опишемо метод структурно-алфавітного пошуку, який ґрунтується на розпізнаванні вхідної інформації та певному впорядкуванні комбінаторних конфігурацій [8]. У ньому використано відомий розв’язний випадок, який задано двома системами перестановок )(a та )(b , на яких уведено цільову функцію ∑ab [9]. Для цих систем визначено перестановки, для яких ∑ab набуває найбільшого або найменшого значень. Якщо елементи перестанов- ки із системи )(a впорядковані від більшого елемента до меншого, а із )(b — від меншого елемента до більшого, то значення ∑ab є глобальним мінімумом. Якщо елементи обох таких перестановок упорядковані від мен- шого елемента до більшого, то значення ∑ab є глобальним максимумом. Цей розв’язний випадок не належить жодному класу із класів задач комбі- наторної оптимізації. З метою використання оговореного розв’язного випадку для розв’язан- ня задач комбінаторної оптимізації методом структурно-алфавітного пошу- ку встановимо зв’язок між прикладними задачами і оговореним вище розв’язним випадком, увівши системи комбінаторних функцій H та ,H ′ де Hwjf mk ∈ 1 )),((β — комбінаторна функція, аргументом якої є перестанов- ка ,Wwk ∈ утворена з елементів базової множини };,...,{ 1 nn aaA = Hwjf mi ′∈′ 1 )),((β — комбінаторна функція, аргументом якої є перестанов- ка ,Ww i ′∈′ утворена з елементів базової множини }.~,...,~{~ 1 mm aaA = Якщо mm wjfwjf 1 1 1 1 )),(()),(( ′= ββ , де 1'1, ww — перші перестановки в ,W W ′ та ,)),(( 1 Hwjf mi ∈β ,)),(( 1 Hwjf mi ′∈′β то .HH ′⊂ Задачу комбінаторної оптимізації, вхідні дані в якій задано функціями mkwjf 1 )),((β та mj 1)(ϕ , назвемо базовою (або задачею системи ).H Задачу, вхідні дані в якій задано Н.К. Тимофієва ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 32 функціями mtwjf 1 )),(( ′β r , де )),1(()),(( tt wjfwjf ′+≤′ ββ rr , та ,)( 1 mjϕ s де ,)1()( +≥ jj ϕϕ ss утворених із mkwjf 1 )),((β та ,)( 1 mjϕ назвемо упорядкова- ною (або задачею системи H ′ ). Зв’язок між базовою та упорядкованою задачами сформулюємо у вигля- ді таких теорем. Теорема 1 [10]. Якщо вхідні дані в задачі системи H ′ задано комбі- наторною і числовою функціями ),),(( 1ωβ ′jfj ,)( Rj ∈ϕ причому ),1()( +≤ jj ϕϕ ),),1(()),(( 1 1 1 wjfwjf jj ′+≤′ +ββ то найбільшого значення цільова функція (1) набуває для перестановки ,),...,1(1 mw =′ а найменшо- го — для ).1,...,(mw k =′ Теорема 2 [10]. Значення цільової функції для задач комбінаторної оп- тимізації, аргументом якої є перестановка, знаходиться в межах: ),(min)()(max t Ww kt Ww wFwFwF tt ′≥≥′ ′∈′′∈′ }!,...,1{ nk ∈ , ti ≠ , },!,...,1{, mti ∈ ,Wwk∈ ., Www ti ′∈′′ У разі мінімізації значення цільової функції знаходиться в межах .)()(min FwFwF kt Ww t <≤′ ′∈′ У разі максимізації — в межах ≤< )( kwFF )(max i Ww wF t ′≤ ′∈′ , де υ )(min)(max )(min ''* t Ww i Wwt Ww wFwF wFF ti t ′−′ +′= ′∈′∈ ′∈′ , υ — коефіцієнт зменшення області пошуку оптимального значення, який уточ- нюється в процесі розв’язання певної задачі. Методом структурно-алфавітного пошуку за розробленими правилами за функціями mtwjf 1\|)),(( ′β r та mj 1\|)(ϕ s знаходимо послідовність локальних оптимумів ))(,...),(( 1 kwFwFF = таких, що ),(extrglob)( k Ww k wFwF k∈ = де max},{min,extr = Www kk ∈, — перестановки, }.!,...,1{, nkk ∈ Наведемо обчислювальну схему пошуку глобального мінімуму для за- дач, аргументом цільової функції яких є перестановка. Глобальний макси- мум знаходиться аналогічно. 1. Базову задачу комбінаторної оптимізації зведемо до упорядкованої, задавши в ній вхідні дані функціями mtwjf 1\|)),(( ′β r та mj 1\|)(ϕ s . Перейде- мо до п. 2. 2. Уведемо множини ,F ,J ,P де F — множина значень локальних мінімумів, P — множина побудованих перестановок, l -му елементу якої відповідає l -те значення локального мінімуму із ,F J — множина номерів позицій значень комбінаторної функції, для яких знайдено локальний міні- мум. Покладемо ,1=k 1=l . Величина k вказує на порядковий номер пере- становки ,Wwk ∈ що будується, а l — порядковий номер перестановки Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Системні дослідження та інформаційні технології, 2013, № 4 33 у множині P (відповідно значення локального мінімуму у множині F та номера позицій значень комбінаторної функції у множині .)J За функцією mtwjf 1 ' \|),)((β r за розробленими правилами будуємо пе- рестановку .Wwk ∈ Якщо Wwk ∈ не змінила порядок значень у ,\|),)(( 1 ' mtwjfβ r у множину F заносимо знайдену за виразом (1) величи- ну )( kwF , а в P — відповідно ,k l wP = переходимо до п. 6. В іншому разі покладаємо )(* kwFF = , .* kk ww = Знайдемо поточний локальний мінімум. Покладаємо ,1=j ,1~ =j ,1=s ,jjs = .0=p Величина j — номер позиції значення ),,)(( 'twjfβ r з якої продовжується побудова перестановки, sj — номер позиції значення комбі- наторної функції, з якої починається будуватися чергова перестановка, j~ — номер позиції значення комбінаторної функції, для якої знаходиться ло- кальний мінімум, p — коефіцієнт, який визначає перехід до пошуку черго- вого локального мінімуму. Переходимо до п. 3. 3. Покладаємо .1+= kk Побудова чергової перестановки проводиться за значеннями комбінаторної функції, починаючи з ),)(( t r wjf ′β r за прави- лами, описаними у п.п. 3.1–3.3. Якщо ,1=l то sr jj = , в іншому разі ,rr Jj = ,JJr ∈ .1,1 −= lr Переходимо до п. 3.1. 3.1. Для задачі розміщення визначаємо адресу матриці ,, yx де знахо- диться .),)(( 'twjfβ r Величини yx, — елементи перестановки .Wwk ∈ Номери позицій цих елементів у перестановці визначаються номерами стовпця і рядка, де знаходиться значення )( jϕ s , на яке перемножується зна- чення ).,)(( 'twjfβ r Для задачі комівояжера номери рядка і стовпця матриці, на перетині яких знаходиться ),,)(( 'twjfβ r є елементами перестановки. У задачі про призначення транспозиція проводиться або рядків або стовпців, тому x вважаємо елементом перестановки, а y — номером позиції елемен- та перестановки. Переходимо до п. 3.2. 3.2. Покладаємо 1+= jj . Якщо mj > або перестановку вже побудова- но, переходимо до п. 4. В іншому разі — до п. 3.3. 3.3. Якщо для значення ),)(( 'twjfβ r елементи перестановки kw уже визначено, переходимо до п. 3.2, в іншому разі — до п. 3.1. 4. Для одержаної перестановки kw знаходимо значення цільової функ- ції )( kwF . Якщо )( FwF k ≥ та 22nk > , переходимо до п. 6. Якщо )( FwF k ≥ та ,22nk ≤ покладаємо .1+= pp Якщо ,ϖ>p переходимо до п. 5 (ϖ — коефіцієнт, що визначає глибину пошуку оптимального розв’язку). В іншому разі покладаємо ,1+= ss jj переходимо до п. 3. Якщо )( FwF k < та ,22nk ≤ покладаємо ),( kwFF = ,* kk ww = ,~ sjj = ,1+= ss jj ,1+= sjj ,0=p переходимо до п. 3. Н.К. Тимофієва ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 34 5. Якщо досліджено околи знайдених локальних мінімумів, переходи- мо до п. 6. В іншому разі покладаємо ,FFl = ,k l wP = ,~jJ l = ,1+= ll ,2+= sjj ,)1( −−= pjj ss ,1+= ss .0=p Переходимо до п. 3. 6. За оптимальний розв’язок, який може збігатися з глобальним, приймаємо ,Wwk ∈ для якої цільова функція із множини F набуває най- меншого значення. 7. Кінець роботи алгоритму. Сформулюємо наступну лему. Лема 2. Задачі комбінаторної оптимізації подібні за способом їхнього розв’язання, якщо аргументом цільової функції в них є перестановка. Доведення. Подібність задач комбінаторної оптимізації, в яких аргу- мент цільової функції є перестановка, випливає з того, що цільова функція в них зводиться до одного виразу (1), вхідні дані моделюються функціями натурального аргументу, а методом структурно-алфавітного пошуку за цими функціями за однією і тією ж схемою знаходиться оптимальний розв’язок для задач різних класів, тобто вони подібні, що і доводить лему 2. ПОДІБНІСТЬ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ, У ЯКИХ ЦІЛЬОВА ФУНКЦІЯ ЗАЛЕЖИТЬ ВІД КІЛЬКОХ ЗМІННИХ Прикладні задачі складні за своєю природою і основна задача, як правило, розділяється на підзадачі, а цільова функція, за якою оцінюється оптималь- ний розв’язок, залежить від кількох змінних, якими є комбінаторні конфігу- рації різних типів. Якщо побудувати математичні постановки задач роз- пізнавання мовленнєвих сигналів та клінічної діагностики з використанням теорії комбінаторної оптимізації, то можна побачити, що вони розділяються на три підзадачі: • структуризація бібліотеки еталонів; • пошук у бібліотеці еталонної інформації; • задача порівняння еталонної та вхідної інформації. Для обох класів задач аргументом цільової функції в першій підзадачі є розбиття n -елементної множини на підмножини, в другій підзадачі — розміщення без повторень, а в третій — сполучення без повторень. Розгля- немо ці задачі детальніше. Розпізнавання мовленнєвих сигналів полягає у знаходженні для вхідного сигналу найбільш правдоподібного еталонного з усіх можливих еталонних сигналів. Для розв’язання цієї задачі необхідно провести пошук певного еталону в бібліотеці і порівняти його із вхідним сигналом [11]. Розглянемо задачу порівняння еталонного та вхідного сигналів. Уведе- мо дві базові множини ),...,( 1 naaA = та ),,...,( ~1 i n ii bbB = де Aas ∈ — зна- чення сигналу у відліку ,s ,,1 ns = а ii l Bb ∈ відповідає відліку еталонного сигналу, },~,...,1{ nl∈ },,...,1{ qi∈ q — кількість еталонних сигналів. Вхід- ні дані, якими є ваги між елементами Aas ∈ та ,ii l Bb ∈ задамо несиметрич- Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Системні дослідження та інформаційні технології, 2013, № 4 35 ною матрицею nxnlscC ~= , номера стовпців якої збігаються з нумерацією елементів Aas ∈ , а номера рядків — з нумерацією елементів .ii l Bb ∈ Оскі- льки з кожної базової множини A та iB вибираються по одному елементу в строгому порядку, то отримана комбінаторна конфігурація є розміщення без повторення. Позначимо її ,Mk ∈μ де M — їхня всіляка множина. Для ви- значення елементів Aas ∈ та ,ii l Bb ∈ що вибираються з базових множин на k -му варіанті розв’язку задачі, уведемо комбінаторну )1,0( -матрицю .)()( ~nnx k sl k gQ μμ = Якщо ,1)( =k slg μ то з множин A та iB вибрана па- ра ),,( i ls ba в іншому разі значення .0)( =k slg μ Для запису цільової функції в явному вигляді змоделюємо вхідні дані функціями натурального аргумен- ту. Елементи матриці C подамо числовою функцією ,\|)( 1 mjϕ а матриці )( kQ μ — комбінаторною ,\|),)(( 1 mkjf μβ де .~nnm ⋅= Задача порівняння еталонного і вхідного мовленнєвих сигналів полягає у знаходженні такого розміщення без повторення ,kμ для якого =)( kF μ ,)),(()(max 1 ∑ =∈ = m j k j M jfj k μβϕ μ де ∑ = m j k j jfj 1 )),(()( μβϕ — інтегральна міра подібності, а ),()( i lsj bauj =ϕ — елементарна міра подібності, яка визначає подібність між елементами еталонного і вхідного сигналів. Розглянемо задачу пошуку в бібліотеці еталонного сигналу. В цій підзадачі як ваги між еталонним і вхідним сигналами виступають величини інтегральних мір подібності ),( kF μ числове значення яких по- дамо матрицею .'C Номера стовпців цієї матриці збігаються з номерами еталонних сигналів, розміщених у бібліотеці. Рядок у ній один і відповідає номеру один вхідного сигналу .A Оскільки при порівнянні вхідного і ета- лонного сигналів із множин A та B вибираються два елементи, то утворе- ний об’єкт є сполучення без повторення, який позначимо як ,Mk ′∈′μ де M ′ — їхня всіляка множина, ),...,( 1 i q i BBB = — множина еталонних сигна- лів. Уведемо комбінаторну )1,0( -матрицю .)()( 11 qx t l t gQ μμ ′=′ Якщо ,1)(1 =′tlg μ то з множин A та B вибрана пара ,),( i lBA в іншому разі — значення .0)(1 =′tlg μ Елементи матриці C′ подамо числовою функці- єю ,\|)( 1 1 −′ njϕ а матриці )( tQ μ′ — комбінаторною .\|),)(( 1 1 −′′′ ntjf μβ Задача пошуку еталонного сигналу, який відповідає вхідному, полягає у знаходженні такого сполучення без повторення ,tμ′ для якого ,)),(()(max)( 1 1 * ∑ − =∈′ ′′′′=′ n j t j M t jfjF t μβϕμ μ де ∑ = =′ m j k j jfjj 1 .)),(()()( μβϕϕ Н.К. Тимофієва ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 36 Задача клінічної діагностики. Побудуємо математичну модель задачі клінічної діагностики як задачу комбінаторної оптимізації. Позначимо )~,...,~{~ 1 n aaA = множину захворювань, описання яких знаходиться в бібліо- теці (множина еталонів), де елемент },,...,1{,~~ nsAas ∈∈ відповідає пев- ному захворюванню, якому поставлено у відповідність характерні ознаки ),...,,( )()( 2 )( 1 )( ' t q ttt t vvvV = , tq′ — кількість ознак t -го захворювання. Вхідною інформацією в задачі клінічної діагностики є множина ознак ,)~,...,~,~(~ ~21 qvvvV = що описує одне або кілька захворювань. Позначимо їх ,}~,...,~{~ 1 n bbB = де Bbd ~~ ∈ — захворювання, яке потрібно визначити, n — кількість можливих захворювань, а qqt ~≠′ або .~qqt =′ Ознаки Vvr ~~ ∈ вхід- ної інформації мають той же зміст, що і описані в еталоні ознаки ,)()( tt l Vv ∈ },~,...,1{ qr∈ },...,1{ tql ′∈ . Задача полягає у знаходженні для B~ із множиною ознак V~ найбільш правдоподібного одного або кількох еталонів із множини ),~,...,~{~ 1 naaA = тобто за вхідними ознаками встановлюється одне або кілька захворювань .~~ Bbd ∈ Ознаки в цій задачі відіграють роль критеріїв, за якими оцінюється її розв’язок. Як і в розпізнаванні мовленнєвих сигналів, для розв’язання цієї задачі необхідно провести пошук певного еталону в бібліотеці й порівняти його із вхідними ознаками. Розглянемо задачу порівняння ознак еталону ),,...,,( )()( 2 )( 1 )( t q ttt t vvvV ′= які визначають t -е захворювання, і вхідних ознак ),~,...,~,~(~ ~21 qvvvV = за якими необхідно встановити діагноз. Позначимо )~,( )( r t sl vvu′ елементарну міру подібності між елементами множин V~ та .)(tV Вважаємо, що міри подіб- ності між елементами )()( tt s Vv ∈ та Vvr ~~ ∈ є вхідні дані. Їхні числові значен- ня задамо скінченною послідовністю (комбінаторною функцією натурально- го аргументу, яка залежить від розміщення без повторення iμ ). Задача порівняння еталону і вхідних ознак полягає в знаходженні такого розміщен- ня без повторення ,),...,( *** 1 i q ii ′= μμμ для якого змодельовані цільові функ- ції набувають максимального значення. Розглянемо задачу перебору еталонів .)~,...,~{~ *1 n aaA = У цій задачі як ва- ги між елементами Aas ~~ ∈ та вхідними даними V~ виступають значення ін- тегральних мір подібності, одержаних за заданими цільовими функціями при порівнянні ознак еталону і вхідних ознак. Задача пошуку бібліотечного еталону, який відповідає вхідному, поля- гає у знаходженні такого сполучення без повторень, для якого значення часткових критеріїв, за якими оцінюється результат розв’язку, були б найбільшими. Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Системні дослідження та інформаційні технології, 2013, № 4 37 Таким чином, як задача клінічної діагностики так і розпізнавання мов- леннєвих сигналів розділяються на три підзадачі: структуризація бібліотеки еталонів; пошук у бібліотеці еталонної інформації; порівняння еталонної і вхідної інформації. Аргументом цільової функції в них є різні типи вибірок та розбиття n -елементної множини на підмножини. ВИСНОВКИ Задачі комбінаторної оптимізації різних класів, а також множини комбіна- торних конфігурацій подібні, якщо вони розв’язуються за однією і тією ж обчислювальною схемою або модифікацією одного і того ж алгоритму. По- дібність задач комбінаторної оптимізації встановлюється за аргументом цільової функції, а подібність комбінаторних множин — за способом їхньо- го утворення і упорядкування. Дослідження прикладних задач комбінатор- ної оптимізації на подібність дозволить значну їхню частину звести до неве- ликого числа стандартних схем, можливо канонічних форм. Це дасть змогу створювати адекватні математичні моделі прикладних задач різних класів та вибирати або розробляти для їхнього розв’язання ефективні універсальні методи та алгоритми. ЛІТЕРАТУРА 1. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: пер. с англ. — М.: Мир, 1980. — 476 с. 2. Липский В. Комбинаторика для программистов: пер. с польск. — М.: Мир, 1988. — 213 с. 3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: пер. с англ. — М.: Мир, 1985. — 510 с. 4. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комби- наторных задач оптимизации. — К.: Наук. думка, 1981. — 281 с. 5. Беллман Р. Динамическое программирование: пер. с англ. — М.: Изд-во ино- странной литературы, 1960. — 400 с. 6. Михалевич В.С. Последовательные алгоритмы оптимизации и их применение // Кибернетика. — 1965. — № 1. — С. 45–56; № 2. — С. 85–89. 7. Тимофеева Н.К. О способах образования аргумента целевой функции в задачах комбинаторной оптимизации // Кибернетика и системный анализ. — 2002. — № 6. — C. 96–103. 8. Тимофієва Н.К. Теоретико-числові методи розвязання задач комбінаторної оптимізації. Автореф. дис. докт. техн. наук / Ін-т кібернетики ім. В.М. Глушкова НАН України, Київ. — 2007. — 32 с. 9. Харди Г.Г., Литтльвуд Дж. Е., Полиа Г. Неравенства: пер. с англ. — М.: Гос. из-во иностр. лит., 1948. — 456 с. 10. Тимофеева Н.К. Определение множества значений целевой функции в задачах дискретной оптимизации // Кибернетика и вычислительная техника. Сложные системы управления: Сб. науч. тр. — К., 1998 . — Вып. 120. — С. 37–43. 11. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. — К.: Наукова думка, 1987. — 262 с. Надійшла 22.05.2012

Про подібність задач комбінаторної оптимізації та універсальність алгоритмів

Репозитарії

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