Dinamiese programmering, die basiese beginsels

Om die optimale oplossing te kies wanneer die uitvoering van die program take word soms nodig om groot hoeveelhede data kombinasies wat die geheue van die persoonlike rekenaar laai sorteer. Sulke metodes sluit in, byvoorbeeld, die ontwikkeling metode van "verdeel en heers". In hierdie geval is die algoritme bied skeiding probleem in aparte kleiner subtake. Hierdie metode is slegs in daardie gevalle waar klein subtake onderling onafhanklike toepassing. Om te verhoed dat die uitvoering van onnodige werk as interafhanklik sub-take, gebruik dinamiese voorgestelde Amerikaanse R.Bellmanom in die 50s ontwikkeling metode.

die metode

Dinamiese programmering is om die optimale oplossing te bepaal die N-dimensionele probleem, deel haar n aparte fases. Elkeen van hulle is 'n sub-taak met betrekking tot een veranderlike.

Die grootste voordeel van hierdie benadering kan beskou word dat die betrokke in die een-dimensionele optimeringsprobleem ontwikkelaars subtake in plaas van 'n N-dimensionele probleem, en ons primêre doel gaan "bottom-up".

Dit is raadsaam om dinamiese programmering toe te pas in daardie gevalle waar die sub-take met mekaar verband hou, met ander woorde gemeenskaplike modules. Die algoritme bied die beslissing van elk van die subtake keer, en besparing antwoorde word uitgevoer in 'n spesiale tafel. Dit maak dit moontlik 'n antwoord nie om te bereken wanneer hulle weer ontmoet met dieselfde sub-taak.

Dinamiese programmering taak los die probleem van optimalisering. Die skrywer van hierdie metode is geformuleer deur R. Bellman optimaliteit beginsel: alles wat die aanvanklike toestand van elk van die stappe en die omskryf in hierdie stap oplossing, al die volgende om die optimale kies met betrekking tot die staat, wat die stelsel aan die einde van stap ontvang.

Die metode verbeter die prestasie van die take opgelos deur middel van variante, of rekursie.

Gebou taak algoritme

Dinamiese programmering algoritme behels die bou van sulke take wat die taak so is verdeel in twee of meer subtake om sy oplossing is saamgestel uit 'n optimale oplossing vir al subtake, dit sluit. Verder, is dit nodig om 'n herhaling verhouding skryf, en die berekening van die optimale parameter waardes vir die taak as 'n geheel.

Soms, op die 3de stap is om 'n paar ekstra agtergrondinligting oor die vordering van elke taak te memoriseer. Dit staan bekend as die terugkeer beroerte.

aansoek metode

Dinamiese programmering toegepas wanneer daar twee kenmerkende eienskappe:

• optimaal vir subtake;
• teenwoordigheid in die probleem van oorvleuelende subprobleme.

Die oplossing van die optimalisering probleem deur dinamiese programmering, moet jy eers die struktuur van die oplossing beskryf. Die taak het optimale te wees as die oplossing is saamgestel uit die beste besluite van sy subtake. In hierdie geval, is dit raadsaam om dinamiese programmering te gebruik.

Die tweede eiendom van die probleem, wat noodsaaklik is in hierdie metode, - 'n klein aantal sub-take. Rekursiewe oplossing van die probleem met behulp van dieselfde oorvleueling sub-probleme, die aantal wat afhanklik is van die grootte van die aanvanklike inligting. Die antwoord is gestoor in 'n spesiale tafel, die program spaar tyd deur die gebruik van hierdie data.

Veral effektief is die gebruik van dinamiese programmering wanneer die taak in wese is wat nodig is om besluite te neem in stadiums. Byvoorbeeld, oorweeg 'n eenvoudige voorbeeld van die probleem van vervanging en herstel van toerusting. Kom ons sê oor die beslissende masjien fabriek vir die vervaardiging van bande op dieselfde tyd maak die band in twee verskillende vorme. In die geval dat een van die vorms in gebreke bly, is dit nodig om die masjien te onderwerp. Dit is te verstane dat dit soms meer winsgewend te vervang en 'n tweede vorm ten einde die masjien te onderwerp in geval en hierdie vorm sal onwerkbaar in die volgende fase wees. Veral omdat dit makliker is om beide werk vorm te vervang voordat hulle begin om te misluk. Dinamiese programmering metode bepaal die beste strategie in die saak van die vervanging van hierdie vorme, met inagneming van al die faktore: die voordele van die voortsetting van vorms van uitbuiting, verlies van masjien stilstand, die koste van weggegooi bande en nog baie meer.