Аналіз і застосування алгоритмів вибору оптимального транспортного маршруту

Abstract

Сучасні інноваційні технології автоматизації різних сфер людської діяльності відкрили унікальні можливості для прогнозування та імітації складних систем, вивчення їх характеристик і управління ними в умовах обмеженості часу, ресурсів або інформації. Формалізація даних є необхідною для математичного аналізу будь-якої системи, що дозволяє побудувати математичну платформу. Використання математичних моделей для аналізу ймовірно є одним з найбільш ефективних способів дослідження складних систем і вирішення важливих практичних завдань управління. Графи є універсальною моделлю для представлення об’єктів та процесів у різних сферах, таких як фізика, медицина, теорія ймовірностей, виробництво обчислювальних машин, електроніка, механіка, фізіологія, радіозв’язок, авіація, картографія, графіка, антропологія та багато інших. Зазвичай, графи використовуються для вирішення задач таких як пошук найкоротшого шляху, ймовірності, топологічного планування, або кластеризації. Один з піонерів у математичному підході до теорії графів був Леонард Ейлер, який, розглядаючи задачу про сім мостів, довів, що неможливо пройти всі сім міських шляхопроводів та повернутися до початкової точки, перетнувши кожен міст лише один раз. Через приблизно 100 років нові дослідження в галузі електромереж, кристалографії, хімії та суміжних галузей привнесли нові ідеї в теорію графів. На сьогодні графи застосовуються не лише для отримання результату на зображенні різних процесів. Наприклад, при перегляді графа, який відображає мережу шляхів між містами держави, можна зосередитися на маршруті від пункту 1 до пункту 2. Проте, коли маємо безліч маршрутів, хочемо вибрати оптимальний або найбезпечніший. Для розв’язання цієї проблеми потрібні розрахунки з використанням графів. В таких обставинах виявляється необхідність у використанні потужних цифрових технологій. На сьогодні графи охоплюють різноманітні аспекти та активно розвиваються у багатьох напрямках. Особливий інтерес становить питання про знаходження найкоротшого шляху. Під час аналізу алгоритмів та методів маршрутизації важливо звернути увагу на ті, що відносяться до цієї проблеми. Математичне тлумачення графів відображається у формалізації об’єктів та зв’язків до складних випадкових множин.