Ramazonov asadbekning Diskret tuzilmalari fanidan bajargan mustaqil ishi

Tarmoq va chegara usuli yordamida masalani yechishga misol
Sayohatchi sotuvchi muammosi uchun dastlabki ma’lumotlar .
Shaharlar soni n = 5. Shaharlarni bog’lovchi yo’l tarmog’ining grafigi, halqalarsiz to’liq, yo’naltirilgan, assimetrik oddiy, 5 × 5 o’lchamdagi C matritsasi [5] tomonidan berilgan , grafik yoylar og’irlikda; matritsaning satrlari chiqish nuqtalariga, ustunlar – kelish nuqtalariga to’g’ri keladi. AQSh bildirmoq bo’lsin dastlabki (boshlang’ich) qiymati bilan belgisi bilan ob’ektiv funktsiyasi bog’lab pasaytirish Q * = ∞ - NGCP; u bilan joriy reytinglarni solishtirish uchun foydalaniladi. To’liq marshrutni shakllantirish va uning uchun DFni hisoblash mumkin bo’lganda, Q * = ∞ qiymati yangisiga almashtiriladi, u hisoblangan DFga aylanadi, u bilan boshqa marshrutlar qo’shimcha ravishda taqqoslanadi va baholanadi, H c = 1 + 5 + 6 + 7 + 8 + 3 + 1 = 31 – MQXF qiymati (smeta) xarajat matritsasi satrlari va ustunlari konstantalari yig’indisi sifatida olinadi.Yonlarning og’irligi (yoy bo’ylab harakatlanish qiymati) C ij elementlari bilan beriladi . kvadrat matritsa. Ushbu xarajatlar matritsasi S [5] masaladagi o’zgarishlarning asosiy ob’ekti hisoblanadi. C [5] matritsasining barcha diagonal elementlari T yo’nalishiga (dumaloqda) kiritilmasligi kerak , chunki mos keladigan yoylar grafik halqalardir va shuning uchun ularga juda katta xarajatlar ( ∞ ) tayinlanadi . Hujayralardagi qolgan qiymatlar quyidagi natural sonlar bilan ketma-ket to’ldiriladi (misolda, S 11 = 1 katakchadan soat yo’nalishi bo’yicha spiral.matritsaning markaziga). Marshrutni topish bo’yicha ishlar yo’llarning doimiy grafigida (cho’qqilari va yoylari bilan) va echimlarni topish uchun ketma-ket o’sib boruvchi grafik daraxtida (tugun va novdalar bilan) amalga oshiriladi. X nomi algoritmning har bir bosqichida yechim qidirish daraxtining joriy tuguniga, Y nomi esa turga kiritilgan shoxlanishning tugunlari-natijasiga, Y nomi esa tayinlanadi. Kiritilgan emas salbiy tugun, T safari (yo’l).

Ko’p bosqichli qarorlar daraxtini qidirish algoritmi
Muammoni muvaffaqiyatli hal qilish har bir satrda va C [5] matritsasining har bir ustunida ularning “diagonal” joylashuvi bilan kamida bitta nol mavjudligini ta’minlash orqali erishiladi . Bunday holda, marshrut nolga ega bo’lgan katakchalar orqali yotqizilishi mumkin va marshrutning narxi eng kam bo’ladi. Bundan tashqari, matritsadagi nollarning bunday pozitsiyasi C [5] matritsasini va uning o’lchamlarini xiralashgan C [5] = 2 × ga kamaytiradigan o’zgarishlarni kamaytirish protsedurasini takroran qo’llash orqali ta’minlanishini ko’ramiz. 2 . Matritsa 2 × 2 o’lchamga yetganda, u marshrutga kiritilgan cho’qqilarning aniq ta’rifini beradi. Xususiyatlari ( d i ,d j ) d i qatordagi yo’llar grafigining yoylari va o’zgaruvchan xarajatlar matritsasining d j ustunidagi S [n] . X daraxt tugunlari “ijobiy” va “salbiy” bo’linadi. Qaror daraxtidagi osilgan “kechiktirilgan” tugunlar (barglar) to’plami B belgisi bilan belgilanadi va maqsad funktsiyasining pastki chegarasining boshlang’ich qiymati Q * = ∞ bilan belgilanadi. Algoritm qadamlari ikki xil: oddiy va kutilayotgan tugunga qaytish bilan; ikkinchi tur “orqaga kuzatish” protsedurasini amalga oshiradi: