Համակարգչային գիտության մեջ ասվում է, որ խնդիրն ունի համընկնող ենթախնդիրներ, եթե խնդիրը կարելի է բաժանել ենթախնդիրների, որոնք մի քանի անգամ օգտագործվում են, կամ խնդրի ռեկուրսիվ ալգորիթմը լուծում է նույն ենթախնդիրը անընդհատ, այլ ոչ թե միշտ նոր առաջացնել: ենթախնդիրներ։
Որո՞նք են դինամիկ ծրագրավորման օպտիմալ ենթակառուցվածքը և համընկնող ենթախնդիրները:
Խնդիրն ունի ենթակառուցվածքի օպտիմալ հատկություն, եթե տվյալ խնդրի օպտիմալ լուծումը կարելի է ստանալ՝ օգտագործելով նրա ենթախնդիրների օպտիմալ լուծումը: Դինամիկ ծրագրավորումն օգտվում է այս հատկությունից՝ լուծում գտնելու համար:
Ի՞նչ է համընկնող ենթախնդիրը դինամիկ ծրագրավորման մեջ:
1) Համընկնող ենթախնդիրներ․ Դինամիկ ծրագրավորման մեջ ենթախնդիրների հաշվարկված լուծումները պահվում են աղյուսակում, որպեսզի դրանք նորից չհաշվարկվեն:
Ո՞րն է տարբերությունը օպտիմալ ենթակառուցվածքի և համընկնող ենթախնդիրների միջև:
Ես հասկանում եմ թիրախային մոտեցումը երկու մեթոդների համար, որտեղ Optimal Substructure-ը հաշվարկում է օպտիմալ լուծումը՝ հիմնվելով n-ի վրա, մինչդեռ Overlapping Subproblems-ը թիրախավորում է բոլոր լուծումները մուտքային տիրույթի համար, ասենք 1-ից մինչև n:այնպիսի խնդրի համար, ինչպիսին է Ձողերի կտրման խնդիրը:
Այս տեխնիկաներից ո՞րն է օգտագործում ենթախնդիրների համընկնումը:
Դինամիկ ծրագրավորումը համընկնող ենթախնդիրների հետ կապված խնդիրների լուծման տեխնիկա է: Սրանում մենք պահպանում ենք ենթախնդրի արդյունքը, որը լուծվում է մեկ անգամ՝ հետագա օգտագործման համար: Ենթախնդիրների լուծումները պահելու տեխնիկան կոչվում է հիշողություն։
