ගතික වැඩසටහන්, මූලික මූලධර්ම

ප්රශස්ත විසඳුම තෝරා ගැනීමට සිදු වූ විට වැඩසටහන් කාර්යයන් සමහර විට පෞද්ගලික පරිගණකය මතකයේ පටවන දත්ත සංයෝජන විශාල ප්රමාණයක් නිරාකරණය කිරීම අවශ්ය වේ. එවැනි ක්රම "බෙදා පාලනය" කිරීමේ වැඩසටහන් ක්රමය, උදාහරණයක් ලෙස, අඩංගු වේ. මෙම අවස්ථාවේ දී මෙම ඇල්ගොරිතමය වෙනම කුඩා අනුකොටස් කොටස්වලට වෙන් ප්රශ්නය සපයයි. එකම කුඩා අනුකොටස් අන්යෝන්ය වශයෙන් ස්වාධීන කොහෙද එවැනි අවස්ථාවන්හිදී මෙම ක්රමය යෝග්ය වේ. එකිනෙකාට සහසම්බන්ධී ය උප කාර්යයන් නම්, අනවශ්ය කටයුතු කිරීමට වළක්වා ගැනීමට, ගතික ක්රමලේඛන ක්රමය 50s ඇමරිකානු R.Bellmanom යෝජනා භාවිතා කරයි.

මෙම ක්රමය

ගතික ක්රමලේඛන ඇය n වෙනම අවස්ථා හුවමාරු, ප්රශස්ත විසඳුම n-මාන ප්රශ්නය තීරණය කිරීම සඳහා වේ. ඔවුන් එක් එක් එක් විචල්ය සම්බන්ධයෙන් උප කාර්යයකි.

මෙම ප්රවේශය වල ඇති ප්රධාන වාසිය වන්නේ නිර්මාණකරුවන් ඒක මාන ප්රශස්තිකරණය ප්රශ්නය සම්බන්ධ බව සැලකිය හැකිය වෙනුවට n-මාන ප්රශ්නය අනුකොටස්, අපගේ මුලික අරමුණ "ආරෝහණ" යන්නේ.

එය, උප-කාර්යයන් සම්බන්ධයි වූ එම අවස්ථාවල දී ගතික ක්රමලේඛන අයදුම් කිරීමට ඉතා යෝග්ය වේ එනම් පොදු මොඩියුල බෙදා ගන්න. මෙම ඇල්ගොරිතමය වරක් අනුකොටස් එක් එක් තීරණය සපයන හා, ප්රතිචාර ඉතිරි විශේෂ වගුවේ සිදු කෙරේ. මෙය ඔවුන් එම උප කාර්යය නැවත හමු වූ විට පිළිතුර ගණනය කිරීමට නොහැකි හැකි වේ.

ගතික ක්රමලේඛන කාර්ය ප්රශ්නය සිදුවීමක්ම සමාජමය සහ ප්රශස්තිකරණය ය. ආර් Bellman optimality මූලධර්මය විසින් මෙම ක්රමය කතුවරයා සකස් ය: සියලු පියවර අවසානයේ පද්ධතිය ලැබෙන රාජ්ය, සම්බන්ධයෙන් ද ප්රශස්තම තෝරා ගැනීමට පහත සඳහන්, සහ පියවර මෙම පියවර අර්ථ විසඳුම එක් එක් මූලික රාජ්ය ඕනෑම.

මෙම ක්රමය ප්රභේද මාර්ගයෙන්, හෝ සහානුයාත වලට මඟින් විසඳා ඇති කාර්යයන් කාර්ය සාධනය වැඩි දියුණු කරන ලදි.

ගොඩනැගිල්ල කාර්ය ඇල්ගොරිතමය

ගතික ක්රමලේඛන ඇල්ගොරිතමය කර්තව්යය නිසා එහි විසඳුමක් සඳහා දෙකක් හෝ ඊට වැඩි අනුකොටස් බෙදී ඇත එවැනි කාර්යයන් ඉදිකිරීම් සම්බන්ධ සියලු අනුකොටස් කිරීමට ප්රශස්ත විසඳුම සමන්විත වේ, එය ඇතුළත් වේ. තවදුරටත්, එය නැවත ඇති සම්බන්ධය ලිවීමට අවශ්ය වන අතර, සමස්තයක් ලෙස කාර්යය සඳහා ප්රශස්ත පරාමිතිය වටිනාකම් ගණනය.

සමහර විට, 3 වන පියවර එක් එක් කාර්ය ප්රගතිය පිළිබඳ සමහර අතිරේක පසුබිම් තොරතුරු මතක තබා ගැනීම සඳහා ය. මෙම නැවත ආඝාතය ලෙස හැඳින්වේ.

කමය

ලක්ෂණ දෙකක් තිබේ විට ගතික ක්රමලේඛන ආලේප කරයි:

• අනුකොටස් සඳහා ප්රශස්ත;
• subproblems අතිච්ඡාදනය වන ප්රශ්නය ද වර්තමානයේ දී.

ගතික ක්රමලේඛන විසින් ප්රශස්තිකරණය ප්රශ්නය විසඳීම, ඔබ මුලින්ම විසඳුමක් ව්යුහය විස්තර කිරීමට අවශ්ය වේ. කර්තව්යය විසඳුම එහි අනුකොටස් හොඳම තීරණ සමන්විත වේ නම් ප්රශස්ත විය යුතුව තිබේ. මේ අවස්ථාවේ දී, එය ගතික ක්රමලේඛන භාවිතා කිරීමට ඉතා යෝග්ය වේ.

ප්රශ්නය දෙවන දේපල, මෙම ක්රමය අත්යවශ්ය, - උප-කාර්යයන් ඉතා සුළු ප්රමාණයක්. එම අතිච්ඡාදනය උප ගැටළු, මූලික තොරතුරු ප්රමාණය මත පදනම් වන සංඛ්යාව භාවිතා කරමින් ප්රශ්නය ආවර්තනික විසඳුමක්. පිළිතුර විශේෂ වගුවේ ගබඩා කර ඇත, මෙම වැඩසටහන මෙම දත්ත භාවිතා කරමින් කාලය ඉතිරි.

විශේෂයෙන් ඵලදායී කර්තව්යය අදියරවල තීරණ ගැනීමට අවශ්යයෙන්ම අවශ්ය විට ගතික ක්රමලේඛන භාවිතයයි. උදාහරණයක් ලෙස, ප්රතිස්ථාපනය සහ උපකරණ අළුත්වැඩියා කිරීම පිළිබඳ ප්රශ්නය සරල උදාහරණයක් සලකා බලන්න. ගේ එම අවස්ථාවේ දී ටයර් නිෂ්පාදනය සඳහා වාත්තු යන්ත්රය කර්මාන්ත ශාලාව ගැන කියන්න විවිධ ආකාර දෙකක් ටයර් කිරීමට අපි කටයුතු කරමු. ආකෘති එක් අසමත් බව මෙම අවස්ථාවට, එය යන්ත්රය disassemble අවශ්ය ය. එය නඩුවේ යන්ත්රය disassemble හා මෙම ආකෘති පත්රය ඊලඟ අදියර තුළ වැඩිවිය හැක පිණිස සමහර විට වඩාත් ලාභදායී වෙනුවට බව අවබෝධ කරගත හා දෙවන ආකාරයකි. ඔවුන් අසමත් කිරීමට ආරම්භ කිරීමට පෙර ඒ දෙකම වැඩ හැඩය වෙනුවට කිරීමට පහසු වේ, විශේෂයෙන්ම සිට. සූරාකෑම දිගටම රූපයන් ප්රතිලාභ, යන්ත්ර පැමීණෙන අහිමි වීම, ඉවතලන ටයර් සඳහා යන පිරිවැය හා වඩා: ගතික ක්රමලේඛන ක්රමය සැලකිල්ලට සියලු සාධක සැලකිල්ලට ගනිමින්, මෙම ආකෘති ආදේශ කිරීම යන කාරණය හොඳම උපාය තීරණය කරයි.