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

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

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

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

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

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

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

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

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

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

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

Запропоновано алгоритм розміщення для конструктивних вузлів електронної апаратури на базі точкового сканування зі зсувом елементів. Проведено експериментальні дослідження на тест-задачі Стейнберга.

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

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

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

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

Розглянуто декілька стратегій та алгоритмів послідовного пакування схем із заданими обмеженнями. Розкрито особливості різних стратегій пакування схем із заданими обмеженнями.

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

Запропоновано алгоритм виходу з локальних екстремумів у задачах розміщення елементів електронних схем. На базі тест-задачі Стейнберга досліджено ефективність стратегії почергової зміни метрик: евклідової та евклідової в квадраті.

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