Динамик програмчлалын үндэс


Хэцүү байдлын түвшин Easy
Байнга асуудаг Infosys MAQ
Динамик програмчлал Онол

Динамик програмчлалын үндсүүдэд бид DP-ийн үндэс суурь, түүний хуваагдал, байлдан дагуулал, Recursion гэсэн шунахай аргаас ялгааг авч үзэх болно.

Динамик програмчлал нь рекурс хийх, хувааж эзэмшихтэй адил арга юм. Энэ нь асуудлыг дэд асуудал болгон хуваадаг. Гэхдээ эдгээр дэд асуудлуудыг хуваах, байлдан дагуулах, рекурс хийх гэх мэтээр бие даан шийдвэрлэхийн оронд өмнөх дэд асуудлуудын үр дүнг ижил төстэй тооцоонд ашигладаг.

Энэ нь програмыг оновчтой болгоход хэрэглэгддэг. Өмнө нь тооцоолсон үр дүнг ашигладаг тул түүний экспоненциал цагийн нарийн төвөгтэй байдлыг ашиглан олон гишүүнт болгон бууруулж болно. Жишээлбэл - Муухай тоонуудын рекурсив шийдлийн хугацааны нарийн төвөгтэй байдал нь экспоненциал, DP шийдэл нь шугаман байна.

АН-ын зарим үндсэн асуудлууд

  • Муухай тооны асуудал
  • Зоос солих
  • Fibonacci тоо
  • Хонхны дугаар асуудалтай байна
  • Ханой хотын цамхаг
  • Хонхны дугаар
  • Үүргэвчтэй холбоотой асуудал

Dynamic Programming (DP) vs Greedy Method

АН-д алхам бүр оновчтой шийдлийг олж авахын тулд одоогийн болон өмнөх шийдлүүдийг харгалзан шийдлийг үнэлдэг. Гэсэн хэдий ч шунахай алгоритм дээр бид зөвхөн одоогийн нөхцөл байдлыг харгалзан хамгийн сайн сонголтыг сонгодог.

Хэдийгээр шунахай аргууд нь ерөнхийдөө DP-ээс хурдан бөгөөд санах ойд хэмнэлттэй байдаг тул ирээдүйд ашиглахад зориулж урьд өмнө тооцоолсон утгуудыг хадгалдаггүй тул энэ нь оновчтой шийдлийн баталгаа болж өгдөггүй.

Dynamic Programming (DP) vs Divide & Conquer Method

Хуваах, ялахдаа бид асуудлыг дэд асуудал болгон хувааж дэд асуудал бүрийг бие даан шийдвэрлэнэ. Гэхдээ АН-д асуудлыг бие даан шийдвэрлэхээс илүүтэйгээр бид өмнө нь олж авсан үр дүнгээ шинэ тооцоололд ашигладаг. Өөрөөр хэлбэл бид хувааж, байлдан дагуул + Цээжлэх = дээрээс доош динамик хандлага гэж хэлж болно.

(Цээжлэх гэдэг нь ижил асуудлуудыг дахин дахин тооцоолохоос урьдчилан сэргийлэх зорилгоор урьд нь тооцоолсон үр дүнг ерөнхийдөө хэш-газрын зураг дээр хадгалах техникийг хэлнэ.)

Динамик програмчлал (АН) vs Recursion Method

АН нь дахин тооцоолохоос зайлсхийхийн тулд өмнө нь тооцоолсон шийдлүүдийг ирээдүйд дахин ашиглах шаардлагатай үед хадгалдаг. Гэсэн хэдий ч рекурсын хувьд дахин тооцоолол хийх боломжтой бөгөөд энэ нь үнэ цэнийг хадгалдаггүй тул шаардлагагүй юм.

Рекурс нь асуудлыг хэд хэдэн удаа дахин тооцоолоход хүргэдэг тул ийм тохиолдолд рекурсын хугацааны нарийн төвөгтэй байдал нь АН-ын шийдлээс хамаагүй их байдаг.

Энэ нийтлэлд бид энэ талаар авч үзсэн Динамик програмчлал үндсүүд. Дараагийн өгүүллүүдэд бид АН-тай холбоотой зарим үндсэн асуудлуудыг авч үзэх болно.

лавлагаа Ярилцах асуултууд