Algoritm va uning intuitiv, formal va kibernetik ta’riflari

Graflarda optimallashtirish masalalari. Deykstr algoritmi
Amaliyotda uchraydigan ko‗plab masalalarda marshrut uzunligi maksimallashtirilishi yoki minimallashtirilishi talab etiladi. Shunday masalalardan biriga, aniqrogʻi, kommivoyajer masalasiga Gamilton graflari bilan shugʻullanganda duch kelamiz. G(V,U) oriyentirlangan graf berilgan bo‗lsin, bu yerda V {1,2,...,m}. G grafning biror s uchidan boshqa t V uchiga boruvchi yo‗llar orasida uzunligi eng kichik bo‗lganini topish masalasi bilan shugʻullanamiz. Bu masalani minimal uzunlikka ega yo„l haqidagi masala deb ataymiz. Quyida bu masalaning umumlashmasi hisoblangan masalani qarab, uni ham o‗sha nom bilan ataymiz. Grafdagi (i, j) yoyning uzunligini cij bilan belgilab, matritsa berilgan deb hisoblaymiz. Yuqorida ta‘kidlaganlarimizga ko‗ra, C matritsaning cij elementlari orasida manfiylari yoki nolga tenglari ham bo‗lishlari mumkin. Agar grafda biror i uchdan chiqib j uchga kirruvchi yoy mavjud bo‗lmasa, u holda bu yoyning uzunligini cheksiz katta deb qabul qilamiz (cij ). Bundan tashqari, G grafda umumiy uzunligi manfiy bo‗lgan sikl mavjud emas deb hisoblaymiz, chunki aks holda uzunligi eng kichik bo‗lgan yo‗l mavjud emas. Minimal uzunlikka ega yo‗l haqidagi masalani hal etish usullari orasida Deykstra6 tomonidan taklif etilgan algoritm ko‗p qo‗llaniladi. Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul qilamiz) grafdagi ixtiyoriy k uchgacha (bu uchni oxirgi uch deb hisoblaymiz) eng qisqa uzunlikka ega yo‗lni topish imkonini beruvchi Deykstra algoritmi keltirilgan. Dastlabki qadam. Manbaga (1 belgili uchga) qiymatni mos qo‗yib, bu uchni dastlab deb qabul qilingan R to‗plamga kiritamiz: R deb olamiz.
Yo’naltirilgan, tartiblangan va binar daraxtlar.
Daraxt - bu bogʻlangan asiklik graf, ya’ni sikllar yoʻq va uchlar juftligi orasida bitta yoʻl bor (29-rasm). Kirishning nol darajasiga ega boʻlgan uch daraxtning ildizi, chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi. Ulanish har qanday uchlar juftligi oʻrtasida marshrut mavjudligini anglatadi, aylanuvchanlik sikllar yoʻqligini anglatadi. Demak, xususan, shundan kelib chiqadiki, daraxtdagi qirralarning soni uchlar sonidan bitta kamroq va har qanday uchlar juftlari orasida bitta va faqat bitta yoʻl bor. Oʻrmon – juda koʻp daraxtlardir. Yoʻnaltirilgan (oriyentirlangan) daraxt - bu faqat bitta ertikal kirish nol darajasiga ega boʻlgan (boshqa yoylar unga olib kelmaydigan), boshqa uchlarning kirish darajasi 1 boʻlgan siklik orgraf (sikllarni oʻz ichiga olmaydigan yoʻnaltirilgan graf). Daraxtning asosiy tushunchalari Ildiz tuguni - daraxtning eng yuqori tuguni (18-rasmdagi 8-tugun ). Ildiz – ixtiyoriy tanlab olingan uchlardan biri. Barg yoki terminal tuguni – avlodi mavjud boʻlmagan tugun (18-rasmdagi 1, 4, 7, 13 tugunlari). Ichki tugun - bu daraxtga avlodi mavjud boʻlgan har qanday tugun va shuning uchun barg tuguni emas (18-rasmda 3, 6, 10, 14)Uchning darajasi - unga tushgan qirralarning soni.