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

Abstract

Розглянуто основні алгоритми пошуку найкоротших шляхів між кінцевими вузлами, на основі яких функціонують протоколи маршрутизації інформаційних мереж зв'язку. Розглянуто методи штучного інтелекту і теорії рішень, що застосовуються для пошуку найкоротших шляхів у мережах. Виконано порівняльний аналіз ефективності наступних алгоритмів пошуку найкоротшого шляху у ad hoc мережі: алгоритму Дейкстри, алгоритму Беллмана-Форда і алгоритму А*. Показано, що за рахунок вибору відповідної евристичної функції в алгоритмі A* вдається більше ніж у два рази скоротити час пошуку в порівнянні з алгоритмом Дейкстри.