Багатокритеріальний пошук та візуалізація оптимальних шляхів на мережі

Інститут кібернетики імені В.М. Глушкова НАН України Київський національний університет імені Тараса Шевченка Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» Чернівецький національний університет імені Юрія Федьковича «ПРОБЛЕМИ ІНФОРМАТИКИ ТА КОМП’ЮТЕРНОЇ ТЕХНІКИ» (ПІКТ – 2025) Праці XIV Міжнародної науково-практичної конференції ЧЕРНІВЦІ 13 – 15 ЛИСТОПАДА, 2025 Чернівці 2025 Проблеми інформатики та комп’ютерної техніки: праці XIV Міжнародної науково-практичної конференції (ПІКТ – 2025), присвяченої 85-й річниці від дня народження проф. Кириченка М.Ф. м. Чернівці, 13–15 лист. 2025. Чернівці : Технодрук, 2025. 204 с. Програмний комітет: Організаційний комітет: Співголови Білоскурський Р.Р. проф. (Україна, Чернівці) Крак Ю.В., проф. (Україна, Київ) Члени комітету Азаров О.Д., проф. (Україна, Вінниця) Байєр Г., проф. (Німеччина, Цвікау) Бармак О.В., проф. (Україна, Хмельницький) Абабій В., проф. (Молдова, Кишинів) Граур А., проф., (Румунія, Сучава) Гребеннік І.В., проф. (Україна, Харків) Григорків В.С., проф. (Україна, Чернівці) Дейбук В.Г., проф. (Україна, Чернівці) Дивак М.П., проф. (Україна, Тернопіль) Добровольський Ю.Г., проф. (Україна, Чернівці) Крістіа Д., проф., (Румунія, Ясси) Кушнір Р.М., проф. (Україна, Львів) Куц Р. проф., (США, Ньюхевен) Мельник А.О., проф. (Україна, Львів) Наконечний О.Г., проф. (Україна, Київ) Пікієвич П., проф., (Польща, Д.-Гурнича) Ситніков В.С., проф. (Україна, Одеса) Станушек М., проф., (Польща, Краків) Тарасенко В.П., проф. (Україна, Київ) Ушенко Ю.О., проф. (Україна, Чернівці) Федасюк Д.В., проф. (Україна, Львів) Філіпова Л. PhD, (Словаччина, Братислава) Хаас В., проф., (Чехія, Прага) Хіміч О.М., проф. (Україна, Київ) Чикрій А.О., проф. (Україна, Київ) Шрайнер В., проф., (Австрія, Лінц) Ясній П.В., проф. (Україна, Тернопіль) Якоб Ф., проф., (Словаччина, Кошице) © Чернівецький нац. ун-т, 2025 © ПВКФ "Технодрук", 2025 Голова Остапов С.Е., проф. Заступники голови Баловсяк С.В., доц., Малик І.В., проф., Угрин Д.І., проф. Члени оргкомітету Руснак М.А. – вчений секретар, Антонюк С.В., Воробець Г.І., Газдюк К.П., Дрінь Я.М., Кириченко О.Л., Кириченко О.О., Коцур М.П., Лазорик В.В., Стецько Ю.П., Танасюк Ю.В., Тимофієва Є.М., Філіпчук О.І., Фратавчан В.Г., Яковлєва І.Д. ISBN 978-617-8034-69-6 ISBN 978-617-8034-69-6 УДК 004(082) П-78 П-78 5 СЕКЦІЯ 4 КОМП’ЮТЕРНІ СИСТЕМИ І КОМПОНЕНТИ .................................................................................................... 79 КРИВОРУЧКО О.В., ЧОРНОУС О.С. ІНТЕЛЕКТУАЛЬНЕ УПРАВЛІННЯ ТА МОНІТОРИНГ МАГІСТРАЛЬНИХ ОПТОВОЛОКОННИХ МЕРЕЖ ПРОВАЙДЕРІВ . 79 ЛЯШКЕВИЧ В.Я., ОЛАР О.Я., ЯРОШЕНКО О.І. ВИБІР РЕЛЕВАНТНИХ ОЗНАК АНОМАЛЬНИХ ПРОЯВІВ У КОМП’ЮТЕРНИХ МЕРЕЖАХ ДЛЯ ЇХ АВТОМАТИЗОВАНОГО ВИДОБУВАННЯ З МЕРЕЖНОГО ТРАФІКУ ..................................................................................................................................... 81 СЕКЦІЯ 5 УПРАВЛІННЯ ТА МОДЕЛЮВАННЯ В СОЦІАЛЬНИХ І ЕКОНОМІ-ЧНИХ СИСТЕМАХ ....................... 83 BOROZAN O., ABABII V. ANALYSIS OF EMOTIONS IN SPEECH TO IDENTIFY EXCEPTIONAL SITUATIONS ...................................................................... 83 MELNIC R., ABABII V. DECISION SUPPORT SYSTEM FOR THE MANAGEMENT OF EDUCATIONAL INSTITUTIONS .................................................... 86 RORARI A., BOROZAN O., DRUMEA N., CLIMA A., ABABII V. APPLYING VIRTUAL REALITY MODELS IN REAL-TIME PROCESS MONITORING AND CONTROL ............................................ 88 STRUNA V., LUNGU I., ROȘCA N., LASCO V., ABABII V. ADAPTIVE SERVICE-ORIENTED COMPUTING ARCHITECTURE ................................................................................................... 90 IVATO Y., BUN R. SPATIAL MODELING OF GREENHOUSE GAS EMISSION PROCESSES FROM OIL INDUSTRY IN UKRAINE ............................. 92 КАПТАР Д.Є., ФРАТАВЧАН В.Г. СИСТЕМА ОБРОБКИ РЕЗУЛЬТАТІВ СОЦІОЛОГІЧНИХ ОПИТУВАНЬ СТУДЕНТІВ ................................................................. 94 МАГДА К.М., РУСНАК М.А. БАГАТОКРИТЕРІАЛЬНИЙ ПОШУК ТА ВІЗУАЛІЗАЦІЯ ОПТИМАЛЬНИХ ШЛЯХІВ НА МЕРЕЖІ ........................................... 96 МОСЯНДЗ О.М., ФРАТАВЧАН В.Г. ВІЗУАЛЬНИЙ МОНІТОРИНГ ХРОНОЛОГІЇ ПРИКОРДОННИХ ПРАВОПОРУШЕНЬ ............................................................... 97 NIKOLENKO K., MOROZ V. INTEGRATION OF MULTI-SCALE ADAPTIVE ATTENTION MECHANISM FOR SEMANTIC SEGMENTATION IN AUTONOMOUS DRIVING ..................................................................................................................................................................... 99 POHORILETS D., BUN R. GEOSPATIAL ANALYSIS OF CONSEQUENCES OF WAR-INDUCED FOREST FIRES IN THE ZHYTOMYR, RIVNE, AND VOLYN REGIONS USING SATELLITE IMAGE PROCESSING AND A CLOUD PLATFORM ....................................................................... 101 PUTO A., BUN R. SPATIAL MODELING OF GREENHOUSE GAS EMISSIONS FROM ROAD TRANSPORT IN UKRAINE ........................................ 103 УРБАНОВИЧ А.М., МІНКОВ К.О., ФРАТАВЧАН В.Г. ПЕРСОНАЛЬНИЙ АСИСТЕНТ ОБЛІКУ ОСОБИСТИХ ФІНАНСОВИХ ВИТРАТ: МОДЕЛЬ, АЛГОРИТМИ ТА РЕАЛІЗАЦІЯ НА ПЛАТФОРМІ PYTHON ................................................................................................................................................................. 105 РУСНАК М.А., ФАРБАТЮК В.В. ЛІНІЙНЕ ПРОГРАМУВАННЯ – ГЕНЕРАЦІЯ ТА РОЗВ'ЯЗУВАННЯ ПРИКЛАДІВ .................................................................... 106 СЕКЦІЯ 6 ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА ЇХ ЗАСТОСУВАННЯ ................................................ 109 БАНДУРА Б. В., АНТОНЮК С. В. SPOTWISE - ІНТЕЛЕКТУАЛЬНИЙ ТУРИСТИЧНИЙ АСИСТЕНТ ................................................................................................ 109 УГРИН Д.І., УШЕНКО Ю.О., БРЕСЛАВСЬКИЙ О.І. 96 УДК 519.81(075.8) МАГДА К.М., РУСНАК М.А. Чернівецький національний університет імені Юрія Федьковича (Україна) БАГАТОКРИТЕРІАЛЬНИЙ ПОШУК ТА ВІЗУАЛІЗАЦІЯ ОПТИМАЛЬНИХ ШЛЯХІВ НА МЕРЕЖІ Запропоновано метод візуалізації пошуку оптимальних маршрутів у графі з двома критеріями на основі алгоритму Мінті. Постановка задачі. Розглянемо зорієнтований граф (𝐼 ), де 𝐼 – множина вершин графа, ( ) 𝐼 – множина дуг (упорядкованих пар вершин) графа. Кожній вершині 𝐼 поставимо у відповідність дійсне число , кожній дузі ( ) – два невід’ємних числа та . Такий граф будемо називати мережею. Число будемо називати інтенсивністю вершини 𝐼. Якщо , вершину назвемо джерелом, якщо , – стоком, якщо , – нейтральною. Відповідне дузі ( ) число характеризує її з якісного боку (довжина дуги, прибуток від використання дуги), число задає внутрішні обмеження дуги (пропускну здатність)[1]. Мережа допускає потік ( ) , якщо виконуються співвідношення: Основною оптимізаційною задачею на мережі є знаходження оптимального потоку , на якому досягає мінімуму функція вартості: Частинним випадком цієї задачі є задача про найкоротший шлях. Нехай мережа має одне джерело (вершина 1) та один стік (вершина n), тобто d1 = 1, dn = -1, а решта вершин нейтральні (dі = 0). Умову (2) умовою цілочисельності потоку: xіj {0,1}. Отримаємо задачу: де cіj – це довжина дуги (i, j). Для розв’язання задачі (4) - (6) застосовується метод Мінті[2], який дозволяє знайти найкоротші шляхи від джерела до кожної з вершин мережі. Алгоритм методу Мінті: 1) Вершині 1 (джерелу) ставимо у відповідність позначку h1 = 0. 97 r) На кроці r маємо множину позначених вершин та множину не позначених вершин , зауважимо, що . r+1) Для кожної дуги ( ), де i , j , обчислюємо величину hj = hi + ci,j і виділяємо ті дуги, для яких ця величина мінімальна, а саму вершину переносимо в множину . Процес повторюємо, доки можна «розширювати» множину I, у противному випадку – алгоритм завершено, позначка кожної вершини є довжиною оптимального шляху до неї від джерела. Основний результат та приклад. Нас зацікавили питання – коли множина розв’язків задачі про найкоротший шлях містить більше за один елемент, чи має зміст задача відшукання серед них таких, що задовольняють додатковому критерію якості? Для дослідження нами був розроблений і протестований програмний продукт, який дозволяє вводити параметри мережі, зберігати мережі для подальшого використання, редагувати їх на етапі використання, здійснювати візуалізацію мереж та множину розв’язків послідовних оптимізаційних задач. У програмній реалізації математична модель представлена орієнтованим графом (𝐼 ), де кожній дузі 𝑢 ( ) присвоєно два атрибути: довжина wіj та вартість використання cіj. Досліджувалися задачі: 1) на заданій мережі відшукати множину найкоротших шляхів і вибрати серед них ті, вартість використання яких найменша; 2) на заданій мережі відшукати множину шляхів, вартість використання яких найменша і вибрати серед них найкоротші. Алгоритмічна логіка реалізована за допомогою наступних функцій:  find_minty_paths(graph, start, end): знаходить усі прості шляхи між вершинами start та end шляхом повного перебору.  minty_shortest_paths(graph, start, end): зі списку всіх шляхів, отриманих попередньою функцією, відбирає ті, що мають мінімальну довжину. Пошук мінімуму здійснюється за критерієм: min ( ∑(i,j) path wij )  minty_cheapest_paths(graph, start, end): відбирає шляхи з мінімальною сумарною вартістю за критерієм: min ( ∑(i,j) path cij )  minty_cheapest_among_shortest(graph, start, end): реалізує багатокритеріальний пошук, знаходячи найдешевші шляхи серед множини найкоротших.  minty_shortest_among_cheapest(graph, start, end): знаходить найкоротші шляхи серед множини найдешевших. Такий підхід дозволяє не лише знаходити оптимальні маршрути за одним критерієм, але й аналізувати компромісні рішення, що є важливим для практичних задач логістики та планування. ПЕРЕЛІК ЛІТЕРАТУРИ 1. Руснак М. А. Математичне програмування : навч. посіб. / уклад.: М.А.Руснак, М.П. Коцур. Чернівці : Чернівец. нац. ун-т ім. Ю. Федьковича, 2025. 200 с. 2. Мінті Дж. Алгоритм пошуку шляхів у графі // Теорія графів та комбінаторна оптимізація. – 1970. – С. 45–53. УДК 004:631 МОСЯНДЗ О.М., ФРАТАВЧАН В.Г. Чернівецький національний університет імені Юрія Федьковича (Україна) ВІЗУАЛЬНИЙ МОНІТОРИНГ ХРОНОЛОГІЇ ПРИКОРДОННИХ ПРАВОПОРУШЕНЬ Реферат. Розглядається програмна розробка для візуалізації результатів аналізу журналів та звітів прикордонної служби з динаміки порушень правил перетину державного кордону в пунктах пропуску та незаконного його перетину поза пунктами пропуску. Проводиться систематизація та аналіз звітних даних в межах окремого прикордонного пункту, окремих «ПРОБЛЕМИ ІНФОРМАТИКИ ТА КОМП’ЮТЕРНОЇ ТЕХНІКИ» (ПІКТ – 2025) Праці XIV Міжнародної науково-практичної конференції ЧЕРНІВЦІ 13 – 15 ЛИСТОПАДА, 2025 Папір офсетний. Формат 60х84/8. Ум. друк. арк. 23,71. Вид. №25-15. Зам. № 37. Тираж 75 прим. Видавець та виготівник: ПВКФ «Технодрук» Свідоцтво суб’єкта видавничої справи ДК №1841 від 10.06.2004 р. 58000, м. Чернівці, вул. І. Франка, 20, оф.18, тел. (0372) 55-05-85 Видання містить праці учасників XIV Міжнародної науково-практичної конференції «Проблеми інформатики та комп’ютерної техніки» (ПІКТ–2025). Редакційна колегія: Остапов С.Е., Руснак М.А., Лазорик В.В. Комп’ютерний набір та верстка: Руснак О.В. Відповідальний за випуск: Остапов С.Е.