Національний технічний університет України

“Київський політехнічний інститут”

Донець Андрій Георгійович

УДК 519.1

Розробка методів та алгоритмів розв’язання задачі Штейнера на площині

01.05.01 – теоретичні основи інформатики та кібернетики

Автореферат дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ - 2002

Дисертацією є рукопис.

Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” Міністерства освіти і науки України.

Науковий керівник: доктор фізико-математичних наук, професор,

Асельдеров Зайнутдін Макашаріпович,

Інститут проблем математичних машин і систем

Національної академії наук України, провідний

науковий співробітник.

Офіційні опоненти: доктор фізико-математичних наук, професор,

Гупал Анатолій Михайлович,

науково-учбовий центр прикладної інформатики Національної академії наук України, директор,

кандидат фізико-математичних наук

Алі Аднан Мохамед, Інститут програмних систем Національної академії наук України, науковий співробітник.

Провідна установа: Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів

еколого-економічних досліджень.

Захист відбудеться “ 25” жовтня 2002 р. об 11 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М.Глушкова Національної академії наук України за адресою:

03680 МСП Київ 187, проспект Академіка Глушкова , 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту.

Автореферат розісланий “19” вересня 2002 р.

Учений секретар

спеціалізованої вченої ради

Синявський В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. У різних галузях господарства виникають задачі про з’єднання кількох об’єктів довільної природи загальною мережею мінімальної вартості. Математичним аналогом таких задач є задача про мінімальне остовне дерево (МОД). Мінімальне остовне дерево використовується при розв’язанні таких відомих задач як задача кластеризації, при обчисленні характерної розмірності множини точок і при розпізнаванні образів. Воно також використовувалося для мінімізації довжини провідників при компонуванні електричних схем ЕОМ. МОД дає наближений розв’язок для задачі комівояжера та інших подібних задач. Але розв’язок задачі МОД не приводить до побудови можливої найкоротшої мережі, яка з’єднує задані точки. За умови використання допоміжних точок можлива побудова найкоротшої мережі, яка називається деревом Штейнера. Відповідну задачу вперше сформулювали в 1934 р. М.Кьослер та В.Ярнік, хоча виникнення самої ідеї приписують П’єру Ферма.

У розв’язанні цієї задачі були задіяні такі відомі закордонні вчені як З.Мельзак, Е.Гільберт, Г.Поллак, Ф.Хванг, А.Ахо, М.Гері, Р.Грехем, Д.Джонсон. Досить швидко було встановлено, що задача занадто складна. У 1977 р. Р.Грехем і Д.Джонсон довели NP-повноту цієї задачі.

Для прямокутної метрики розв’язок деяких випадків задачі знайшов В.О.Трубін.

У класичній задачі Штейнера передбачається, що всі ланки мережі, які з’єднують задані точки, однорідні. Проте на практиці в таких галузях економіки, де можна застосувати задачу Штейнера, як проектування трубопроводів, дренажних систем, ліній електромереж, залізниць, автомобільних доріг, різних підсистем САПР всі ланки мережі мають різні вагові характеристики. Цим вимогам відповідає зважена задача Штейнера, де враховуються ці вимоги.

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

Існують ще декілька різновидностей задачі Штейнера, відмінних від класичної, які виникають при її перенесенні в n-вимірний простір (), або при введенні в простір компактних множин довільної структури, де заборонено проходження з’єднуючих ліній.

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

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

Зв’язок роботи з науковими програмами, планами, темами. Проведені в дисертаційній роботі дослідження виконані в рамках держбюджетних тем “Розробка аналітичної інформаційно-довідкової системи “Державна інвентаризація радіоактивних відходів” (№ДР 0100U004613) та “Розвиток та алгоритмічна реалізація апарату конструктивної теорії розв’язання важкорозв’язуваних задач комбінаторної оптимізації” (№ДР 0102U000585).

Мета і задачі дослідження. Предметом дослідження в дисертаційній роботі є класична та зважена задача Штейнера в двовимірному просторі, а також гіпотеза Гільберта – Поллака, яка виділяється з класичної задачі і є окремою проблемою, розв’язаною тільки для значення числа точок 3 = n = 5. Основними методами дослідження є методи обчислювальної геометрії з залученням випуклого аналізу, методів дискретної та неперервної оптимізації, комбінаторного аналізу та теорії графів. Мета дослідження – розробка нових підходів до розв’язання класичної задачі Штейнера; постановка різних типів задач та розробка методів розв’язування зваженої задачі Штейнера; побудова більш досконалого еврістичного алгоритму розв’язування задачі Штейнера; застосування нових підходів для доведення справедливості гіпотези Гільберта – Поллака в цілому або для деяких чисел вершин n = 6.

Наукова новизна одержаних результатів. У дисертації вперше для задачі про точку, що мінімізує суму відстаней від неї до вершин випуклого многокутника, виведено систему тригонометричних рівнянь, які є необхідними умовами екстремуму. Ця задача була поставлена П’єром Ферма і послужила прототипом для задачі Штейнера, а рівняння потім застосовувалися для знаходження властивостей мінімального дерева Штейнера (МДШ) і зваженої задачі Штейнера.

Уперше розглянуто всі розв’язки задачі Штейнера для n = 4 і n = 5 з урахуванням вироджених випадків.

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

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

Доведені нові теореми декомпозиції, які в сукупності з відомими дозволяють зменшити перелік можливих дерев Штейнера на заданій множині точок.

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

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

Для розв’язання проблеми Гільберта – Поллака вперше запропоновано параметричне представлення мінімального дерева Штейнера. Це дало можливість звести вказану проблему до задачі нелінійного програмування.

Наводиться схема, яка дозволяє за рахунок сучасних програмних засобів вирішити питання для наступних значень числа точок n = 6 про справедливість гіпотези Гільберта – Поллака.

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

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

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

Розроблений і реалізований у програмному вигляді еврістичний алгоритм знаходження мінімального дерева Штейнера може бути застосований при проектуванні різних комунікаційних мереж (нафтопроводів, газопроводів, ліній електропередач, ліній зв’язку, мережі автомобільних доріг та залізниць тощо). У загальному вигляді навіть при наближеному розв’язку це дасть значний економічний ефект, а для деяких обмежених варіантів гарантовано точний оптимальний розв’язок.

Розроблена методика для постановки задачі і створення відповідного алгоритму розв’язування зваженої задачі Штейнера. Запропоновано два типи таких задач: з постійними та змінними вагами ділянок з’єднуючого дерева Штейнера, які можуть застосовуватись з урахуванням різних вимог практичної

конкретної задачі. Зважена задача Штейнера більше відповідає таким вимогам на відміну від класичної задачі.

Запропоноване параметричне представлення дерева Штейнера дозволяє звести проблему Гільберта – Поллака до серії задач нелінійного програмування. Наведена схема доведення проблеми, яка може бути реалізована в майбутньому у вигляді програмного забезпечення. Крім того, параметричне представлення дає можливість безпосереднього знаходження МДШ для багатьох спеціальних конфігурацій заданих точок.

Значна частина результатів дисертації може бути використана в навчальному процесі вузів України, де викладаються дисципліни “Прикладна математика” та “Геометричне моделювання”.

Особистий внесок здобувача. У працях, що написані в співавторстві, дисертанту належить: у [2] – основна ідея роботи, побудова алгоритму та теоретичне обгрунтування; в [4] – тестові випробування алгоритму переліку різнокомпонентних дерев; у [6] – втілення ідеї наукового керівника в теоретичні твердження та їх доведення. Праця [2] написана у співавторстві з Шулінком Г.О., [4] – з Петренюком А.Я., [6] – з Асельдеровим З.М.

Усі інші результати, що складають зміст дисертації, автором отримані особисто.

Апробація результатів дисертації. Окремі результати дисертаційної роботи доповідалися на XXI науковому міжнародному семінарі “Дискретна математика” (Одеса, вересень 1999 р.), на науковому семінарі з дискретної математики кафедри економічної кібернетики Запоріжського державного університету (травень 2000 р.), на науковому семінарі кафедри обчислювальної математики та математичної кібернетики у Дніпропетровському державному університеті ( вересень 2000 р.), на міжнародній конференції “Комп’ютерна математика. Оптимізація обчислень” (Севастополь, травень 2001 р.), на міжнародній конференції з прикладної математики, присвяченій 65-річчю з дня народження Б.М.Пшеничного (Київ, червень 2002 р.).

Дисертаційна робота в цілому обговорювалась на науковому семінарі “Теорія оптимальних рішень” Інституту кібернетики ім. В.М.Глушкова НАН України (квітень 2002 р.).

Публікації. Основні результати дисертації викладено у 8 наукових працях, з них 3 – у журналі “Математичні машини і системи”, 5 – у фахових наукових збірниках праць.

Обсяг та структура роботи. Дисертаційна робота складається зі вступу, п’яти розділів, висновків, списку використаних джерел і одного додатку. Повний обсяг дисертації – 190 сторінок, серед них 53 рисунків і 4 таблиці, бібліографія налічує 244 найменувань на 20 сторінках, додаток – 55 сторінок.

ЗМІСТ РОБОТИ

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

У першому розділі “Огляд літератури за темою і вибір напрямків досліджень” зроблено аналітичний (та історичний) огляд виникнення задачі Штейнера на площині, етапів її розв’язування та трансформування її в сучасну проблему. Показано, що задача Штейнера набула багато модифікацій та розгалужень, серед яких, крім вищезазначеної, найбільш відомими стали задача Штейнера на графах та задача Штейнера з прямокутною метрикою. Для цих задач Грехем, Джонсон у 1977 р. довели, що вони також є NP-повними. Огляд досягнутих результатів за останні 40 років показує, що навіть у класичній постановці задачі Штейнера невирішеними, а також недостатньо вивченими залишаються такі питання:

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

-

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

- створення більш досконалих еврістичних алгоритмів знаходження МДШ для довільного числа заданих точок;

- доведення справедливості гіпотези Гільберта – Поллака, яка є важливою для оцінки еврістичних алгоритмів, для числа точок, більшого 5.

У зв’язку з тим, що при проектуванні різних комунікаційних мереж застосовується математична модель, тією чи іншою мірою адекватна задачі Штейнера, виникає практична необхідність проведення таких досліджень:

- знаходження нових правил декомпозиції, які давали б можливість удосконалити існуючі точні алгоритми (типу Е.Кокейна) знаходження МДШ;

- розробка більш досконалих еврістичних алгоритмів знаходження МДШ, які б повністю ліквідували численні недоліки і вади подібних відомих алгоритмів;

- розробка формалізованої постановки, побудова алгоритму (точного, чи еврістичного) розв’язку задачі Штейнера, у якої ділянки з’єднуючого дерева мають різну вагу, з метою застосування для розв’язування конкретних практичних задач;

- розробка нових математичних інструментів, які б спростили або дали можливість дальшого просування в теоретичному доведенні справедливості гіпотези Гільберта–Поллака;

- розробка алгоритмів та відповідних інформаційних технологій, які б дозволили за допомогою комп’ютерних обчислень зробити наступний крок для доведення гіпотези Гільберта – Поллака.

Цими об’єктивнми даними обумовлювався вибір напрямків досліджень.

У другому розділі “Класична задача Штейнера” описується задача, яка формулюється так.

Задача Штейнера. На площині задана множина точок . Необхідно знайти найкоротше з’єднуюче дерево, використовуючи за можливістю додаткову множину точок (0 = m = n – 2).

Ця задача виникла з іншої задачі, яку розглядав у свій час П’єр Ферма: для заданого опуклого многокутника P1, P2, . . . , Pn знайти точку O, сума відстаней від якої до вершин многокутника мінімальна.

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

(1)

(2)

Для n = 3, якщо всі кути трикутника ABC менші 1200, ця задача і задача Штейнера збігаються.

Побудуємо на стороні AB рівносторонній трикутник , де вершини A, B і (AB) обходяться проти годинникової стрілки. Якщо з’єднати точки C і (AB) відрізком, а потім описати коло навколо , то точка перетину D є розв’язком цих двох задач для трикутника (рис. 1,а). Відрізок C(AB) називається віссю Сімпсона. Якщо зробити аналогічну побудову на їнших сторонах , то отримаємо ще дві вісі, і всі вони мають однакову довжину. З побудови легко знайти координати точки (AB):

(3)

Аналогічно виконується побудова для опуклого чотирикутника P1P2P3P4 (рис. 1,б). Тут можуть існувати дві альтернативні вісі Сімпсона – AB і CD. Якщо , то відповідна вісь Сімпсона AB називається невиродженою. У цьому розділі знайдені необхідні і достатні умови того, щоб вісь Сімпсона була оптимальною і невиродженою.

Теорема 2.1. У опуклому чотирикутнику вісь Сімпсона буде невиродженою, якщо відповідний кут між діагоналями чотирикутника 1200.

Для п’яти точок уже існує п’ять альтернативних осей Сімпсона. У дисертації детально розглянуті всі випадки розташування цих точок (у тому числі й вироджені).

Драбиною називається множина точок , з координатами і (i = 1, 2, . . . , m), де b – дійсне число, і . Якщо b = 1, то . На рис. 2 зображена драбина . Драбини вперше почали вивчати Чунг і Грехем у 1978 році. Дуже швидко можна знайти оптимальне дерево Штейнера для m = 2k (k = 1). Це дерево складається з k повних дерев Штейнера, отриманих для чотирьох вершин.

Для k = 1 довжина оптимального дерева ; для довільного k . Для m = 2k + 1 (k = 1) питання було вирішено не відразу. Чунг і Грехем знайшли правильну формулу для довжини оптимального дерева, але невірно вказали метод його побудови. Лише через 18 років у 1996 р.

Р.Буркард, Т.Дудаш та Т.Майєр виявили цю помилку і запропонували інший спосіб побудови, який приводить до оптимальної формули. У дисертації пропонується загальний метод побудови МДШ для парних і непарних m і виводиться загальна формула його довжини:

. (4)

У цьому розділі розглядаються також інший тип драбин, у яких b = 1, а ордината верхніх точок a = 1. Для парних m наведені два способи побудови МДШ, один з яких буде оптимальним при , а другий – при . Для непарних m знаходяться умови, за яких побудоване дерево є повним деревом Штейнера:

. (5)

У третьому розділі “Про алгоритми розв’язування задачі Штейнера” йдеться мова про існуючі алгоритми знаходження МДШ і запропоновано еврістичний алгоритм знаходження МДШ, оснований на побудові МОД.

Серед точних алгоритмів розв’язання задачі Штейнера найбільш відомий алгоритм Е.Кокейна, який був започаткований у 1967 р. і доведений до програмної реалізації в 1972 році. З того часу в усіх публікаціях на дану тему користуються термінологією (нотацією) Кокейна.

Визначення. Дерево U на множині точок , де , (називаються p-точки і s-точки відповідно) є дерево Штейнера на P, якщо виконуються умови:

А1: U – таке, що не самоперетинається;

А2: степінь вершини si дорівнює 3, 1 = i = k;

А3: степінь вершини Pj не більше 3,;

А4: кожна s-точка з’єднує три вершини в U;

А5:

Повне дерево Штейнера (ПДШ) на P є дерево, яке задовольняє умовам А1-А4 і має n – 2 s-точки.

Мелзак першим довів, що на множині P існує скінченна множина дерев Штейнера і геометричний спосіб їх побудови, яка містить усі МДШ.

Теорема 3.1. Нехай U є МДШ на P. Тоді для деякої множини на P, де і 1 = t = n – 1, U – об’єднання піддерев Ui, i = 1, 2, . . . , t, де Ui для кожного i – є ПДШ і МДШ на Ai.

Рис. 3 ілюструє цю теорему, на основі цієї якої Е.Кокейн створив послідовність процедур для розв’язання проблеми Штейнера.

Крок 1. Формується множина D підмножин множини P.

Крок 2. Для заданого будується оцінка для всіх

дерев Td, де кожна Td – об’єднання мінімальних за довжиною ПДШ на A1, A2, . . . , At. Тоді всі дерева МДШ на P містяться в класі , який є остаточним.

Розмір цього класу настільки великий, що не дозволяє розробити ефективний алгоритм навіть для сучасних комп’ютерів. Тому цю проблему розв’язують двома способами. По-перше, розробляють більш досконалі алгоритми, які дозволяють зменшити перелік всіх варіантів, а по-друге, будують критерії, які дозволяють відсіяти більшість варіантів множин дерев, або розбити їх на менші підмножини. Більшість цих критеріїв, або правил декомпозиції, винайшли Мелзак, Гільберт і Поллак. Кокейн ввів ще два критерії, які використовують концепцію опуклості множини P. Він ввів поняття каркасу Штейнера M(P), яке спочатку збігається з поняттям опуклої оболонки (многокутником) множини P. Далі на кожному кроці з периметра цього многокутника видаляються точки, які не можуть належати МДШ. В остаточному вигляді каркас Штейнера може складатися з декількох многокутників, два сусідніх з яких мають спільну точку.

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

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

Теорема 3.11. Нехай ABCD – опуклий чотирикутник, у якого . Позначимо , , , причому (рис. 4,а). Нехай задовольняються умови

1)

2)

3)

4)

Тоді МДШ не заходить в середину чотирикутника.

У цьому розділі запропоновано еврістичний алгоритм знаходження МДШ, в основі якого лежить алгоритм побудови МОД. Існує декілька подібних еврістичних алгоритмів, з них найбільш заслуговує уваги алгоритм, який запропонували у 1981 р. Сміт, Лі і Лібман. При цьому вони використовували також тріангуляцію Делоне і діаграму Вороного. Однак у всіх подібних алгоритмах мовчазно передбачалось, що вироджене дерево, яке складається тільки з вершин множини P, є оптимальним і не потребує удосконалення. Розглянемо випадок МОД, яке складається з послідовності відрізків з постійним відношенням (i = 1) і постійним кутом повороту (рис. 5), при цьому 1200 ? б < 1800.

Таке дерево, яке називається логарифмічною спіраллю, для кутів повороту 1200 < б < 1800 розглядав Венг для точок Штейнера. Він довів теорему, яка аналогічно може бути доведена для даного випадку.

Теорема 3.15. Логарифмічна спіраль, означена вище, має полюс O, який є граничною точкою an при n ? 8, і полярні кути рівні між собою.

Розглянемо випадок, коли . Легко довести, що чотирикутники aiai+1am+i+1am+i подібні чотирикутнику a0a1am+1am з коефіцієнтом подібності ki. Доведена

Теорема 3.16. Існує дерево Штейнера, побудоване на вершинах спіралі, довжина якого менша від довжини спіралі.

Доведення теореми проводиться конструктивним чином для значень і k = 2/3. В еврістичному алгоритмі, запропонованому в дисертації, вміщено модуль, який виявляє всі подібні спіралі в МОД і перетворює їх в дерева Штейнера меншої довжини. Це означає, що запропонований алгоритм вигідно відрізняється від подібних існуючих.

У четвертому розділі “Зважена задача Штейнера” йдеться про принципово нове розширення поняття задачі Штейнера. Спочатку розглянемо її для трьох точок.

На площині задано три точки: P1, P2 і P3 з відповідними вагами , і . Необхідно знайти таку точку O, яка дає мінімум величині

.

Для цієї функції аналогічно класичній задачі Штейнера можна вивести необхідні умови типу (1) – (2) у вигляді тригонометричних рівнянь. Тоді друге рівняння з (1) і друге рівняння з (2) буде відповідати системі

(6)

З цієї системи знаходимо

. (7)

Ця формула вірна для будь-якої перестановки індексів. З неї витікають обмеження на ваги (правило трикутника)

{i,j,k} = {1,2,3}. (8)

Як і для класичної задачі Штейнера, тут також можливі вироджені випадки, коли оптимальною точкою може бути будь-яка вершина . Умови невиродженості мають вигляд

(9)

Якщо аналогічно рис.1 побудувати точку за правилом , , то P3K є зважена вісь Сімпсона, і перетин її з колом, описаним навколо , дає точку O, яка дає мінімум функції Z. Координати точки K знаходяться за формулами

(10)

де , а замість індексів Pi пишеться i. У множині з чотирьох точок зважене дерево також може мати два варіанти з п’яти ділянок, тому необхідно мати два значення ваги п’ятої ділянки. Якщо вони задані, то за формулами (10) можна побудувати еквівалентну точку K і перейти до варіанту з трьох точок. У загальному вигляді постановка зваженої задачі Штейнера формулюється так:

на площині задана скінченна множина точок , яким відповідає вага (i = 1, 2, . . . , n), і задано правило, за яким ділянці AB приписується вага , якщо відома топологія дерева, побудованого на множині , де S – довільна множина точок. Необхідно знайти дерево з мінімальною сумарною зваженою довжиною його ділянок.

Основні вимоги, які висуваються до функції ваги , витікають з умов (8). Для чотирикутника P1P2P3P4 це “правило чотирикутника” для (i = 1, 2, 3, 4), а для ділянки AB, яка відповідає об’єднанню ,

(11)

де (i = 1, 2), і для них . У дисертації проаналізовано всі випадки зваженої задачі Штейнера для чотирьох і п’яти точок. Для більшої кількості точок важливим є спосіб задавання функції ваги. Показано, що існують два способи – табличний і аналітичний. Перший задає значення функції ваги для всіх можливих топологій з’єднуючого дерева, а другий – обчислює значення за відомими значеннями ваги інцидентних ділянок, або вершин P. На прикладах доведено, що алгоритм Кокейна для знаходження МДШ можна модифікувати і для зваженої задачі Штейнера, якщо внести поправки вагової функції до всіх відповідних правил декомпозиції.

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

1. Функцію ваги можна задавати у вигляді поверхні, тоді вагою ділянки буде довжина геодезичної лінії між двома точками. Типовою поверхнею є така

(12)

Тоді задача зводиться до знаходження інтегралу

(13)

2. Нехай вага ділянки задається тією ж функцією і сумується по всій довжині кривої. Тоді вага криволінійної ділянки між двома точками A і B

. (14)

Рівняння Ейлера після перетворень зведеться до такого:

(15)

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

П’ятий розділ “Про проблему Гільберта – Поллака” висвітлює класичну задачу Штейнера з іншого боку, який порівнює між собою МОД та МДШ. Нехай - довжина МОД, а - довжина МДШ для заданої множини P точок на площині. Гільберт і Поллак у 1968 р. висунули гіпотезу про те, що

(16)

Як відомо, МДШ складається з декількох нових дерев Штейнера на підмножинах Ai (i = 1, 2, . . . , k), де . Нехай - довжина відповідного повного дерева Штейнера, тобто , а - довжина мінімального остовного дерева на множині точок Ai. Гіпотеза Гільберта – Поллака стверджує, що для i = 1, 2, . . . , k.

Для n = 3 Гільберт і Поллак довели справедливість гіпотези у 1968 р., у 1977 р. Поллак робить це для n = 4 і в 1985 р. Ду, Яо і Хванг довели це для n = 5. З того часу за цією темою нічого не друкувалось.

У цьому розділі дисертант наводить значно спрощене доведення для n = 4, ніж у Поллака. Далі запропоновано параметричний підхід до класичної задачі Штейнера, який полягає в заміні змінних у вигляді координат точок P, на параметри якими є довжини ділянок шуканого дерева Штейнера. На рис. 6,а це відображено для n = 4.

Координати заданих точок легко записуються через параметри вектора :

Другий варіант побудови дерева Штейнера наведено на рис. 6,б, де використовується вектор параметрів . Нехай - довжина дерева Штейнера в системі параметрів .

Теорема 5.1. Для того, щоб вісь Сімпсона довжиною S була оптимальною, необхідно виконання співвідношення

де .

Параметричне представлення МДШ дозволяє проблему Гільберта Поллака звести до розв’язання задач нелінійного програмування. Це означає, що якщо раніше цю проблему вирішували за рахунок інтелекту дослідника, із залученням складних геометричних побудов, то тепер основний тягар розрахунків перекладається на ЕОМ. Для цього загальний алгоритм доведення справедливості гіпотези Гільберта – Поллака розбивається на три менші алгоритми.

А1 – алгоритм, який перелічує всі можливі остовні дерева для заданої кількості точок. При цьому використовуються геометричні властивості площини.

А2 – алгоритм, який вибирає чергову топологію дерева Штейнера і формує для кожного остовного дерева задачу лінійного програмування. При цьому відсіваються ті остовні дерева, які не відповідають умовам оптимальності.

А3 – алгоритм, що розв’язує задачу нелінійного програмування. У дисертації наводиться приклад для n = 4. Всього остовних дерев для цього випадку 16. За рахунок симетрії і за умов оптимальності відсівається 9 варіантів і залишається розв’язати 7 задач лінійного програмування з обмеженнями.

Для n = 5 всього допустимих остовних дерев налічується 49. За рахунок симетрії можна зменшити це число до 38. Якщо зважити на те, що існує 5 дерев Штейнера, то при порівнянні одного оптимального з іншими чотирма можна це число ще зменшити. Це потребує деякого формалізму, який теж можна запрограмувати і перекласти цю роботу на комп’ютер.

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

ВИСНОВКИ

Основні результати дисертаційної роботи:

1. Виведена система тригонометричних рівнянь, які є необхідними умовами для точки, що дає розв’язок узагальненої задачі Ферма на площині.

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

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

4. Розроблено еврістичний алгоритм знаходження мінімального дерева Штейнера (МДШ), який використовує алгоритм побудови мінімального остовного дерева (МОД). Він має складність O(nlogn), як і найкращі відомі алгоритми, але відрізняється тим, що в ньому вперше розглянуто вироджений випадок, коли МОД має фрагменти у вигляді спіралей. Алгоритм переробляє такі спіралі в мінімальні піддерева МДШ.

5. Уперше формалізована зважена задача Штейнера, яка відрізняється від класичної тим, що ділянки МДШ мають певну вагу. Виведені формули, які є необхідними умовами для оптимальності вибраних додаткових точок Штейнера. Задача повністю досліджена для чотирьох і п’яти точок.

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

7. Запропоновано і теоретично обгрунтовано новий параметричний підхід до розв’язання класичної задачі Штейнера, в якому параметрами є довжини ділянок МДШ. Це дає змогу для деяких множин точок, які утворюють певну конструкцію, отримувати розв’язок задачі безпосередньо.

8. На основі вказаного підходу запропоновано метод розв’язання гіпотези Гільберта – Поллака для кількості вершин, більшої 5, який зводить проблему до розв’язання декількох задач нелінійного програмування з квадратичними обмеженнями у вигляді нерівностей.

9. Запропоновано загальну схему для побудови трьохетапного алгоритму, який би розв’язував гіпотезу Гільберта – Поллака за допомогою вищезгаданого методу.

Основні положення дисертації опубліковані в таких працях:

1. Донец А.Г. Об одном подходе к решению задачи Штейнера // Математические машины и системы. – 1997. – № 2. – С.41-42.

2. Донец А.Г., Шулинок Г.А. Быстрый алгоритм построения выпуклой оболочки на плоскости // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1999. – С.85-91.

3. Донец А.Г. О взвешенной задаче Штейнера // Математические машины и системы. – 2000. – №1. – С.55-64.

4. Донец А.Г., Петренюк А.Я. О перечислении разнокомпонентных

древесных разложений. // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2000. – С.70-75.

5. Асельдеров З.М., Донец А.Г. О теоремах декомпозиции для задачи Штейнера // Математические машины и системы. – 2000. – №2,3. – С.16-21.

6. Донец А.Г. Решение задачи Штейнера для вписанных многоугольников // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М.Глушкова НАН України, 2000. – С.110-117.

7. Донец А.Г. Параметрический подход к решению задачи Штейнера // Комп’ютерна математика. Оптимізація обчислень. – К.: Ін-т кібернетики ім. В.М.Глушкова НАН України, 2001. – Т.2. – С.120-126.

8. Донец А.Г. О гипотезе Гильберта – Поллака для оптимальных деревьев Штейнера // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 2001. – С.72-76.

Донець А.Г. Розробка методів та алгоритмів розв’язання задачі Штейнера на площині. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Національний технічний університет України “Київський політехнічний інститут”, Київ, 2002.

Дисертаційну роботу присвячено вивченню та аналізу задачі Штейнера на площині та пов’язаних з нею проблем. У вигляді тригонометричних рівнянь виведено необхідні умови існування розв’язку узагальненої задачі Ферма, яка стала прототипом задачі Штейнера; виведена загальна формула довжини мінімального дерева Штейнера для конструкцій типу “драбин”. Розроблено новий алгоритм побудови опуклої оболонки множини точок на площині, новий еврістичний алгоритм складністю O(nlogn) розв’язання задачі Штейнера. Доведено, що такі фрагменти мінімального остовного дерева як спіралі можна трансформувати у піддерева меншої довжини. Формалізовано постановку зваженої задачі Штейнера, яка відрізняється від класичної тим, що в ній ділянки мінімального дерева мають певну вагу. Виведені необхідні умови оптимальності її розв’язку. Побудовані три моделі зваженої задачі Штейнера, наближені до практичних задач. Запропоновано і теоретично обгрунтовано новий параметричний підхід до розв’язання класичної задачі Штейнера. На основі цього підходу розроблено метод обгрунтування гіпотези Гільберта – Поллака, який зводить проблему до розв’язання задач нелінійного програмування. Запропоновано загальну схему для побудови трьохетапного алгоритму обгрунтування гіпотези Гільберта – Поллака.

Ключові слова: мінімальне остовне дерево, мінімальне дерево Штейнера, опукла оболонка, еврістичний алгоритм, зважена задача Штейнера, гіпотеза Гільберта – Поллака.

Донец А.Г. Разработка методов и алгоритмов решения задачи Штейнера на плоскости. – Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. – Национальный технический университет Украины “Киевский политехнический институт”, Киев, 2002.

Диссертационная работа посвящена изучению и анализу задачи Штейнера на плоскости и связанных с нею проблем. Исследована обобщенная задача Пьера Ферма, которая послужила прототипом классической задачи Штейнера. Выведены необходимые условия существования решения задачи, которые записаны в виде системы тригонометрических уравнений. Из них легко получить решение задачи для четырех и пяти точек.

Описана новая процедура построения минимального дерева Штейнера для системы точек, образующих прямоугольную “лестницу”. Это позволило вывести формулу длины этого дерева, справедливую для четного и нечетного числа ступенек этой лестницы, и которая обобщает формулы, ранее найденные раздельно. Найдены подобные формулы и для других типов лестниц.

Разработан алгоритм определения выпуклой оболочки множества точек на плоскости, в основу которого положено покоординатное упорядочение этих точек. В общем случае он выгодно отличается от известных подобных алгоритмов обхода Грехэма и БЫСТРОБОЛ-метода.

Разработан эвристический алгоритм определения минимального дерева Штейнера, в основу которого положен алгоритм определения минимального остовного дерева. Хотя его сложность равна O(nlogn), как и лучших известных алгоритмов, но он отличается тем, что в нем впервые улучшается длина таких вырожденных фрагментов как спираль.

Впервые формализована постановка взвешенной задачи Штейнера, которая отличается от классической тем, что в ней каждый участок связывающего дерева имеет определенный вес. Найдены зависимости, являющиеся необходимыми условиями минимальности взвешенного дерева.

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

Теоретически обоснован и на примерах опробован новый параметрический подход к решению классической задачи Штейнера. В нем вместо переменных координат точек введены параметры, какими являются длины участков связывающего дерева Штейнера. Это позволяет в некоторых случаях получать решение задачи Штейнера непосредственно.

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

Ключевые слова: минимальное остовное дерево, минимальное дерево Штейнера, выпуклая оболочка, эвристический алгоритм, взвешенная задача Штейнера, гипотезы Гильберта – Поллака.

Donets A. G. Development of methods and algorithms for solving the Steiner problem on plane. – Manuscript.

Thesis for a candidate scientific degree in physics and mathematics by the speciality 01.05.01 – theoretical foundation for the informatics and cybernetics. – The national technical university of Ukraine. “Kyiv politechnical institute”, Kyiv, 2002.

The thesis is devoted to the study and analysis of the Steiner problem on a plane and related problems. Necessary conditions for the existence solution to of the generalized Fermat problem being a prototype to the Steiner problem are derived in the form of trigonometrical equations. A general formula for the minimal length of the Steiner tree for “ladder”- type constructions is obtained. A new algorithm is created for constructing the convex hull of a set of points on the plane. Also a new heuristic algorithm of O(nlogn) complexity is devoloped for solving the Steiner problem. It is proved that spiral fragments of the minimal spanning tree can be transformed into subtrees of lesser length. The statement of the weighed Steiner problem is advanced differing from the classic by the minimal tree sections having certain weight. Necessary conditions for optimality of solutions to this problem are developed. Three different models of the weighed Steiner problem are suggested, which are close to practical problems. A new parametric approach to solving the classic Steiner problem is advanced and theoretically grounded. On the basis of this approach a method for