Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва 2000


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Адаптивні алгоритми визначення екстремальних множин графів'

    Текст наукової роботи на тему «Адаптивні алгоритми визначення екстремальних множин графів»

    ?УДК 621.3.06

    В.А. Литвиненко

    АДАПТИВНІ АЛГОРИТМИ ВИЗНАЧЕННЯ ЕКСТРЕМАЛЬНИХ

    МНОЖИН гРАФІВ

    Завдання визначення екстремальних множин графів [1-3] досить часто використовуються в проектних процедурах САПР ЕВА як проектних операцій. Наприклад, завдання визначення максимальних внутрішньо стійких множин використовується при вирішенні задачі розміщення Штейнберга, в завданню трасування при розподілу фрагментів ланцюгів по магістралях в каналах металізації, при розподілі ланцюгів по верствам, і т.д. [3-5]. Разом з тим алгоритми визначення екстремальних множин графів є найбільш трудомісткими. Наприклад, завдання виділення всіх максимальних повних подграфов (етика) графа є ИР- ^ удной завданням [1,2].

    Під точністю рішення задач визначення екстремальних множин графів будемо розуміти кількість виділених екстремальних частин графа. Наприклад, для завдання виділення максимальних внутрішньо стійких множин точне рішення буде відповідати виділенню всіх максимальних внутрішньо стійких множин. В цьому випадку точність рішення буде складати 100%. Чим менше кількість виділених екстремальних частин графа, тим менше точність рішення.

    , -фов можна розділити на точні і наближені. Застосування точних алгоритмів обмежена їх комбінаторної складністю. Наближені алгоритми дозволяють отримувати рішення з обмеженою точністю, яка залежить від структури самого алгоритму Напри, -льон сімейств клік графа, що покривають всі вершини або ребра графа, що дозволяють отримувати наближені рішення з відносно низькою точністю [3,6,7].

    ,

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

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

    необхідна точність рішення, ресурс часу, відведений на рішення задачі, а також розмірність самого завдання.

    Використання програмних модулів адаптивних алгоритмів проектних опера () () на сруктурной схемою (рис.1). У загальному випадку будь-який пакет програм ьой проектної процедури може використовувати будь-який програмний модуль] юй проектної операції з бібліотеки адаптивних програмних модулів проектних операцій.

    -

    грам

    1

    ІМ ПОІ

    -

    грам

    ПШ

    ІМ ПО;

    -

    грам

    ППП

    ПМ Пош

    БІБЛІОТЕКА ПРОГРАМНИХ ​​МОДУЛІВ АЛГОРИТМІВ ПРОЕКТНИХ ОПЕРАЦІЙ

    рис.1.

    Структурна схема програмного модуля адаптивного алгоритму проектної операції показана на рис.2. Вхідні параметри надходять від пакета програм проектної. лічильник адаптації для настройки алгоритмів проектної операції з метою отримання необхідної точності рішення проектної процедури. У загальному випадку кожної мй проектної операції може відповідати кілька алгоритмів, які можуть отримувати рішення з різним ступенем точності. Тому блок адаптації призначений також для вибору відповідного алгоритму для виконання проектної операції. База даних містить результати досліджень ефективності алгоритмів проектної операції. З бази даних блок адаптації вибирає необхідні дані для визначення значень пара, .

    Вхідні Блок адаптації База

    параметри даних

    рис.2.

    І 87

    Як приклад розглянемо проектну операцію визначення клік графа. Кліки графа в проектних процедурах САПР ЕВА використовуються при вирішенні таких завдань, як задача розміщення Штейнберга, канальна трасування, розподіл ланцюгів по верствам і т.д. [3-5]. Під точністю рішення розуміється кількість виділених. . схема програмного модуля проектної операції визначення клік графа, побудованого на основі бібліотеки програмних модулів адаптивних алгоритмів, показана на рис.3. Вхідними параметрами є: Л - необхідна точність рішення, - ресурс часу, відведений для виконання проектної операції, n - число вершин графа, m - число ребер графа (р ^ мірність завдання). Блок адаптації аналізує значення цих параметрів і вибирає один з трьох програмних модулів: POINTS, EIDGES або CLIQUES.

    рис.3.

    POINTS і EIDGES призначені для отримання наближеного рішення - визначення сімейств клік графа, що покривають відповідно всі вершини і ребра графа [6]. При наявності ресурсу часу точність рішення може бути підвищена за рахунок налаштування відповідного модуля на виконання певної кількості

    ,

    підстановок вихідного графа.

    CLIQUES ,

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

    ності [7].

    Вибір числа ітерацій і значення параметра проводиться у відповідність з даними бази даних, які визначають відповідність між необхідною точністю з одного боку і числом ітерацій і значенням керуючого параметра з іншого, в залежності від структури графа. База даних сформована на основі дослідження графів розмірністю до 1000 вершин. Програмне забезпечення розроблене на C ++ Builder 3 для Windows 95 / NT.

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

    ЛІТЕРАТУРА

    1. Крістофідес Н. Теорія графів. Алгоритмічний підхід / Пер. з англ. / Под ред. ГТ. Гаврилова. - М .: Світ, 1978. - 432c.

    2. Рейнгольд Е., Нівергельт Ю., Део Н. Комбінаторні алгоритми. Теорія та практика. / Пер. з англ. / Под ред. В.Б. ^ ексеева. - М .: Світ, 1980. - 476 с..

    3. Меліхов А.Н., Берштейн J1.C., Курейчик В.М. Застосування графів для проектування дискретних пристроїв. - М .: Сов.радіо, 1975. - 224с.

    4. К.К.Морозов і ін. Проектування монтажу друкованих плат на ЕОМ. - М .: Сов.радіо, 1979. - 224 с.

    5. Селютин В.А. Автоматизація проектування електронних пристроїв. - М.: Сов.радіо, 1977. - 384с.

    6. Литвиненко В.А. Методи визначення сімейств клік графа // Методи і програми

    . 2. , . - -

    , 1982. -. 90-92.

    7. Калашников В.А., Литвиненко В.А. До питання визначення сімейств клік графа // 30. Intern. Wiss. Koll. TH llmenau Vortragsreihe. - 1985. - C. 41-44.

    УДК.621.372.6

    H.K. Полуяновіч, A.B. Жуков

    РОЗРОБКА автоматизована система аналізу та синтезу схем ЗАМІЩЕННЯ

    Незважаючи на широке практичне застосування методів і алгоритмів схе-

    ,

    ,

    () .

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

    ,

    електричної схеми ланцюга до, яка описує її, системі рівнянь .

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

    [A] * [X] = [B]

    де в класичному варіанті МУН A-матриця провідностей схеми, Х-вектор вузлових напруг, В-вектор задають джерел струму.

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


    Завантажити оригінал статті:

    Завантажити