Dinamik Proqramlaşdırma Əsasları

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Infosys MAQ
Dinamik proqramlaşdırma nəzəriyyəBaxılıb 31

Dinamik Proqramlaşdırma əsaslarında DP-nin əsaslarını və Açgözlü metoddan, Bölün və Fəth edin və Rekursiyadan fərqlərini əhatə edəcəyik.

Dinamik proqramlaşdırma, təkrarlama, bölmə və fəth etmə kimi bir yanaşmadır. Problemi alt problemlərə ayırır. Ancaq bu alt problemləri bölün, fəth edin və rekursiya kimi müstəqil olaraq həll etmək əvəzinə əvvəlki alt problemlərin nəticələrini üst-üstə düşən problem olaraq da bilinən oxşar hesablamalar üçün istifadə edir.

Proqramların optimallaşdırılması üçün istifadə olunur. Əvvəllər hesablanmış nəticələrdən istifadə edildiyi üçün, eksponent zaman mürəkkəbliyindən istifadə etmək çox polinuma endirilə bilər. Məsələn - Çirkin Nömrələrin rekursiv həllinin zaman mürəkkəbliyi eksponent və DP həllinin xətti.

DP-nin bəzi əsas problemləri

  • Çirkin rəqəmlər problemi
  • Sikkə dəyişikliyi
  • Fibonacci nömrələri
  • Zəng nömrələri problemi
  • Hanoi qülləsi
  • Zəng nömrələri
  • Qapaq problemi

Dinamik Proqramlaşdırma (DP) və Acgöz Metod

DP-də hər bir addım optimal həlli əldə etmək üçün mövcud və əvvəlki həlləri nəzərə alaraq həllini qiymətləndirir. Ancaq acgöz alqoritmdə yalnız mövcud vəziyyəti nəzərə alaraq ən yaxşı variantı seçirik.

Xəsislik metodları ümumiyyətlə DP-dən daha sürətli olmasına və gələcəkdə istifadə üçün əvvəlcədən hesablanmış dəyərləri saxlamadığı üçün yaddaşa da təsirli olsa da, optimal bir həll zəmanəti vermir.

Dinamik Proqramlaşdırma (DP) vs Divide & Conquer Method

Bölmək və fəth etmək üçün bir problemi alt problemlərə ayırırıq və hər alt problemi müstəqil olaraq həll edirik. Lakin DP-də problemləri müstəqil həll etməkdənsə, əvvəllər əldə edilmiş nəticələri yeni hesablamalar üçün istifadə edirik. Başqa sözlə, Böl və Fəth et + Yaddaşlaşma = yuxarıdan aşağıya dinamik yanaşma deyə bilərik.

(Yaddaşlama, əvvəlcədən hesablanmış nəticələrin ümumiyyətlə eyni problemlərin hesablanmasının qarşısını almaq üçün ümumiyyətlə hash-map-də saxlama üsuluna aiddir.)

Dinamik Proqramlaşdırma (DP) və Rekursiya Metodu

DP, yenidən hesablamaların qarşısını almaq üçün əvvəlcədən hesablanmış həlləri istifadə etmək üçün və gələcəkdə yenidən tələb olunduqda saxlayır. Bununla birlikdə, rekursiyada, dəyərləri saxlamadığı üçün lazımsız olan yenidən hesablamaların olması ehtimalı var.

Rekursiya problemlərin bir neçə dəfə yenidən hesablanmasına gətirib çıxarır, buna görə də belə hallarda rekursiyanın zaman mürəkkəbliyi həmişə DP həllindən çox olur.

Bu yazıda, haqqında danışdıq Dinamik proqramlaşdırma əsaslar. Növbəti məqalələrdə DP ilə bağlı bəzi əsas problemləri əhatə edəcəyik.

arayış Müsahibə Suallar

Translate »