Amaliy matematika va informatika” kafedrasi “algoritmlar nazariyasi” fanidan

II-BOB LEVIT ALGORITMI HAQIDA

Levit algoritmi - bu grafikning uchidan boshqalariga eng yaqin masofani topadigan grafiklar algoritmi. Algoritm, shuningdek, salbiy og'irlikdagi chiziqlar uchun ham ishlaydi. Algoritm dasturlash va texnologiyada keng qo'llaniladi. Levit algoritmi berilgan vektordan s boshqalargacha bo'lgan masofani topadi. Salbiy sikl bo'lmasa, og'irlik qirralari bilan ishlashga imkon beradi. Algoritm cheklangan vaqt davomida ishlaydi Umumiylikni yo'qotmasdan, biz grafik ulangan deb taxmin qilamiz. Keyin barcha vertikal qismlar M0 da paydo bo'lganda algoritm tugaydi. Dastlabki grafikda salbiy tsikllar bo'lmaganligi sababli, har bir verteks uchun eng qisqa yo'l bor. Shunda har bir verteksgacha bo'lgan masofani atigi bir necha marta qisqartirish mumkin va natijada vertex M0 dan M1 ga ham sonli marta o'tkaziladi. Boshqa tomondan, har bir qadamda, hozirgi vertex M0 ga joylashtirilishi kafolatlanadi. Shunda barcha vertikal qismlar M0 sonli bosqichlarda bo'ladi.

Levit algoritmining ommabop va maxsus grafiklarda samarali ishlashi keltirilgan. Uning "kanonik" versiyadan farqi shundaki, elementni oxiriga emas, balki boshida {\ displaystyle M1} M1 navbatiga qo'shish. Bu sizga ba'zi grafikalarda daromad olishga imkon beradi, ammo eng yomon holatda eksponent ish vaqtiga olib keladi.

Dijkstra usuli bilan taqqoslaganda, Levit usuli ba'zi vertikallarni qayta-qayta qayta ishlash kerakligini yo'qotadi va o'rnatilgan M1-dan vertikallarni qo'shish va chiqarib tashlashning sodda algoritmlarida g'alaba qozonadi. Tajribalar shuni ko'rsatadiki, "geometrik" kelib chiqishi bo'lgan grafikalar uchun, ya'ni transport tarmoqlari va real masofalar asosida qurilgan grafikalar uchun Levit usuli eng tezkor hisoblanadi. U dastur hajmini yutadi.
Levit usuli, shuningdek, Dijkstra usulidan afzalliklarga ega, chunki u yoyning uzunligi holatida qo'llanilishi mumkin (oxir-oqibat, "yoy uzunligi" bu bizga haqiqat bilan foydali aloqalarni beradigan ism). Agar l (u) qiymatlari har doim ham ijobiy emas deb faraz qilsak, eng qisqa yo'l muammosini hal qilish ancha murakkab. Birinchi qiyinchilik shundaki, ma'lum bir yoygacha hisoblangan masofani aniqlash uchun Dijkstra usulining oddiy qoidasi yo'qoladi. Ushbu qiyinchilikni, keyinchalik bilib olamiz, garchi usulning samaradorligi biroz pasaygan bo'lsa ham (ushbu vektorga olib boruvchi barcha yoylar tekshirilishi kerak).

Ikkinchi qiyinchilik yanada jiddiyroq: grafikadagi salbiy uzunliklar uchun yoylarning uzunliklarining manfiy yig'indisi bo'lgan konturlar bo'lishi mumkin (biz bunday konturlarni “manfiy” deymiz). Yo'lga salbiy yo'lni qo'shish ob'ektiv funktsiyaning qiymatini pasaytiradi va biz qo'shadigan salbiy yo'l qancha ko'p bo'lsa, shuncha yaxshi bo'ladi. Minimal darajadagi cheksiz pasayishdan xalos bo'lishning iloji yo'q, ammo qiyin vaziyatdan chiqishning ikkita yo'li bor (albatta, chiqish yo'lini tanlash bizga bog'liq emas, ammo hal qilinishi kerak bo'lgan amaliy muammoga bog'liq).Yo'llarni yo'lga kiritishni taqiqlang, ya'ni faqat oddiy yo'llarni ko'rib chiqing, ammo bunday taqiq vazifani juda qiyinlashtiradi. Salbiy ko'chadan bo'lsa, muammoning echimi yo'q deb hisoblang va salbiy halqa bo'lmagan holatlarda muammoni hal qilish bilan cheklanamiz. Bunday holda, Levit usuli kerakli maqbul echimni beradi va ba'zi bir o'zgartirishlar bilan salbiy konturlarni "qo'lga olish" imkoniyatini beradi.