Udweliso Dynamic, imigaqo esisiseko

Ukukhetha le isisombululo eliphezulu xa esenza imisebenzi kweenkqubo wambi kufuneka ukuba ukuhlela oluninzi lwendibaniso data ewalayishayo imemori ye computer. ndlela ziquka, umzekelo, indlela uhlelo of "Yahlula kwaye lulawulo". Kulo mzekelo algorithm inika ingxaki ukwahlukana ibe yayo ezincinane eyahlukileyo. Le ndlela kusebenza kuphela kwiimeko apho imisebenzi yayo esezantsi ezincinane azikhethe ezizimeleyo. Ukuthintela enza umsebenzi ngokungeyomfuneko xa sub-imisebenzi ezihambelanayo, usebenzisa indlela iinkqubo olutshintshatshintshayo ecetywayo American R.Bellmanom kwi 50.

indlela

kweenkqubo Dynamic kukuqinisekisa isisombululo eliphezulu le ngxaki n-mbini, ukwabelana n yakhe izigaba ezahlukeneyo. Ngamnye kubo a sub-umsebenzi ngokuphathelele enye bume.

Inzuzo ephambili yale ndlela kuqwalaselwa ukuba ababhekisi phambili ababandakanyekayo kule ngxaki noun-liyajikeleza yayo endaweni le ngxaki n-mbini, yaye injongo yethu yokuqala uya "bottom-up".

Kucetyiswa ukuba basebenzise iinkqubo onamandla kwiimeko apho sub-imisebenzi zihlobene, ie ukwabelana iimodyuli ezifanayo. I algorithm inika isigqibo nganye yayo kanye, kunye neempendulo yokonga lwenziwa kwitafile ekhethekileyo. Oku kwenza kube lula ukuba ukubala impendulo xa kwakhona badibana efanayo sub-msebenzi.

Dynamic umsebenzi udweliso elisombulula ingxaki ka kahle. Umbhali yale ndlela laliqulunqwe yi R. Bellman optimality Umgaqo: nantoni na isimo sokuqala nganye amanyathelo kunye nesisombululo ezichazwe kweli nyathelo, zonke ezi zinto zilandelayo ukuze ukhethe eyiyo ngokunxulumene kurhulumente, apho ufumana nkqubo ekupheleni inqwanqwa.

Indlela kuphucula ukusebenza imisebenzi isonjululwe ngokusebenzisa ezahlukeneyo, okanye recursion.

umsebenzi Building algorithm

Dynamic algorithm udweliso kubandakanya ukwakhiwa ezinjalo imisebenzi ukuba umsebenzi ngoko zahlulwe zibe yayo ezimbini okanye ngaphezulu ukuya isisombululo yayo ubunjwe isisombululo kangangoko yonke imisebenzi yayo esezantsi, oko kuquka. Ngaphezu koko, kuyimfuneko ukuba abhale ngokunxulumene yokuphinda, nasekubaleni amaxabiso parameter elilelona ukuba lo msebenzi xa iyonke.

Maxa wambi, phezu inyathelo 3 kukuba ngentloko ulwazi ngemvelaphi olongezelelweyo ngenkqubela umsebenzi ngamnye. Le nto ibizwa ngokuba stroke ukubuya.

indlela isicelo

iinkqubo Dynamic lisetyenziswa xa kukho iinkalo ezimbini iimpawu:

• kangangoko ukuze imisebenzi yayo;
• ubukho kwi ingxaki idlulela yileyo.

Ekusombululeni ingxaki noun ngu lwenkqubo eliguqukayo, kufuneka kuqala ukuchaza isakhiwo isisombululo. Lo msebenzi kufuneka abe ngokupheleleyo ukuba isisombululo nto ndiyibhalayo izigqibo ngeyona yayo yayo. Kulo mzekelo, kuyacetyiswa ukuba kusetyenziswe iinkqubo olutshintshayo.

Ipropati lwesibini ingxaki, kubalulekile kule ndlela, - inani elincinane sub-misebenzi. isisombululo recursive ingxaki besebenzisa efanayo sub-iingxaki sifana kakhulu, inani apho kuxhomekeke kubukhulu ulwazi lokuqala. Impendulo lugcinwe kwitafile ekhethekileyo, inkqubo konga ixesha ngokusebenzisa le datha.

Ingakumbi ngempumelelo kukusetyenziswa kweenkqubo olutshintshayo xa ncakasana kufuneka lo msebenzi ukuba benze izigqibo kumanqanaba. Ngokomzekelo, cinga umzekelo olula ingxaki yokutshintshwa kunye nokulungiswa kwezixhobo. Masithi kwi-mveliso kumatshini ekubunjweni ekuveliseni amavili ngexesha elifanayo ukwenza ivili ngeendlela ezimbini ezahlukeneyo. Kwimeko yokuba omnye iifom uyasilela, kuyimfuneko ukuba ibattery umatshini. Iyaqondakala into yokuba ngamanye amaxesha inzuzo ngakumbi ukubuyisela kunye uhlobo yesibini ukuze ibattery umatshini kwimeko kunye nale fom iya kuba nocalu kwinqanaba elilandelayo. Ingakumbi ekubeni kube lula ukubuyisela zombini imilo ukusebenza ngaphambi kokuba uqale ukuze kuphumelele. indlela iinkqubo Dynamic imisela inqubo engcono semcimbini sokutshintshwa kwezi fom, kuthathelwe ingqalelo yonke imibandela: iinzuzo yokuqhubeka iintlobo yokuxhaphaza, ukungabi kwemitshini ngomatshini, iindleko lwamavili ezilahliweyo nangaphezulu.