Головна Головна -> Реферати українською -> Дисертації та автореферати -> Розробка методів та алгоритмів розв’язання задачі Штейнера на площині

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

Назва:
Розробка методів та алгоритмів розв’язання задачі Штейнера на площині
Тип:
Реферат
Мова:
Українська
Розмiр:
17,10 KB
Завантажень:
191
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10 
Національний технічний університет України
“Київський політехнічний інститут”
Донець Андрій Георгійович
УДК 519.1
Розробка методів та алгоритмів розв’язання задачі Штейнера на площині
01.05.01 – теоретичні основи інформатики та кібернетики
Автореферат дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ - 2002
Дисертацією є рукопис.
Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” Міністерства освіти і науки України.
Науковий керівник: доктор фізико-математичних наук, професор,
Асельдеров Зайнутдін Макашаріпович,
Інститут проблем математичних машин і систем
Національної академії наук України, провідний
науковий співробітник.
Офіційні опоненти: доктор фізико-математичних наук, професор,
Гупал Анатолій Михайлович,
науково-учбовий центр прикладної інформатики Національної академії наук України, директор,
кандидат фізико-математичних наук
Алі Аднан Мохамед, Інститут програмних систем Національної академії наук України, науковий співробітник.
Провідна установа: Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів
еколого-економічних досліджень.
Захист відбудеться “ 25” жовтня 2002 р. об 11 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М.Глушкова Національної академії наук України за адресою:
03680 МСП Київ 187, проспект Академіка Глушкова , 40.
З дисертацією можна ознайомитися в науково-технічному архіві Інституту.
Автореферат розісланий “19” вересня 2002 р.
Учений секретар
спеціалізованої вченої ради
Синявський В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. У різних галузях господарства виникають задачі про з’єднання кількох об’єктів довільної природи загальною мережею мінімальної вартості. Математичним аналогом таких задач є задача про мінімальне остовне дерево (МОД). Мінімальне остовне дерево використовується при розв’язанні таких відомих задач як задача кластеризації, при обчисленні характерної розмірності множини точок і при розпізнаванні образів. Воно також використовувалося для мінімізації довжини провідників при компонуванні електричних схем ЕОМ. МОД дає наближений розв’язок для задачі комівояжера та інших подібних задач. Але розв’язок задачі МОД не приводить до побудови можливої найкоротшої мережі, яка з’єднує задані точки. За умови використання допоміжних точок можлива побудова найкоротшої мережі, яка називається деревом Штейнера. Відповідну задачу вперше сформулювали в 1934 р. М.Кьослер та В.Ярнік, хоча виникнення самої ідеї приписують П’єру Ферма.
У розв’язанні цієї задачі були задіяні такі відомі закордонні вчені як З.Мельзак, Е.Гільберт, Г.Поллак, Ф.Хванг, А.Ахо, М.Гері, Р.Грехем, Д.Джонсон. Досить швидко було встановлено, що задача занадто складна. У 1977 р. Р.Грехем і Д.Джонсон довели NP-повноту цієї задачі.
Для прямокутної метрики розв’язок деяких випадків задачі знайшов В.О.Трубін.
У класичній задачі Штейнера передбачається, що всі ланки мережі, які з’єднують задані точки, однорідні. Проте на практиці в таких галузях економіки, де можна застосувати задачу Штейнера, як проектування трубопроводів, дренажних систем, ліній електромереж, залізниць, автомобільних доріг, різних підсистем САПР всі ланки мережі мають різні вагові характеристики. Цим вимогам відповідає зважена задача Штейнера, де враховуються ці вимоги.
Перші дослідження і впровадження цієї задачі для побудови газопроводів та електромереж були започатковані академіком Н.З.Шором та його учнями у 1967-1970 роках. Очевидно, що зважена задача Штейнера складніша за класичну. З огляду на те, що її застосування завжди є актуальним, стає актуальною і тема всебічного дослідження цієї задачі.
Існують ще декілька різновидностей задачі Штейнера, відмінних від класичної, які виникають при її перенесенні в n-вимірний простір (), або при введенні в простір компактних множин довільної структури, де заборонено проходження з’єднуючих ліній.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок