Ramazonov asadbekning Diskret tuzilmalari fanidan bajargan mustaqil ishi

Sayohatchi sotuvchi muammosini hal qilish algoritmining har bir bosqichida quyidagilar bajariladi (aniqlanadi):
Uning har bir satri va ustunida nol elementlarni olish uchun C [i, j] matritsasini qisqartirish ;
Matritsada nol qiymatga ega bo’lgan S hujayralar to’plamini va ularning xarakteristikalari d i , d j , ∑ ijni tekis jadval ko’rinishida shakllantirish;
Maks ∑ ij hisoblab chiqiladi va marshrutga kiritilmagan max bo’lgan katak ( k, l ) aniqlanadi ;
Matritsa o’zgartirildi: katakning k – qatori va l – ustuni ( k, l ) matritsadan chiqariladi ;
NGCP baholari yechim qidirish daraxtining ijobiy va salbiy tugunlari uchun hisoblanadi;
Marshrut afzal (pastki) bahoga ega elementni ( k, l ) o‘z ichiga oladi ō ( k, l ) NGTSF
Hisob-kitoblar bir-biri bilan taqqoslanadi, dastlabki Q * va joriy qadamda hisoblangan H ;
Matritsaning o’lchami dim S [n] hisoblab chiqiladi va bu o’lchamning dim 2 × 2 bilan tengligi tekshiriladi ;
Qaror daraxtining osilgan tugunlarining B to’plami , ularning NSCF bo’yicha baholari bilan shakllanadi.
Keyingi bosqich uchun yechim qidirish daraxtining bir qismi berilgan.
Takroriy bosqichlar: T turningshakllanishi T = { (a, b) (c,) yoylari ketma-ketligi sifatida hosil bo’lgan T yo’liga kiritish uchun yo’l grafigining 1-yoyi (k, l) ni tanlashdan boshlanadi. D) (ef) (hg). .... }.
QADAM 1. Dastlabki C [n] matritsasini qisqartirish tartibi (undagi nollarni olish). Har bir i- chi qatorda S [n] eng kichik elementni toping va uni chiziqning barcha elementlaridan ayiring. Biz matritsaning barcha qatorlaridan o’tamiz. Bunday o’zgartirilgan matritsa uchun har bir j – ustunda yana eng kichik elementni topamiz va uni har bir j – ustunning barcha elementlaridan ayiramiz. Biz barcha ustunlardan o’tamiz. Topilgan eng kichik elementlar qator va ustunlar (matritsa chiziqlari) konstantalari deb ataladi va h i , i = 1 (1) 2n ni bildiradi. Doimiy H cbutun matritsaning qisqarishi S [n] chiziq konstantalarining yig’indisi ∑ h i deyiladi . Bu H c (C [5] ) = ∑ h i = 1 + 5 + 6 + 7 + 8 + 3 + 1 = 31 yig’indisi muammoning barcha yechimlarining NGCP ning taxminidir. Joriy matritsalarni S [n] algoritm bosqichlarida qisqartirish faqat uning ba’zi qatorlari va/yoki ustunlarida nol bo’lmagan taqdirdagina amalga oshiriladi va yangi konstantalar faqat shunday satrlar uchun aniqlanadi.