Maraqlıdır

Alqoritmlər, Optimizasiya və Səyahət edən Satıcı Problemi

Alqoritmlər, Optimizasiya və Səyahət edən Satıcı Problemi


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Bu, dünyamızı gücləndirmək üçün sadə ikili rəqəmlərdən necə istifadə etdiyimizi araşdıran Alqoritmlər və Hesablamalara dair yeddi hissəli seriyanın beşinci məqaləsidir. İlk məqalə, Alqoritmlər Yaşadığımız Dünyanı necə idarə edir, burada tapa bilərsiniz.

Nəzəri bir kompüter aliminin əsas işi problemlər üçün səmərəli alqoritmlər tapmaqdır və bu problemlərdən ən çətini sadəcə akademik deyil; hər gün oynanan ən çətin real dünya ssenarilərinin təməlində dayanırlar. Bunlardan ən kritiksi optimallaşdırma problemidir: bunu necə tapırıq yaxşı sonsuz görünən mümkün həll yollarımız olduqda problemin həlli?

İLƏ BAĞLI: YENİ ALQORİTM AVTOMOBİL Maşınlara insan kimi daha çox yer dəyişdirməyə icazə verir

Hələlik edə biləcəyimiz ən yaxşı şey evristik bir yanaşma və akifayət qədər yaxşı həll, lakin zamanla bir araya gələn və başqa yerdə daha yaxşı istifadə edilə bilən sonlu mənbələrimizi tükəndirən hesablanmayan təsirsizlər səviyyəsini yaradırıq. Buna Səyyar Satıcı Problemi deyirik və bu problemin həllinin iqtisadiyyatımıza trilyonlarla dollar qənaət edə biləcəyini söyləmək çox azdır.

Səyahət edən Satıcı Problemi, Eksponent Zamanın Mürəkkəbliyi və Beyond

Səyahət edən Satıcı Problemi belə izah olunur: bir şirkət, səyahət satıcılarından birinin siyahıdakı hər şəhəri ziyarət etməsini tələb edir n siyahıdakı bir şəhər ilə hər şəhər arasındakı məsafələrin məlum olduğu şəhərlər. Hər bir şəhər yalnız bir dəfə ziyarət edilə bilər və satıcı başladığı şəhərdə bitirir. Bunu həyata keçirə biləcəyi ən qısa yol nədir?

Bu problem üçün bildiyimiz ən təsirli alqoritm işləyir eksponent vaxt, gördüyümüz kimi olduqca qəddardır. RSA şifrələməsindən fərqli olaraq, Səyahət edən Satıcı Problemi halında, Shor alqoritminin etdiyi kimi modul hesab və ya faktorizasiyanı dövr tapmağa çevirmə yoxdur. Gəzən Satıcı Problemi bir qərar problemidir və bildiyimiz heç bir qısa yol yoxdur ki, bizi altına atsın eksponent zamanın mürəkkəbliyi.

Bunun niyə dəhşətli bir vəziyyət olduğunu gücləndirmək üçün gəlin dəli olduğuna dair çox yayılmış bir nümunədən istifadə edək eksponent zamanın mürəkkəbliyi ala bilər. Deyək ki, bir kağızı istədiyiniz qədər dəfələrlə qatlaya bilərsiniz və bu daima qatlamaq üçün lazım olan qədər uzunluğa sahib olacaqdır. Qatlanmış kağızın bizdən uzağında böyüdüyü son məhsulda "vərəqlər" yığınının genişliyini ölçərək, gözlədiyiniz budur:

* 0 qat: 1 / 250th düym qalınlığı.
* 10 qat: ~ 2.05 düym qalın.
* 25 qat: ~ 1 mil qalın.
* 43 qat: Ayın səthi.
* 52 qat: Günəşin içərisində.
* 57 qat: Ultima Thule-dən keçmək
* 67 qat: Bir ucundan digərinə keçmək üçün 1,5 il işıq alır.
* 82 qat: Samanyolu qalaktikası qədər genişdir.
* 93 qat: Messier 87-nin mərkəzindəki supermassive qara dəliyin astronomik atma məsafəsində.
* 101 qat: Orada nə olduğundan əmin deyiləm, çünki müşahidə edilə bilən kainatın xaricindədir.

Və bu yaxşı indi əldə etdiyimiz alqoritm. Bu yığının içindəki "vərəqlərin" hər biri satıcının gedə biləcəyi bir yol sonunda uzunluğu bütün digər marşrut uzunluqlarına görə yoxlamaq və ölçmək lazımdır və hər qat, ziyarət etməsi lazım olan şəhərlər siyahısına əlavə bir şəhər əlavə etməyə bərabərdir. Ən yaxşı həll yolunu tapmaq üçün mümkün olan hər hansı bir yolu yoxlayaraq Səyahət edən Satıcı Problemini həll etməyə çalışdığımız üçün səhv etdiksə, baxırıq faktiki zaman mürəkkəbliyi. Bizim istifadə 128-bit 2 olan RSA şifrələmə nümunəmizin nömrəsi128101 qat yalnız 2-dir101, 35! 2-dən keçmiş zərbələr128 ən azı 100 faktor. Girdiyiniz hər əlavə artımla daha da pisləşir və bu, Səyahət Satıcısı Problemini bu qədər vacib və eyni zamanda dəli edən bir şeydir.

Optimizasiya alqoritmləri problemi

Səyahət edən Satıcı Probleminə düzgün cavabı necə tapacağımızı bilmirik, çünki ən yaxşı cavabı tapmaq üçün bütün digər cavabları istisna etmək üçün bir yola ehtiyacınız var və bunu bütün imkanları yoxlamadan və ya saxlamadan necə edəcəyimiz barədə heç bir fikrimiz yoxdur. indiyə qədər tapılmış ən qısa marşrutun bir qeydidir və cari marşrutumuz bu rəqəmi keçdikdən sonra yenidən başlayır. Bu, sahib olduğumuz ən yaxşı şeydir və bu, yalnız şeyləri ətrafa gətirir eksponent zamanın mürəkkəbliyi, buna görə bir həll olaraq, heç bir həll yolu deyil.

Səyahət edən Satıcı Problemi bir çox səbəbə görə xüsusi bir şeydir, amma ən başlıcası, bir optimallaşdırma problemi olması və optimallaşdırma problemləri gündəlik həyatda hər yerdə ortaya çıxmasıdır. Giriş ölçülərinə gəldikdə, 101 heç də çox deyil. Həqiqi dünyada, ABŞ-ın tək bir əyalətində nəzəri olaraq böyük ticarət distribyutorunun çatdırılma sahəsinin bir hissəsi ola biləcək bir çox kiçik şəhər və ya şəhər var. Yük maşınlarının gündəlik olaraq müxtəlif müştərilərə etməsi lazım olan bütün dayanacaqlar arasındakı ən qısa marşrutu müəyyənləşdirmək, əmək və yanacaq xərclərinə saysız-hesabsız puldan qənaət edəcəkdir.

Xaricdən fabrikiniz üçün hissələr alırsınızsa, çatdırılma metodlarının hansı marşrutu və birləşməsi sizə ən az pula başa gələcək? Xərçəngi məğlub edə biləcək zülal qatlarının hansı konfiqurasiyası var? Səyahət edən Satıcı Problemini yaxın bir şeydə həll edə biləcək bir alqoritm tapmaq polinom vaxtı hər şeyi dəyişdirər və bunu bir gecədə edərdi.

Problemin bir hissəsi də problemin təbiətinə görə bir həll yolunun olub olmadığını bilmirik polinom vaxtı riyazi olaraq mümkündür. Bunun səbəbi problemləri təsnifləşdirmə tərzimiz və Səyahət edən Satıcı Probleminin, sistemdəki riyaziyyat və kompüter elmindəki ən böyük problemlərdən birini meydana gətirən, gerçək dünya üçün təsirləri çox xüsusi bir təsnifata aid olmasıdır.

Alqoritmlər və Hesablamalar seriyamızın altıncı məqaləsi, P Vs. NP, NP-Complete və hər şey üçün alqoritm, burada tapa bilərsiniz.


Videoya baxın: اقوى تطبيق شحن شدات بيجي مجانا ثغرة رهيبة. ببجي موبايل (BiləR 2022).