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

програмчлалын үүрэг заримдаа хувийн компьютерийн санах ой эхлэж мэдээлэл нэгдлийн их хэмжээний ангилахын тулд шаардлагатай хийж байх үед хамгийн оновчтой шийдлийг сонгох хэрэгтэй. Ийм арга Жишээ нь, "хуваагдал ба дүрэм" -ийн програмчлалын арга орно. Энэ тохиолдолд алгоритм нь тус тусад нь жижиг шийдлүүдийг болгон хуваах асуудлыг олгодог. Энэ арга нь зөвхөн жижиг дэд даалгавар харилцан бие даасан хүмүүст тохиолдолд хэрэглэж болно. харилцан хамааралтай дэд зорилт бол шаардлагагүй ажил хийж зайлсхийхийн тулд 50 гаран настай АНУ-ын R.Bellmanom санал динамик програмчлалын аргыг ашигладаг.

арга

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

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

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

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

арга төрлүүдтэй, эсвэл рекурсын замаар шийдэж ажлуудын гүйцэтгэлийг сайжруулдаг.

Барилгын ажил алгоритм

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

Заримдаа, 3-р алхам дээр ажил тус бүр явцын талаар зарим нэмэлт суурь мэдээллийг цээжлэх явдал юм. Энэ нь буцах харвалт гэж нэрлэдэг.

Хэрэглээний арга

хоёр шинж онцлог байдаг байх үед Динамик програмчлалын хэрэглэж байна:

• шийдлүүдийг оновчтой;
• subproblems давхардсан асуудал байгаа эсэх.

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

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

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