Dynamic shirye-shirye, da ka'idodi

Don zaɓar mafi kyau duka bayani a lõkacin yin shirye-shirye da ayyuka a wani lokaci ana bukata don warware yawa data haduwa da lodi da memory na sirri kwamfuta. Irin wannan hanyoyin sun hada da, misali, da shirye-shirye Hanyar "rabawa da mulki". A wannan yanayin da algorithm samar da rabuwa matsala a cikin raba karami subtasks. Wannan hanya ne m kawai a kuma waɗannan lokuta inda kananan subtasks suna da tarayyar m. Don kauce wa yin da ba dole ba aiki idan interdependent sub-ayyuka, yana amfani da tsauri shirye-shirye Hanyar samarwa American R.Bellmanom a cikin 50s.

A hanyar

Dynamic shirye-shirye ne domin sanin da mafi kyau duka bayani da n-girma matsala, raba ta n raba saukarwa. Kowane daga cikinsu shi ne wani sub-aiki tare da girmamawa ga daya m.

Babban amfani da wannan dabarar za a iya gani da cẽwa developers da hannu a cikin daya-girma ingantawa matsalar subtasks maimakon wani n-girma matsala, kuma mu primary haƙiƙa da yake faruwa da "kasa-up".

A bu mai kyau zuwa ga tambaya tsauri shirye-shirye a cikin waɗannan lokuta inda da sub-ayyuka suna m, watau raba kowa kayayyaki. A algorithm bayar da shawarar da kowane daga cikin subtasks sau daya, kuma saving martani aka yi a wani na musamman tebur. Wannan ya sa ya yiwu ba yin lissafi da amsa lokacin da suka hadu da sake tare da wannan sub-aiki.

Dynamic shirye-shirye aiki solves matsalar na ingantawa. Marubucin wannan hanya da aka tsara ta R. Bellman optimality manufa, abin da ke da farko Jihar kowane daga cikin matakai da kuma bayani a tsare a cikin wannan mataki, duk wadannan su zabi mafi kyau duka dangane da jihar, wanda ya yarda aka yi tsarin a karshen mataki.

A Hanyar inganta yi na ayyuka warware ta wajen bambance-bambancen karatu, ko recursion.

Building aiki algorithm

Dynamic shirye-shirye algorithm ya shafi gina irin wannan ayyuka da cewa aiki don haka ne raba biyu ko fiye subtasks zuwa ta bayani da aka hada da wani mafi kyau duka bayani ga dukkan subtasks, shi ya hada. Bugu da ari, shi wajibi ne don rubuta wani komawa aboki, da kuma kirga da ganiya siga dabi'u ga aiki a matsayin dukan.

Wani lokaci, a kan 3rd mataki shi ne ya haddace wasu ƙarin bango bayani a kan irin ci gaban da kowane aiki. Wannan shi ake kira da dawowar bugun jini.

aikace-aikace hanyar

Dynamic shirye-shirye ne amfani a lokacin da akwai guda biyu halayyar fasali:

• mafi kyau duka domin subtasks.
• gaban a matsalar da overlapping subproblems.

Gyaran ingantawa matsalar ta tsauri shirye-shirye, za ka farko da bukatar bayyana tsarin da bayani. The aiki yana zama mafi kyau duka idan da mafita da aka hada da mafi kyau yanke shawara na ta subtasks. A wannan yanayin, shi ne bu mai kyau don amfani tsauri shirye-shirye.

Na biyu dukiya daga cikin matsala, da muhimmanci a cikin wannan hanya, - karamin yawan sub-ɗawainiya. Recursive maganin matsalar yin amfani da wannan overlapping sub-matsaloli, da yawan wanda ya dogara a kan girman da farko bayani. Amsar da aka adana a cikin ta musamman tebur, da shirin kubutar da lokaci da yin amfani da wannan bayanai.

Musamman tasiri ne amfani da tsauri shirye-shirye a lokacin da aiki ne da gaske ake bukata don yin yanke shawara a saukarwa. Alal misali, ka yi la'akari da sauki misali na matsalar na sauyawa kuma gyara daga kayan aiki. Bari mu ce a kan zaben 'yan wasa inji factory domin samar da tayoyin a lokaci guda sa hula a biyu daban-daban siffofin. A cikin taron cewa daya daga cikin siffofin kasa, shi ne zama dole kwakkwance da na'ura. Shi ne m cewa wani lokaci mafi riba don maye gurbin da kuma wani na biyu form domin kwakkwance da na'ura in hali da kuma wannan tsari zai kasance unworkable a cikin gaba mataki. Musamman tun yana da sauki don maye gurbin biyu aiki siffar kafin su fara zuwa kasa. Dynamic shirye-shirye Hanyar kayyade mafi kyau dabarun a cikin al'amarin na sauyawa daga wadannan siffofin, shan la'akari duk da dalilai: amfanin ci gaba da siffofin amfani, asarar inji downtime, da kudin jefar da tayoyin da more.