Ramazonov asadbekning Diskret tuzilmalari fanidan bajargan mustaqil ishi

Quyidagi jadvallar vazifa matritsasini qisqartirish bo’yicha yo’l xaritasi,
harakatlar va ularning natijalarini ko’rsatadi.


Qisqartirilgan matritsa uchun satr konstantalari h i o’ngdagi ustunga, ustun konstantalari esa C matritsasidan pastdagi qatorga tayinlanadi [5] . Matritsaning qisqarish doimiysi (C [5] ) = ∑ h i = 31 bir marta hisoblanadi .
Q
ator va ustunli quyma konstantalari bilan xarajat matritsasi.

Endi barcha satrlar va ustunlardagi matritsaning kataklarida nollar va hatto bir nechta bo’lishi mumkin. Nollarni egallagan vaqtinchalik pozitsiyaga ko’ra , diagonal X rejasini tuzmang . Aks holda, bu reja muammoning yechimi bo’lar edi va tegishli marshrutning narxi asl C [5] matritsasining NGCP bahosiga teng bo’ladi , ya’ni H = 31 = 1 + 5 + 6 + 7 + 8 + 3 + 1 .

Nol hujayralar to’plamining S hosil bo’lishi va ularning xususiyatlari . Jadvalni yaratishdan oldin S = { (i, j) | C ij = 0 } nol katakchalar, asl xarajat matritsasi C [5] qisqartirildi .
Biz C [5] matritsasining kataklaridan nol qiymatga ega (yuqori qator S = { (i, j)} ) S to’plamini hosil qilamiz , d i qatorlardagi xarakteristikalar qiymatlarini aniqlaymiz va jadvalga kiritamiz. Va raundga qo’shilish uchun nomzod bo’lgan yoylarning d j ustunlarida . Qisqartirilgan C [5] matritsasining har bir C ij = 0 katakchasi uchun biz d i – qatordagi eng kichik qiymat va d j – ustundagi eng kichik qiymatni topamiz , C ij = 0 katakchaning o’zidan tashqari. Masalan, S jadvalining katakchasi uchun ( i, j ) = ( 2, 5 ) = 0 S [5] matritsasida bizda: 2-qatorda ( i = 2 ) kichikroq element C 2,1 = 6, yaʼni. D i = 6. ( j = 5 ) da beshinchi ustun uchta element nolga ega (yuqoridan tashqari), ya’ni. D j = 0. Har bir bosqichda hujayralar to’plami S = { (i, j) | C ij = 0 } xarajatlarning qisqartirilgan C [5] matritsasida – optimal turga birinchisini kiritish uchun ariza beruvchilar-yoylar to’plami. Jadvalni to’ldirishning umumiy qoidalariS shaklini olish
C
[5] matritsasining S katakchalari toʻplamida nol qiymatga ega boʻlgan ∑ ij = 6 = d i + d j yigʻindisida boshqalardan kattaroq boʻlgan katakchani topamiz . Bu katak argmax ∑ ij = (k, l) = (2, 5);

Jadval S = {(i, j)} nol kataklardan Cij = 0 birinchi bosqichning S [5] matritsasi.

Max ∑ ij ni hisoblang va marshrutga kiritilgan max bilan katakchani (k, l) aniqlang;

Bu qiymatlar, masalan, birinchi ustundagi ( 1,2 ) katak uchun ∑ ij = d i + d j = 0 + 2 = 2 yig’iladi. Va qisqartirilgan C matritsa uchun S dagi barcha nol hujayralar uchun [5] xuddi shunday qayta ishlanadi. Bunday ustun so’mdan orasida eng yirik hujayrali topilgan va hujayra ( k, l ) maksimal summasi mos ( max Σ ij = 6 ) bo’lgan jiddiy va argmax Σ ij = arg 6 = (k, l) = (2 5). Hujayra koordinatalari aniqlangandan so’ng C matritsasi o’zgartiriladi [5].
C matritsasining modifikatsiyasi [5] – k-qator va l- ustun matritsadan chiqariladi:
Ko’p bosqichli algoritmni amalga oshirish jarayonida muammoning dastlabki ma’lumotlari qayta ishlanadi, ishlov berishdan maqsad eng pastda, hududning yo’l xaritasini taqlid qiluvchi grafik cho’qqilarini bir marta kesib o’tish uchun marshrutni shakllantirishdir. Marshrutning narxi. Marshrut unga kiritiladigan grafik yoylarni ketma-ket tanlash orqali shakllantiriladi. Qarorlar daraxtining har bir keyingi novdasi ma’lum qoidalar-cheklovlarga ko’ra topiladi (tanlanadi) va muammoning barcha cheklovlari bajarilganda, yoy joriy marshrutga kiritiladi. Bundan tashqari, “orqa kuzatuv” deb ataladigan narsa amalga oshirilmoqda. Marshrut uzunligini oshirish maqsad funktsiyasining hisoblangan qiymatini nazorat qilish va uning avvalroq kechiktirilgan oraliq “keyinroqqa qoldirilgan” qiymatlaridan oshmasligi sharti bilan amalga oshiriladi. Agar CF bu qiymatdan oshsa, algoritm yechimni kechiktirish momentida yechim topish jarayonining (matritsasining) joriy holatini tiklab, shunday kechiktirilgan variantni davom ettirishga o’tadi (masalan, 4-bosqichda). Qarorlar daraxti orqali “yuqoriga” qaytarish harakati avvaldan kechiktirilgan variantga (tugun) amalga oshiriladi.
C matritsasini o’zgartiramiz [5]. K = 2 sonli qatorni va l = 5 sonli ustunni o’chirish ; xarajatlar matritsasining o’lchami o’zgardi va (5-1) × (5-1) = 4 × 4 ga teng bo’ldi ; Matritsadan chiziqlarni olib tashlashda nol qiymatga ega bo’lgan ba’zi hujayralar olib tashlanishi mumkin; ular yana qabul qilinishi kerak;
Loopning oldini olish, ya’ni. Biz katakchani ( p, q ) marshrutga keyingi tanlash va kiritishni taqiqlaymiz , bu erda q = k = 2, p = l = 5 va (l, k) = (5, 2) pozitsiyasida biz a kiritamiz . katta C pq = ∞ qiymati, uni tanlash va marshrutga kiritish taqiqlanadi. Ushbu harakatlar natijalari quyida C [4] o’ng matritsasida ko’rsatilgan.

O'zgartirilgan birinchi bosqich 4 × 4 xarajat matritsalari
4 × 4 matritsani kamaytirish uchun yangi doimiyni hisoblang, N = ∑h i = 4 + 2 = 6:
NGCP baholari yechim qidirish daraxtining ijobiy va salbiy tugunlari uchun hisoblanadi; Salbiy tugun uchun NGCPni hisoblash ō ( Y ) = ō ( 25 ) = ō (X) + ∑ ( kl) = 31 +6 = 37 va ijobiy tugun uchun NGCP ō (Y) = ō (25) hisoblash = ō (X) + H = 31 +6 = 37 ; hisoblash formulalari bir-biridan farq qiladi, ammo shunga qaramay, hisob-kitoblar ba’zan bir-biriga to’g’ri keladi; taxminlarni taqqoslash shuni ko’rsatadiki, bu vaziyatda ular tengdir. Qanday davom etish kerak, qaysi tugunni tanlash kerak? Biz marshrutni shakllantirganimiz uchun T , keyin biz unga musbat cho’qqini ( 2, 5 ) kiritamiz , ya’ni. Keyin T = { (2,5) (..)… }. Tarmoqlanish uchun tanlangan tugunga ekstremallik munosabatini o’rnatamiz (2, 5 ) yangi nom X = argmin { ō ( Y = (25) ) = 37, ō (Y = (25)) = 37} = ( 2, 5 ) yoki X = Y ( k, l ) = Y ( 2, 5) . Ushbu tugun yanada ko’proq tarmoqlanadi.

XULOSA.
Ushbu Kommivoyajer masalasi (sayohatchi sotuvchi) mustaqil ishini bajarishda Kommivoyajer masalasi haqida boshlang’ich tushunchalar, sayohatchi sotuvchi muammosining matematik modeli, sayohatchi sotuvchi muammosi uchun dastlabki ma’lumotlar va bunga doir misollar haqida ma’lumotlar berildi. Ushbu Kommivoyajer masalasini .

Foydalanilgan adabiyotlar.

1. 
   https://habr.com/ru/post/560468/
   
2. 
   https://hozir.org/ozbekiston-oliy-va-orta-maxsus-talim-vazirligi-samarqand-davla.html?page=2
   
3. 
   http://library.ziyonet.uz/uz/book/download/7230