Grafdagi eng qisqa masofani topish algoritmi yaxshilandi

Gandinagar Hindiston texnologiya instituti dotsenti Manoj Gupta grafdagi barcha juftliklar orasida eng qisqa yo'llarni qidirish algoritmini sezilarli darajada yaxshiladi. FOCS 2025 simpoziumida e'lon qilingan ushbu ilmiy natija 1996 yildan beri ilk bor 2-yaqinlashuv kafolatlanadigan chegarani o'zgartirdi. Endilikda masofani baholash real qiymatdan ko'pi bilan ikki baravar farq qilishi nafaqat uzoq, balki bir-biriga juda yaqin bo'lgan tarmoq tugunlari uchun ham to'liq kafolatlanadi.

• 1996 yildan beri o'zgarmagan klassik APSP usuli sezilarli darajada yaxshilandi.
• Yangi yondashuv yaqin nuqtalar uchun ham 2-yaqinlashuv kafolatini ta'minlaydi.
• Hisoblash murakkabligi oshmadi, algoritm avvalgidek tez ishlaydi.

1996 yilgi usulning cheklovlari va muammolari

1996 yilda tadqiqotchilar Dor, Halperin va Svik barcha yo'llarni birma-bir tekshirmasdan, kichik miqyosdagi orientir nuqtalar yordamida uzun masofalarni tezda baholash usulini taklif qilishgan edi. Biroq yaqin nuqtalar uchun bu usul ko'pincha xato berar edi, chunki orientirlar eng qisqa birikmadan uzoqda joylashib qolardi. Natijada algoritm haqiqiy ikki qadam o'rniga besh qadamdan iborat yo'lni ko'rsatib, ikki baravar chegarasi shartini buzardi.

Ko'p darajali tarmoq va yangi yondashuv

Manoj Gupta orientirlarni tanlash usulini tubdan qayta ko'rib chiqdi va yagona qatlam o'rniga tarmoqning ko'p darajali taqdimotini tashkil qildi. Bu bir nechta miqyosdagi aloqalarni bir vaqtning o'zida tahlil qilish imkonini berdi. Natijada eski usul e'tibordan chetda qoldirgan qisqa yo'llar endi yo'qotilmaydi va hisoblash tezligi pasaymagan holda aniqlik kafolati kengaytirildi.

Algoritmik murakkablik va tarmoqlarni tahlil qilish

Ushbu natijaning ahamiyati faqat navigatsiya ilovalari bilan cheklanib qolmaydi. APSP vazifasi transport tizimlari, telekommunikatsiya tarmoqlari hamda oqsillar o'zaro ta'siridan tortib neyron aloqalarigacha bo'lgan biologik tuzilmalarni tahlil qilishning asosida yotadi. Katta graflarda aniq hisob-kitob qilish kub vaqtni talab qiladi, shuning uchun tezlik va nazorat qilinadigan aniqlikni birlashtiruvchi yaqinlashuv usullari juda muhimdir.

Nazariy ahamiyati va kelajakdagi istiqbollar

Garchi ushbu ish asosan nazariy xarakterga ega bo'lib, xarita servislariga to'g'ridan-to'g'ri joriy etilmasa-da, u kelajakda o'sib borayotgan tarmoqlarni samarali qayta ishlash imkonini beruvchi usullarning matematik poydevorini mustahkamlaydi. Qariyb o'n yilliklar davomida yechilmagan muammoning hal etilishi algoritm nazariyasidagi ulkan qadamdir.