Kompüter alimi 1996-cı ildən mövcud olan alqoritmin məhdudiyyətini aradan qaldırıb

Yeni alqoritm kompüter alimlərinin 1996-cı ildən bəri qarşılaşdığı bir məhdudiyyəti aradan qaldıraraq nəhəng şəbəkələrdə bir-birinə yaxın nöqtələr arasındakı məsafələri daha səmərəli hesablamağa imkan verir. Naviqasiya tətbiqləri adətən bir marşrutu — məsələn, oteldən hava limanına ən sürətli yolu — hesablamaqla kifayətlənir. Kompüter alimləri isə bundan daha böyük problemlə üzləşirlər: şəbəkədəki bütün mümkün nöqtə cütləri arasındakı ən qısa məsafəni hesablamaq.  Bütün cütlər üzrə ən qısa yollar (All-Pairs Shortest Paths — APSP) problemi kimi tanınan bu məsələ yalnız yol xəritələri ilə məhdudlaşmır. Qraf kompüterləri birləşdirən məlumat xətlərini, dəmir yolu ilə əlaqələndirilmiş stansiyaları, hüceyrə daxilində qarşılıqlı əlaqədə olan zülalları və ya beyində bir-biri ilə əlaqə saxlayan neyronları da modelləşdirə bilər. Bu sistemlərdə nöqtələr təpələr (vertices), onları birləşdirən əlaqələr isə tillər (edges) adlanır.

Şəbəkə böyüdükcə dəqiq hesablamaların aparılması daha çox hesablama resursu tələb edir. Sıx qraflar üçün ənənəvi metodlar kubik zaman mürəkkəbliyinə malik ola bilər. Bu o deməkdir ki, təpələrin sayı iki dəfə artırıldıqda görülməli işin həcmi təxminən səkkiz dəfə arta bilər. Üstəlik, nəticənin özü də olduqca böyükdür. n sayda təpəsi olan şəbəkədə məsafəsi hesablanmalı ola biləcək n² sıralanmış cüt mövcuddur. Məhz bu miqyas problemi alimləri təxmini alqoritmlər hazırlamağa sövq edib. Bu metodlar müəyyən dəqiqlikdən bir qədər güzəştə gedərək hesablama sürətini əhəmiyyətli dərəcədə artırır. Nəticə tam dəqiq olmur, lakin riyazi olaraq müəyyən edilmiş hədd daxilində qalır.

1996-cı ildə Dor, Halperin və Zwick mühüm bir metod təqdim etmişdilər. Bu metod demək olar ki, optimal vaxtda “2-yaxınlaşdırma” (2-approximation) nəticəsi verirdi.

Bu yanaşmada hesablanan məsafə həqiqi ən qısa məsafənin iki mislindən çox ola bilməz. Məsələn, iki məntəqə arasındakı real ən qısa məsafə 10 kilometrdirsə, alqoritmin verdiyi nəticə 10–20 kilometr arasında ola bilər.

DHZ alqoritmi bütün mümkün marşrutları ayrı-ayrılıqda araşdırmaq əvəzinə, şəbəkədən nisbətən az sayda nümunəvi təpə seçir. Bu nöqtələr digər təpələr arasındakı məsafələri hesablamaq üçün istinad nöqtələri, yəni bir növ “mənzillər” kimi istifadə olunur. Bu strategiya iki təpə bir-birindən uzaqda olduqda yaxşı işləyir. Məsələn, Nyu-Yorkdan Los-Ancelesə olan məsafə kimi uzun bir marşrutda seçilmiş nümunəvi təpələrdən ən azı birinin ən qısa yola yaxın yerləşməsi ehtimalı yüksəkdir.

Belə bir istinad nöqtəsindən keçmək marşruta yalnız kiçik əlavə məsafə gətirə bilər və nəticənin həqiqi məsafənin iki mislindən çox olmamasına imkan yaradar. Lakin qısa marşrutlarda vəziyyət daha mürəkkəbdir.  Məsələn, Los-Anceles ətrafındakı iki yaşayış məntəqəsi cəmi iki tillə birləşdirilə bilər. Ancaq bu məntəqələrin heç biri nümunəvi təpəyə yaxın olmaya bilər. Bu halda uzaqdakı istinad nöqtəsindən keçmək nəticəsində beş tillik məsafə hesablanması mümkündür. Halbuki real məsafə cəmi iki tildir.

Beləliklə, alqoritm bir-birindən kifayət qədər uzaq təpələr üçün sürətli və etibarlı nəticə versə də, yaxın təpələr üçün eyni zəmanəti effektiv şəkildə təmin edə bilmirdi.  

Qrafın müxtəlif miqyaslarda nümunələndirilməsi

Hindistanın Gandhinagar şəhərində yerləşən Hindistan Texnologiya İnstitutunun dosenti Manoj Gupta yeni həlli Kompüter Elminin Əsasları üzrə 66-cı İllik Simpoziumda (FOCS 2025) təqdim edib. Gupta alqoritmi yalnız bir təbəqədən ibarət nümunəvi təpələrə əsaslanmır. Bunun əvəzinə nümunələr bir neçə fərqli miqyasda yerləşdirilir. Hər bir təbəqə qrafın strukturunun fərqli səviyyəsini əhatə edir. Bunun nəticəsində ən qısa yol nisbətən qısa olduqda belə, uyğun istinad nöqtəsinin tapılması ehtimalı artır. Bu çoxmiqyaslı yanaşma “2-yaxınlaşdırma” zəmanətinin tətbiq oluna bildiyi məsafə həddini aşağı salır. Başqa sözlə, yeni alqoritm əvvəlki metodlarla müqayisədə bir-birinə daha yaxın olan təpə cütləri üçün də etibarlı məsafə qiymətləndirməsi apara bilir və bunu ümumi hesablama vaxtının mürəkkəbliyini artırmadan edir.  Nəticə yenə də həqiqi məsafənin iki mislinə qədər ola bilər. Əsas yenilik isə bu zəmanətin tətbiq oluna bildiyi təpə cütlərinin dairəsinin əhəmiyyətli dərəcədə genişlənməsidir.

Böyük qraflar internet marşrutlaşdırması, nəqliyyatın planlaşdırılması, sosial platformalar, bioloji tədqiqatlar və əlaqəli məlumatları emal edən süni intellekt sistemlərinin əsasını təşkil edir. Belə sistemlərdə həmişə dəqiq məsafənin hesablanması tələb olunmur. Müəyyən dəqiqlik zəmanəti ilə sürətli şəkildə əldə edilən təxmini nəticə, hesablanması çox uzun çəkən mükəmməl nəticədən daha faydalı ola bilər. Yeni nəticə hələ kommersiya naviqasiya proqramlarını əvəz edəcək hazır texnologiya deyil. Bununla belə, daha güclü nəzəri sərhədlərin müəyyənləşdirilməsi gələcək alqoritmlərin hazırlanmasına təsir göstərə bilər. Çünki bu cür nəticələr çoxsaylı əlaqələrdən ibarət nəhəng şəbəkələrdən etibarlı məlumatların daha səmərəli çıxarılması yollarını göstərir.

Qraf nəzəriyyəsində irəliləyişlər çox vaxt uzun müddət dəyişməz qalan nəzəri məhdudiyyətlərin kiçik, lakin əhəmiyyətli dərəcədə təkmilləşdirilməsi ilə əldə edilir.

1996-cı ildən böyük ölçüdə qorunub saxlanılan bir zəmanətin genişləndirilməsi müasir texnologiya və elmin qurduğu nəhəng şəbəkələrdə sürətli və miqyaslana bilən məsafə hesablamalarına doğru mühüm nəzəri addım hesab olunur.

mənbə: scitechdaily.com