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

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

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

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

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

Показано, что задача планирования из теории расписаний разделяется на две подзадачи, а целевая функция зависит от двух переменных, которыми являются комбинаторные конфигурации разных типов. Поиск результата проводится на двух комбинаторных множествах. Подзадачи решаются методом структурно-алфавитного поиска, а основная задача - гибридным алгоритмом, в котором встроенные процедуры, реализованные на основе этого метода, работают в итерационном режиме.

Індекс рубрикатора НБУВ: Р343 с

Рубрики:

Клінічні методи дослідження

Шифр НБУВ: Ж14024 Пошук видання у каталогах НБУВ 

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

З використанням теорії комбінаторної оптимізації сформульовано математичні постановки таких прикладних задач георозподілених динамічних систем, як розподілення сервісних об'єктів на певній території, та задача збереження довкілля. Для них змодельовано цільову функцію та визначено її аргумент. Із розглянутих класів задач виділено підкласи, які розв'язуються за допомогою методу структурно-алфавітного пошуку.

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

Показано, що цільова функція в задачах комбінаторної оптимізації може залежати як від однієї так і від кількох змінних, якими є комбінаторні конфігурації різних типів. Задачі, цільова функція в яких залежить від багатьох змінних, розбиваються на підзадачі та потребують для свого розв'язання розроблення комбінованих (гібридних) алгоритмів.

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

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

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

Описан метод структурно-алфавитного поиска решения задач комбинаторной оптимизации, который основан на распознавании структуры входной информации и одном разрешимом случае, характеризуется большим быстродействием и точностью нахождения оптимального результата. Также показано, что некоторые нерешаемые задачи этого класса сводятся к полиномиально решением или содержат подклассы решаемых задач.

A structure-alphabetical search method of decision of problems of сombinatorial optimization, based on recognition of a structure of input data and one solvable case, characterized by high speed and accuracy of finding the optimal result is described.It is also shown that some the unsolvable problems of this class are taken to polynomial solvable or contain the subclass of solvable problems.

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

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

З використанням комбінаторного аналізу побудовано математичну модель об'ємного координатного комутатора, у якого за рахунок багатошарового виконання зменшено кількість елементів комутації на його поверхні. Грунтуючись на деяких властивостях перестановок, визначено коефіцієнти зменшення цього комутатора, з урахуванням яких оптимізований варіант його конструкції залишається неблокувальним.

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

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

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