Mustaqil ish 7 Topshirdi: absamatov j

bo'lgan muammodan farqli o'laroq , eng uzun yo'l muammosi NP-qiyin va muammoning qaror versiyasi bo'lib, u kamida berilgan yo'l bor-yo'qligini so'raydi. uzunligi, NP-to'liq. Bu shuni anglatadiki, P = NP bo'lmasa , qaror masalasini ixtiyoriy grafiklar uchun polinom vaqtida hal qilib bo'lmaydi . Kuchli qattiqligi natijalar ham u uchun qiyin ekanligini ko'rsatib ma'lum yondashadi . Biroq, u yo'naltirilgan asiklik grafiklar uchun chiziqli vaqt yechimiga ega bo'lib , u rejalashtirish muammolarida muhim yo'lni topishda muhim ilovalarga ega . 1-misol. 1-shaklda tasvirlangan orgrafda oltita uch va o'n bitta yoy bo'lib, har bir yoy uzunligi uning yoniga yozilgan. Ko`rinib turibdiki, berilgan grafda manfiy uzunlikka ega (5,3) yoy ham bor. Isbotlash mumkinki, bu grafda umumiy uzunligi manfiy bolgan sikl mavjud emas.

Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga eng qisqa uzunlikka ega yo’lni topish bilan shug‘ullanamiz. Dastlabki qadam. Manbaga (I belgili uchga) ei=0 qiymatm mos qo'yamiz va R={1} to`plamga ega bo'lamiz. Shuning uchun. 7r.v\ R.{ 2 ,3 ,4,5,6} be' ladi.Umumiy qadam. 1-iteratsiya. R={1} va bo‘lgani uchun boshlang‘ich uchi R to`plamga tegishli, oxirgi uchi esa to`plam elementi bo`lgan barcha yoylar to`plami ga ega bo`lamiz. (R, ) to`plamga tegishli bo`lgan har bir yoy uchun ning qiymatlarini topamiz:

(1,2) yoy uchun

(1,3) yoy uchun

(1,4) yoy uchun

Bu , va miqdorlar orasida eng kichigi bo`lgani uchun (1,2) yoyni ajratamiz. (2-shaklda bu yoy qalin chiziq bilan belgilangan) va 2 belgili uchga qiymatni mos qo`yamiz. Algoritmga ko`ra 2 uchni to`plamdan chiqarib, R to`plamga kiritamiz. Natijada R={1,2} va ={3,4,5,6} to`plamlarga ega bo`lamiz.

Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga eng qisqa uzunlikka ega yo’lni topish bilan shug‘ullanamiz. Dastlabki qadam. Manbaga (I belgili uchga) ei=0 qiymatm mos qo'yamiz va R={1} to`plamga ega bo'lamiz. Shuning uchun. 7r.v\ R.{ 2 ,3 ,4,5,6} be' ladi.Umumiy qadam. 1-iteratsiya. R={1} va bo‘lgani uchun boshlang‘ich uchi R to`plamga tegishli, oxirgi uchi esa to`plam elementi bo`lgan barcha yoylar to`plami ga ega bo`lamiz. (R, ) to`plamga tegishli bo`lgan har bir yoy uchun ning qiymatlarini topamiz: