Raqamli texnologiyalar

Eng qisqa yo’llarni masalalarning turlari.
Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G graf turlarni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa qirralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir.
Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida, turdagi har bir uchlar juftliklari orasida va boshqalar.
Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar.
Eng qisqa masofani topish masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.

Tegishli muammolar.
Deykstra haqiqiy algoritmining funksiyalari turli modifikatsiyalar bilan kengaytirilishi mumkin. Masalan, ba'zida matematik jihatdan maqbul bo'lmagan yechimlarni taqdim etish maqsadga muvofiqdir. Kamdan-kamroq optimal yechimlar topilgan ro'yxatini olish uchun maqbul yechim avval hisoblab chiqilgan. Optimal Graf chizmasida ko'rinadigan bitta qirrali grafadan chiqariladi va bu yangi grafikka optimal yechim hisoblanadi. Dastlabki Graf chizmasida har bir qirrasi o'z navbatida bekor qilinadi va yangi qisqa yo'l aniqlanadi. Keyinchalik, ikkilamchi Graf chizmasida birinchi optimal Graf chizmasida baholanadi va taqdim etiladi. Deykstraning algoritmi, odatda, ulanish-davlat marshrutlash protokollari, OSPF va IS-IS eng keng tarqalgan bo'lib turadigan ish printsipi hisoblanadi. Deykstra algoritmidan farqli o'laroq, Bellman-Ford algoritmi gorizontal manba vertolyotidan salbiy siklga ega bo'lmasa, salbiy qirrali grafika bilan ishlatilishi mumkin. Bunday aylanishlarning mavjudligi eng kichik yo'l yo'qligini anglatadi, chunki har bir siklda aylanish jarayonida umumiy og'irlik pastga aylanadi. Deykstra algoritmini salbiy og'irlik chekkalarini Bellman-Ford algoritmiga (salbiy qirralarni olib tashlash va salbiy davrlarni aniqlash) birlashtirish yo'li bilan moslashtirish mumkin, bunday algoritm Jonsonning algoritmi deb ataladi.
A * algoritmi Deykstra ning algoritmini umumlashtirish, agar maqsadga "masofadan" pastroq bo'lgan cheklovni ta'minlaydigan qo'shimcha ma'lumot mavjud bo'lsa, o'rganilishi kerak bo'lgan sub graf o'lchamini qisqartiradi. Ushbu yondashuv chiziqli dasturlash nuqtai nazaridan qaralishi mumkin: eng qisqa yo'llarni hisoblash uchun tabiiy chiziqli dastur mavjud va uning ikkilamchi chiziqli dasturiga yechimlarni kiritish mumkin va ular faqat izchil sezgirlikni shakllantirsa (taxminan, so'zma-so'z konventsiyalari farqlanadi) adabiyotda joydan joygacha). Ushbu mumkin bo'lgan ikkilangan / izchil topilmalar salbiy bo'lmagan past narxni belgilaydi va A * bu Deykstra algoritmini ushbu kam xarajatlar bilan boshqaradi. Agar ikkilamchi qabul qilishning zaif holatini qondirsa, A * o'rniga Bellman-Ford algoritmiga ko'proq mos keladi.

Deykstraning algoritmining asoslanishi jarayon Primet algoritmida ishlatiladigan ochko'z jarayonga o'xshaydi. Primning maqsadi grafadagi barcha tugunlarni bir-biriga bog'lovchi minimal spaning daraxtni topishdir; Deykstra faqat ikkita tugun bilan bog'liq. Primer, yo'lning umumiy og'irligini boshlang'ich tugunidan, faqatgina individual qirralarni baholaydi. Kichkina birinchi qidiruvni Deykstra algoritmini taqqoslanmagan graflarda ko'rib chiqish mumkin, bu erda navbatdagi navbat FIFO navbatiga ziyon beradi. Tez marshing usuli Deykstra algoritmining uchburchak meshidagi geodezial masofani hisoblaydigan uzluksiz versiyasidir