ЦИФРОВІ ІНСТРУМЕНТИ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПОШУКУ НАЙКОРОТШОГО ШЛЯХУ - Наукові конференції
Головна
UA PL EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

Рік заснування видання - 2011

ЦИФРОВІ ІНСТРУМЕНТИ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПОШУКУ НАЙКОРОТШОГО ШЛЯХУ

14.05.2025 10:46

[1. Інформаційні системи і технології]

Автор: Витвицька Оксана Миколаївна, кандидат економічних наук, доцент кафедри фізико-математичних наук, Івано-Франківський національний технічний університет нафти і газу, Івано-Франківськ



Вступ

У сучасних умовах цифрової трансформації освіти, науки та виробництва особливого значення набуває використання прикладних програмних засобів для розв’язання класичних задач математичного моделювання. Однією з таких задач є задача пошуку найкоротшого шляху, яка широко застосовується у логістиці, транспортному плануванні, комп’ютерних мережах та інших сферах. Ефективне розв’язання цієї задачі вимагає не лише знань алгоритмічних підходів (алгоритм Дейкстри, Беллмана-Форда, Флойда-Уоршелла, A*, тощо), а й володіння сучасними цифровими інструментами, які дозволяють автоматизувати обчислення, візуалізувати процес і адаптувати рішення до конкретних умов [1].

Результати дослідження.

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

Класичні алгоритми для розв’язання цієї задачі: алгоритм Дейкстри (для графів без від’ємних ваг) [2]; алгоритм Беллмана-Форда (допускає від’ємні ваги); алгоритм Флойда-Уоршелла (знаходить найкоротші шляхи між усіма парами вершин); алгоритм A* (пошук із евристикою).

Цифрові засоби для реалізації алгоритму пошуку найкоротшого шляху:

1. Microsoft Excel (надбудова «Розв’язувач») – дозволяє моделювати граф через матрицю суміжності та за допомогою надбудови "Розв’язувач" (Solver) реалізувати пошук найкоротшого шляху як задачу лінійного програмування. Такий підхід особливо корисний у навчальному середовищі для демонстрації логіки задачі. Окрім того, використання надбудови "Розв’язувач" не вимагає знань мов програмування, що робить його доступним інструментом для широкого кола користувачів.

2. Веб-ресурс Visualgo.net пропонує інтерактивну візуалізацію алгоритмів, зокрема Дейкстри, Белмана-Форда та інших. Користувач має змогу створити власний граф, задати ваги, спостерігати покрокову роботу алгоритму. Visualgo ефективно використовується як дидактичний засіб для формування алгоритмічного мислення.

3. Python (бібліотеки NetworkX, matplotlib) – є гнучким інструментом для моделювання графів. Зокрема, бібліотека NetworkX надає функціонал для створення графів, призначення ваг, а також реалізації пошукових алгоритмів. Комбінація з matplotlib дозволяє будувати графічні представлення мережі та візуалізувати маршрути. Цей інструмент є зручним для дослідницьких проєктів та глибшого аналізу.

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

5. Wolfram Alpha – онлайн-сервіс, який підтримує аналітичне розв’язання задач оптимізації, зокрема і пошук найкоротших шляхів, пропонує функції візуалізації та адаптації до змін у реальному часі.

Порівняльний аналіз цифрових інструментів, що використовуються для розв’язання задачі пошуку найкоротшого шляху, засвідчив доцільність вибору того чи іншого застосунку залежно від цілей користувача та освітнього чи практичного контексту. Visualgo є оптимальним засобом для візуалізації алгоритмів (зокрема Дейкстри), формування алгоритмічного мислення та покрокового аналізу обчислень. Excel з надбудовою Solver зручний для моделювання задач у табличній формі, особливо у випадках економічних або логістичних сценаріїв. Python із бібліотекою NetworkX забезпечує гнучкість і масштабованість у професійному програмному середовищі. GeoGebra, хоча і менш функціональний для складних мереж, може бути ефективним у початковому навчанні моделювання структур, наближених до графів. Вибір інструменту має базуватися на освітньому рівні здобувачів, меті моделювання та необхідному рівні візуалізації або програмного контролю.

Висновки

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

Література

1. Інтеграція цифрових технологій в освітній процес: виклики та перспективи [Електронний ресурс] : монографія / Саєнко Н. С., Голуб Т. П., Лавриш Ю. Е., Лук’яненко В. В., Литовченко І. М. – Київ: Центр учбової літератури, 2022. – 204 с. https://ela.kpi.ua/handle/123456789/54226

2. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90



Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Інші наукові праці даної секції

Конференції

Конференції 2025

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення