Müasir cəmiyyətdə informasiyanın həcmi planetin 20 IL əvvəl mövcud olan bütün informasiya həcmini üstələyir. Bütün daxil olan məlumatların emalı çox vaxt aparır

Bu kitab dinamik proqramlaşdırma üzrə digər kitablardan onunla fərqlənir ki, onun arxasında duran riyazi fikirlərdən başlayaraq müzakirə edilir. Sonra bu fikirlərin tətbiqinə yanaşma tədricən qurulur. Daha sadə problemlərdən daha mürəkkəb olanlara keçməklə, oxucu dinamik proqramlaşdırmanın istifadə oluna biləcəyi müxtəlif yolları öyrənəcək və bu fikirləri özbaşına problemlərin həllində necə tətbiq edəcəyini başa düşəcək. Kitabda kağız üzərində və kompüterdə həll etmək üçün tapşırıqlar və problemlər toplusu var. Əsasən, kitabın mətni və tapşırıqlar müasir olimpiada təcrübəsini əks etdirir, lakin sənaye proqramlaşdırmasına da istinadlar var. Dinamik proqramlaşdırma təkcə əksər proqramçıların real həyatda qarşılaşmadığı süni olimpiada məsələlərində istifadə olunmur. Prinsip özü olduqca geniş yayılmışdır: həm oyunların, həm də onlar üçün botların hazırlanmasında (məsələn, ən qısa yolu axtararkən), həm kompilyatorlarda (bəziləri onları həqiqətən yazır), həm də veb proqramlaşdırmada (çox geniş mənada). Bu kitab dinamik proqramlaşdırma üzrə digərlərindən onunla fərqlənir ki, onun əsasında duran riyazi fikirlərdən başlayaraq onu anlatmağa çalışır. Cəbr artıq hər kəsə öyrədilir, lakin rekursiya yox. Həmçinin kitabda hərtərəfli axtarışdan istifadə edən mövcud proqramların necə təkmilləşdirilə biləcəyini nəzərdən keçirilir [27].

Digər bir kitabda Tim Roughgarden “acgöz” alqoritmlərdən (planlaşdırma problemi, minimum əhatəli ağaclar, klasterləşdirmə, Huffman kodları) və dinamik proqramlaşdırmadan (çanta problemi, ardıcıllıqla düzülmə, ən qısa yollar, optimal axtarış ağacları) danışır. “Açgöz” alqoritmlər işin planlaşdırılması probleminə yaxşı uyğun gəlir və başa çatma tarixlərinin ümumi cəmini minimuma endirir. Nəticə dövrlərin növbə ilə işləndiyi iterativ bir quruluşa malikdir. Hansı işin növbəti olduğuna təkrar-təkrar qərar verən “acgöz” alqoritmdən istifadə etmək heç də qeyri-məqbul sayıla bilməz [27].
Həmin müəllifin digər kitabında [28] alqoritmlərdən bəhs edilir. Alqoritmlər kompüter elminin ürəyi və canıdır. Onlarsız heç nə edə bilmərik, alqoritmlərsiz keçinmək mümkün deyil, onlar hər yerdədir - şəbəkə marşrutlaşdırma və genomik hesablamalardan kriptoqrafiya və kompüter təliminin öyrənilməsinə qədər. “Mükəmməl Alqoritm” sizi həm həyatda, həm də hər hansı bir İT şirkətinə işə müraciət edərkən müsahibə zamanı qarşıya vəzifələr qoyacaq və onları ustalıqla həll edəcək əsl peşəkara çevirəcək. Bu kitabda Tim Roughgarden asimptotik analiz, big-O notasiyası, “böl və fəth” alqoritmləri, təsadüfiləşdirmə, çeşidləmə və seçim haqqında danışır.
Planımızın ilk addımı ümumi problemin iki xüsusi halını həll etməkdir. Bu hallara qarşı həll yollarımız ümumi vəziyyətdə “acgöz” alqoritmin necə görünə biləcəyini göstərəcək. Sonra prosedutanı bir namizəd alqoritm qalana qədər daraldırıq və bu konkret namizədin problemi düzgün həll etdiyini sübut edirik. Bu alqoritmə çatdığımız prosesi yadda saxlamaq alqoritmin özündən daha vacibdir; bu proses təkrarlana bilər və biz onu öz proqramlarımızda istifadə edə bilərik.
[29] məqaləsində R. Bellman metodundan istifadə edərək texnoloji avadanlıqların idarəetmə sistemi üçün naqil diaqramlarının layihələndirilməsinin səmərəliliyini artırmaq üçün bir yol təsvir edilmişdir. Texnoloji avadanlıqların idarəetmə sisteminin naqil diaqramının elektron komponentlərini ən yaxşı şəkildə yerləşdirməyə imkan verən riyazi model hazırlanmışdır. Riyazi modelləşdirmənin nəticələri vaxt və maliyyə xərclərini azaltmağa, qəbul edilmiş qərarların etibarlılığını artırmağa imkan verir.
Dinamik proqramlaşdırma iterativ məsələlərin həlli üçün bir üsuldur. Bir çox real problemlər diskret kimi xarakterizə olunur. Bunun səbəbi bəzi amillərin və hesablama obyektlərinin fiziki bölünməzliyidir. Beləliklə, praktikada təxminən 2, 3 fabrik qurmaq və ya qazancının 1/5 hissəsini işə götürmək mümkün deyil. Bütün sənaye hədəfləri zavodların və ya layihə variantlarının dəqiq sayına əsaslanır. Planlaşdırmaya gəldikdə, burada müəssisələrin tipik ölçüləri, vahidlərin tipik tutumlarından istifadə olunur. Bu cür elementlər, öz növbəsində, hesablamaların həyata keçirilməsinə diskretlik gətirir.
Planlaşdırılan göstəricilər var - bunlar illik, aylıq və ya gündəlik dövrlərdir, ayrı-ayrılıqdadır. Hər bir elementin öz başlanğıcı və sonu var.
Diskret proqramlaşdırmaya tam ədəd proqramlaşdırma da deyilir. Bu mövzuda alimlər arasında ixtilaf var. Bir tərəfdən, misallardan göründüyü kimi, belə proqramlaşdırmada həqiqətən də tam ədədlərdən istifadə olunur, digər tərəfdən, ümumiyyətlə, diskret proqramlaşdırma yalnız tam ədəd deyil.
Bu kitabda informatika elmində alqoritmlərin layihələndirilməsi üsullarından biri - dinamik proqramlaşdırma üzrə material qruplaşdırılıb. Bu vəzifələr əslində eyni sxemə uyğun olaraq bu üsuldan istifadə etməklə həll edilir, lakin problemin bu şəkildə həll olunduğunu başa düşmək çox çətindir [30].
Qərar qəbul etmək üçün biliklə yanaşı, oxşar problemlərin həllinə hazırlanmış zəkanın da səyi lazımdır. Məhz kitabın məzmunu və içindəki materialın təqdim edilməsi üslubu informasiyanın intellektual yaradıcı emalına kömək edir. Müxtəlif illərdə informatika üzrə keçirilən olimpiadalarda, eləcə də turnir və yarışlarda məktəblilərə təklif olunan problemlərə baxılır.
Baxdığımız bu məqalədə [31] həlli üçün əvvəllər təklif edilmiş hələ ötən əsrin ortalarında R. Bellman tərəfindən hazırlanmış dinamik proqramlaşdırma metodu tətbiqi məsələlərdən bəhs edilir. Optimallıq prinsipinə və ondan irəli gələn rekurent tənliklərə əsaslanan bu üsul bir çox mürəkkəb tətbiqi məsələlərin həllini eyni tipli daha sadə məsələlərin ardıcıllığının həllinə gətirməyə imkan verirdi.
Bu günə qədər bir çox praktiki vacib problemlər dinamik proqramlaşdırmanın köməyi ilə həll edilmişdir. Bununla belə, irimiqyaslı məsələlərin həlli zamanı, xüsusən də dinamik proqramlaşdırma alqoritminin çoxaldılan təkrar hesablamalar dövrünə qurulduğu sistemlərin işlənib hazırlanması zamanı müasir kompüterlərin gücünü nəzərə alsaq belə, hesablama vaxtı yolverilməz dərəcədə uzun olur. Dinamik proqramlaşdırmanın səmərəliliyinin artırılması problemi aktual olaraq qalır. Müəyyən edilmişdir ki, eyni tətbiqi məsələlərin həlli zamanı dinamik proqramlaşdırmanın müxtəlif tətbiqləri mümkündür.
Məqalədə tətbiq olunan problemlərin spesifik xüsusiyyətlərinin ətraflı təsviri ilə dinamik proqramlaşdırmadan istifadənin səmərəliliyinin artırılması imkanları təhlil edilir. Bu problemlərin bəziləri variantları sadalamadan R.Bellmanın optimallıq prinsipi əsasında optimal trayektoriyanın hesablanması üçün rekursiv düsturlar almağa imkan verir. Göstərilmişdir ki, həlli üçün konkret vəziyyətə aparan dinamik proqramlaşdırma metodu təklif edilmiş bir çox tətbiqi problemlər hesablama prosesində əlavə perspektivsiz vəziyyətlərə imkan verir.
Bu, həm yaddaş istifadəsi, həm də hesablama vaxtı baxımından dinamik proqramlaşdırmanın səmərəliliyini kəskin şəkildə artırır. Bu bəyanat yeni alqoritmin effektivliyini qiymətləndirmək üçün hesablamaların aparılması üçün xüsusi hazırlanmış eksperimental proqramların istifadəsinə əsaslanır.
Xətti proqramlaşdırma - məqsəd funksiyası və məhdudiyyətlər xəttidir; kvadratik proqramlaşdırma - məqsəd funksiyası kvadrat 8 və qabarıqdır, icazə verilən çoxluq xətti bərabərliklər və bərabərsizliklər ilə müəyyən edilir; Konveks proqramlaşdırma - məqsəd funksiyası və icazə verilən çoxluq qabarıqdır; Diskret proqramlaşdırmada həll yalnız diskret, məsələn, dəyişən qiymətlərin icazə verilən çoxluğunun tam, nöqtələrində axtarılır; Stokastik proqramlaşdırma, deterministik problemlərdən fərqli olaraq, burada daxil olan məlumat qeyri-müəyyənlik elementinə malikdir. Dinamik proqramlaşdırma üsulu ilə həll olunan tapşırıqların diapazonu aydın şəkildə qeyd olundu. O dövrdə metod bir sapma ilə idarəetmə sistemlərinin problemlərində optimal (ən yaxşı) həll üsulları ilə eyni sıraya daxil edilmişdir. Əgər xətti və riyazi proqramlaşdırma üsulları statik idisə, dinamik proqramlaşdırmada həllinin axtarıldığı sistem zamanla dəyişə bilərdi. Metodun başqaları ilə müqayisədə xüsusiyyəti ondan ibarətdir ki, problemin həlli üçün sistemin və sistemin özünü idarə etmək üçün bütün prosesi sabit vaxt intervallarına bölmək olar, burada problemin optimal həlli problemin optimal həllindən ibarətdir. hər bir interval (mərhələ, addım). Buna görə də metod "dinamik" - zamanla dəyişən adlanırdı.O dövrdə "dinamik proqramlaşdırma" (dinamik proqram) termini heç bir şəkildə müasir terminlə əlaqəli deyildi, bu da dinamik proqramlaşdırmanın dinamik proqramlaşdırmanın yaradılmasında istifadə edildiyini nəzərə alır. proqram təminatı - kompüter cihazında hesablanan kod şəklində kompüter həlli.
Riyaziyyat və kompüter nəzəriyyəsində dinamik proqramlaşdırma (dinamik proqram) optimal alt quruluşa və üst-üstə düşən alt tapşırıqlara malik məsələlərin həlli üsuludur ki, bu da hərtərəfli sadalamadan 9 dəfə daha səmərəlidir [7]. 1953-cü ildə sonrakı inkişaf zamanı dinamik proqramlaşdırma artıq tətbiqi riyaziyyatın bir qolu kimi investisiya edilmədi. Ümumilikdə informatika ilə əlaqəli oldu və adını aldı. Dinamik proqramlaşdırma (dinamik proqram) mürəkkəb problemləri daha sadə alt tapşırıqlara bölmək yolu ilə həll etmək üsuludur, burada problemin həllinin hər bir addımı üçün sabit vaxt ayrılır. Dinamik proqramlaşdırma metodunun tətbiq olunduğu problem mürəkkəbliyi orijinaldan daha az olan üst-üstə düşən alt tapşırıqlar toplusuna bənzəyən optimal alt strukturu ehtiva etməlidir [32]. Dinamik proqramlaşdırmada optimal alt struktur dedikdə, ilkin məsələnin həlli üçün daha kiçik alt problemlərin optimal həllindən istifadə oluna bilər [33-34]. Dinamik proqramlaşdırmada üst-üstə düşən altproblemlər dedikdə, daha böyük ölçülü bir sıra məsələlərin (bir deyil) həlli üçün istifadə olunan (yəni biz eyni işi bir neçə dəfə edirik) alt problemlər başa düşülür [35]. Dinamik proqramlaşdırma, optimallaşdırma problemlərinə əlavə olaraq, indi alqoritmlərin layihələndirilməsi üçün yaxşı müəyyən edilmiş metodu təsvir etdi. Əlbəttə ki, metod universal deyil və həmişə problemin verilmiş şərtlərinə uyğun gəlmir. Dinamik proqramlaşdırma metodunun tətbiq olunduğu problemlər çoxdan məlumdur. Tapşırığı alt tapşırıqlara bölmək hər hansı bir alqoritm qurmaq üçün standart təcrübədir - bütün proqramçıların istifadə etdiyi universal üsul. Lakin dinamik proqramlaşdırmanın mahiyyəti iki termindən ibarətdir: “dağılma”, “layout”. Həll edilməli olan problem eyni tipli alt tapşırıqlara bölünməyə imkan verməlidir ki, həll alt tapşırıqların optimal həllərindən bir növ əlavə olunsun. Yəni təkrarlanma əlaqələri müəyyən edilməlidir - 10 alt tapşırıq arasındakı asılılıqlar. Metodun bir xüsusiyyəti ondan ibarətdir ki, biz hər bir alt tapşırığı yalnız bir dəfə həll edirik, onun həllini xatırlayırıq. Onun optimal həllinin nəticəsi hər addımda yadda saxlanılır və sonrakı məsələlərin həlli zamanı verilən kimi istifadə olunur. Bir alt tapşırıqdan digərinə keçərkən iki əsas məqam əldə edilir: “bağlantı” və “xatırlama”. Dinamik proqramlaşdırma metodu kənardan sadə görünür və göründüyü kimi, istənilən problemin həllində tətbiq oluna bilər, lakin hər şey o qədər də sadə deyil. Problemə metodu tətbiq etmək üçün universal tövsiyələr yoxdur! Hələ heç kim hər tapşırıq üçün dinamik bir sxem hazırlamayıb. Bunu başa düşmək lazımdır, çünki müəyyən hallarda dinamik proqramlaşdırmadan istifadə edərək həll tapmaq olduqca çətindir. Bundan əlavə, lemmanın, teoremlərin və s.-nin ciddi qaydaları yoxdur.Bu hansısa teorem halı deyil, üsulu ancaq konkret məsələlərin həlli praktikasından öyrənə bilərsiniz. Buna görə dinamik proqramlaşdırmanın bütün nəzəriyyəsi praktikanın 90% -ni və nəzəriyyənin yalnız 10% -ni ehtiva edir. Dinamik proqramlaşdırmanın konsepsiyasını və metodunu tədqiq edərək, onu təşkil edən və məsələlərin həllində istifadə olunan 4 prinsipi ayırd edə bilərik.
1. Həll olunan mürəkkəb problem (məsələ və ya tapşırıq) sadə hala gələnə qədər həmişə bir çox alt tapşırıqlara bölünür. Sadəcə olaraq, bu, əsas tapşırığın eyni tipdən daha sadə olanlara endirilməsidir.
2. Dinamik proqramlaşdırma bütün həllərin tam sadalanmasını tələb edən problemləri həll edir:
2.1. "Seçimlərin sayını hesablamaq..."
2.2. "Optimal şəkildə necə paylamaq olar..."
2.3. "Ən yaxşı marşrutu tapmaq..."
3. Optimallıq prinsipi problemin həllinin hər bir addımında qəbul edilən optimal qərarın əvvəlki dövrdən asılı olmamasında təzahür edir. Hazırda prosesi xarakterizə edən amillər nəzərə alınmaqla optimal həll yolu seçilir. Nümunə olaraq qrafikdə bir idarəetmə nöqtəsindən digərinə ən qısa yolun, son nöqtəyə getmək üçün lazım olan aralıq nöqtənin seçilməsidir, bu nöqtəyə necə, nə vaxt və hansı yolla gəldiyindən asılı olmayaraq qərar veririk. Biz yalnız yol şəbəkəsində nöqtənin yerini əsas tuturuq.
4. Dinamik proqramlaşdırma məsələlərini həll edərkən məsələnin həllini sürətləndirmək üçün əlavə yaddaş tələb olunur, çünki hər addımda parametrlərin ən kiçik və ya ən böyük qiyməti ilə bütün alt tapşırıqların həllini yadda saxlanmalı və lazım olduqda istifadəyə hazır olmalıdır.
Dinamik proqramlaşdırmada problemlərin həllinə iki yanaşma var:
1.Yuxarıdan aşağıya dinamik proqramlaşdırma: problem daha kiçik alt problemlərə bölünür, onlar həll edilir və sonra birləşərək orijinal məsələni həll edirlər. Yadda saxlama tez-tez baş verən alt tapşırıqları həll etmək üçün istifadə olunur.
2. Aşağıdan yuxarıya dinamik proqramlaşdırma: ilkin problemi həll etmək üçün sonradan lazım olan bütün alt tapşırıqlar əvvəlcədən hesablanır və sonra ilkin məsələnin həllini qurmaq üçün istifadə olunur. Bu üsul tələb olunan stek ölçüsünə və funksiya çağırışlarının sayına görə yuxarıdan aşağı proqramlaşdırmadan daha yaxşıdır, lakin bəzən gələcəkdə hansı alt problemləri həll etməli olduğumuzu əvvəlcədən müəyyən etmək asan olmur.
Dinamik proqramlaşdırma üsulu ilə həll edilən bütün növ məsələlər aşağıdakı alqoritmə uyğun olaraq həll edilir:
1) həlli yolu ilə istənilən həllin ifadə olunacağı alt tapşırıqları, optimal həllərin strukturunu müəyyənləşdirin və təsvir edin;
2) alt tapşırıqlar üçün parametrin optimal qiymətlərini birləşdirən təkrarlanan əlaqələri (tənlikləri) yazın;
3) bütün alt tapşırıqlar üçün parametrin optimal dəyərini hesablamaq;
4) alınan məlumatlardan istifadə edərək optimal həll yolu qurmaq.
Əgər optimal yolun axtarışından fərqli olaraq, müəyyən bir şərt üçün mümkün variantların və ya həllərin sayını hesablamaq problemi ilə qarşılaşırıqsa, alqoritmdə 4-cü addım olmayacaqdır. Bununla belə, 3-cü addımda alqoritmin bütün əvvəllər icra edilmiş həllərini əlavə məlumat şəklində saxlamaq üçün əlavə bir addım yerinə yetirməlisiniz. Problemləri həll edərkən, 4-cü addımın həyata keçirilməsi adətən ən çətin olur.