Lüğət

Soldakı açar sözlərdən birini seçin ...

Qrafiklər və ŞəbəkələrSəyahət Satış Problemi

Oxumaq vaxtı: ~15 min
Bu səhifə avtomatik tərcümə edildi və səhvlər ola bilər. Zəhmət olmasa tərcümələri nəzərdən keçirməyə kömək etmək istəyirsinizsə əlaqə qurun!

Şəbəkələr və xəritələr haqqında bir daha düşünək. Təsəvvür edin ki, bir çatdırılma xidməti ziyarət etməlidir ${tsn} bağlamalar paylamaq üçün fərqli şəhərlər. Bu şəhərləri bir qrafikdəki ucları kimi düşünə bilərik. Bütün şəhərlər yollarla bağlıdırsa, bu , buna görə də var ${tsn} × ( ${tsn} - 1)2 = ${tsn*(tsn-1)/2} cəmi kənarları.

Çatdırılma maşını istənilən qaydada bütün şəhərləri ziyarət etməlidir. Königsberg körpüləri problemində hər tərəfi tam olaraq gedən yolları tapmaq istədik. İndi hər vertexə tam olaraq bir dəfə gedən yolları tapmaq istəyirik. Bu yollara Hamiltonian dövrlər deyilir.

Tam qrafiklərdə Həmilton dövrü üçün saysız-hesabsız fərqli imkanlar mövcuddur. Əslində hər hansı bir vertexi başlanğıc vertexdən başlayaraq istənilən şəhərdə istənilən şəhərdən birini seçə bilərik:

Diagram coming soon…

Diagram Coming Soon…

İlə bir qrafikdə ${tsn1} şəhərlərdə hər Hamiltonian dövrü də olmalıdır ${tsn1} şəhərlər. İndi,

    Bu, ümumilikdə, var deməkdir ${tsnPaths(tsn1)} mümkün yolları. Bu məhsul üçün stenoqramdır ${tsn1} ! və ya ${tsn1} Faktiki .

    Təsəvvür edirsiniz ki, iki şəhər arasında - başqa bir şəhərə getmədən birbaşa səyahət etmək mümkün olmaya bilər. Bu vəziyyətdə artıq tam bir qrafikə sahib deyilik və Hamiltonian dövrlərinin sayını tapmaq, əgər ümumiyyətlə mövcuddursa, daha çətin olur.

    İndiyə qədər bəzi şəhərlərin digərlərindən daha ayrı ola biləcəyini nəzərə almamışıq. Həqiqi həyatda isə bu çox vacib bir məqamdır: biz yalnız hər hansı bir yol tapmaq istəmirik, ancaq ən qısa yolu tapmaq istəyirik. Buna Səyahət Satış Problemi deyilir . Yalnız nəqliyyat və logistika məsələsində deyil, həm də tranzistorları mikroçiplərə yerləşdirərkən, daha sürətli kompüter hazırlamaqda və ya DNT-nin quruluşunu təhlil edərkən həll edilməlidir.

    Bir sadə üsul, mümkün olan bütün yolları sınamaq, hər birinin uzunluğunu tapmaq və ən qısa yolunu seçmək olardı. Ancaq biz bunu ədalətlə də göstərdik ${tsn2} şəhərlər var ${tsn2} ! = ${factorial(tsn2)} mümkün yolları. Yüzlərlə və ya minlərlə yüksəkliklərə sahib olduqda, bütün mümkün yolları sınamaq, hətta güclü kompüterlərdən istifadə etməklə mümkünsüz olur.

    Təəssüf ki, səyahət satıcısı problemini həll etmək üçün daha səmərəli bir alqoritm yoxdur. Bunun əvəzinə, riyaziyyatçılar və kompüter alimləri ən yaxşısı olmasa da, yaxşı həll tapan müxtəlif alqoritmlər hazırlamışlar. Yalnız təxmini həllər verən bu alqoritmlərə Heuristics deyilir.

    Bu xəritədəki şəhərləri yenidən dəyişdirməyə çalışın və aralarındakı ən qısa yolun necə dəyişdiyini izləyin. Şəhərləri vuraraq onları silə bilərsiniz və xəritənin istənilən yerinə (8-ə qədər) tıklayaraq şəhərlər əlavə edə bilərsiniz:

    Xəsis alqoritm (və ya yaxın qonşu alqoritmi) çox sadədir: təsadüfi bir şəhərdən başlayırsınız və ardıcıl olaraq əvvəl ziyarət etmədiyiniz ən yaxın şəhərə keçirsiniz. Bütün şəhərləri gəzdikdən sonra durursunuz.

    Animasiya tezliklə ...

    Orta hesabla xəsis alqoritmi istifadə edərək tapılan yolların ən qısa yoldan 25% daha uzun olduğunu göstərə bilərsiniz.

    2 Opt Alqoritmi təsadüfi mümkün bir yol ilə başlayır. Sonra təkrar-təkrar iki kənarı götür və yolun uzunluğunu azaldacağı təqdirdə onları dəyişdirərsən. Uzunluğu daha da azaltmaq olmadıqda hər hansı bir cüt kənarı dəyişdirərək dayana bilərsiniz.

    Animasiya tezliklə ...

    Məlum olur ki, kompüterlər hələ mövcud olmamışdan xeyli əvvəl Təbiət müxtəlif yerlər arasında optimal yolu tapmaq üçün ağıllı bir yol tapmışdı: qarışqa koloniyalarında.

    Qarışqalar yuvaları və mümkün qida mənbələri arasında ən qısa yolu tapmaq istəyirlər. Bir-biri ilə izləri boyunca buraxdıqları və digər qarışqalar təqib edə bildikləri kimyəvi maddələrlə əlaqə qura bilərlər.

    • Qarışqa koloniyası əvvəlcə təsadüfi istiqamətlərə səyahət edən bir çox skaut göndərir. Yemək tapdıqdan sonra feromon izi qoyub geri qayıdırlar. * Digər qarışqalar tapdıqda cığır izləməyə meyllidirlər ki, bu da onları qidaya aparır. Geri qayıdarkən daha çox feromona əmanət qoyur və bununla da cığırı gücləndirir. * Zaman keçdikcə feromon buxarlanır. Bir yol nə qədər uzun olarsa, qarışqalar onun boyunca getməsinə nə qədər çox vaxt sərf edirlər və buna görə də feromonun buxarlanması üçün daha çox vaxtı olur. Qısa yollar, əksinə, daha sürətli güclənə bilər, buna görə də onların gücü daha sürətli artır.

    Diaqram tezliklə gələcək ...

    Qarışqa koloniyası sistemi (ACS) alqoritmləri bir çox "virtual" qarışqalardan istifadə edərək bu davranışları kompüterlərdə təkrarlamağa çalışırlar. Səyyah satıcısı problemi üçün tez bir zamanda çox yaxşı həll yollarını tapa bilirlər.

    ACS alqoritmlərinin xüsusilə faydalı xüsusiyyəti, fasiləsiz işləyə bilməsi və real vaxtda qrafikdəki dəyişikliklərə uyğunlaşmasıdır. Bu dəyişikliklər avtomobil qəzaları və küçə şəbəkələrində yol bağlanması və ya kompüter şəbəkələrindəki veb serverlərə tıxanma səbəb ola bilər.

    Gəzinti satıcısı problemi NP-çətindir , yəni kompüterlər (ən azı çox sayda şəhər üçün) həll etmək çox çətindir.

    Sürətli və dəqiq bir alqoritm tapmaq kompüter elmləri sahəsində ciddi nəticələrə səbəb olacaqdır: demək olar ki, bütün NP-lər üçün sürətli alqoritmlər mövcuddur. Ayrıca İnternet təhlükəsizliyinin əksər hissəsini yararsız hala gətirər, bu da müəyyən problemlərin kompüterlər üçün çox çətin olduğuna inanır.

    Səyahət edən Satışçı problemini həll etmək üçün sürətli bir alqoritm tapmaq eyni zamanda riyaziyyat və kompüter elmindəki ən məşhur açıq problemlərdən birini, P vs NP problemini həll edərdi. Hər biri 1 milyon dollar mükafat daşıyan yeddi Minillik Mükafat Problemlərindən biridir.