Programming Dynamic, prinsip-prinsip dhasar

Kanggo milih solusi optimal nalika nindakaké tugas program sing kadhangkala dibutuhake kanggo Ngurutake gedhe Jumlah saka kombinasi data sing kathah memori saka komputer pribadi. cara kaya mengkono iku kalebu, contone, cara program saka "dibagi lan aturan". Ing kasus iki algoritma menehi masalah misahake menyang subtasks cilik kapisah. Cara iki ditrapake mung ing kasus-kasus iku ngendi subtasks cilik sing bebarengan sawijining. Kanggo supaya Performing karya rasah yen interdependent sub-tugas, migunakake cara program dinamis ngajokaken Amérika R.Bellmanom ing 50s.

cara

programming Dynamic kanggo nemtokake solusi optimal masalah n-dimensi, nuduhake n orane tumrap sekolah kapisah dheweke. Saben wong iku sub-tugas karo bab siji global.

Ing kauntungan utama iki pendekatan bisa dianggep sing gawe melu masalah Optimization siji-dimensi subtasks tinimbang masalah n-dimensi, lan adil utami kita arep kanggo "bottom up".

Sampeyan saranake kanggo aplikasi program dinamis sing njagani sub-tugas sing magepokan, IE nuduhake modul umum. algoritma menehi kaputusan saka saben subtasks sapisan, lan respon daya wis dileksanakake ing Tabel khusus. Iki ndadekake iku bisa ora kanggo ngetung jawaban nalika padha ketemu maneh karo sub-tugas padha.

tugas program Dynamic solves masalah Optimization. Penulis cara iki nyusun dening R. Bellman optimality asas: apa iku negara dhisikan saka saben langkah lan solusi ditetepake ing langkah iki, kabeh saka ing ngisor iki kanggo milih optimal ing hubungan kanggo negara, kang ditampa sistem ing mburi langkah.

cara mbenakake kinerja saka tugas ditanggulangi kanthi Varian, utawa recursion.

algoritma tugas Building

algoritma program Dynamic melu pambangunan tugas kuwi sing tugas supaya dipérang dadi loro utawa luwih subtasks kanggo menehi solusi dumadi saka solusi optimal kanggo kabeh subtasks, kalebu. Luwih, iku perlu kanggo nulis hubungan ambalan, lan ngitung angka parameter paling luweh kanggo tugas minangka wutuh.

Kadhangkala, ing langkah 3 iku apal sawetara informasi latar mburi tambahan ing kemajuan saben tugas. Daftar iki disebut stroke bali.

cara aplikasi

programming Dynamic wis Applied nalika ana loro fitur karakteristik:

• optimal kanggo subtasks;
• ngarsane ing masalah saka nyalip subproblems.

Ngrampungaken masalah Optimization dening program dinamis, sampeyan kudu njlèntrèhaké struktur saka solusi. tugas wis dadi optimal yen solusi dumadi saka pancasan paling saka subtasks sawijining. Ing kasus iki, iku luwih apik kanggo nggunakake program dinamis.

Properti kapindho masalah, penting ing cara iki, - nomer cilik sub-tugas. solusi rekursif saka masalah nggunakake nyalip sub-masalah padha, nomer kang gumantung ing ukuran resmi dhisikan. Jawaban iki disimpen ing meja khusus, program ngirit wektu kanthi nggunakake data iki.

Utamané efektif nggunakake program dinamis nalika tugas punika ateges needed kanggo pancasan ing orane tumrap sekolah. Contone, nimbang conto prasaja saka masalah panggantos lan ndandani saka peralatan. Ayo dadi ngomong ing pabrik mesin casting kanggo produksi ban ing wektu sing padha nggawe ban ing loro macem-macem formulir. Ing acara sing siji saka format ing gagal, iku perlu kanggo mbongkar mesin. Dingerteni sing kadhangkala liyane duwe bathi kanggo ngganti lan wangun liya supaya mbongkar mesin cilik lan wangun iki bakal unworkable ing tahap sabanjure. Utamané wiwit iku luwih gampang kanggo ngganti kaloro wangun apa sadurunge miwiti gagal. cara program Dynamic nemtokake strategi paling ing prakara panggantos bentuk, njupuk menyang akun kabeh faktor: keuntungan saka formulir terus eksploitasi, mundhut saka downtime mesin, biaya ban dibuwak lan liyane.