Алгоритмҳои ҳарисона
Муҳокимаи алгоритмҳои ҳирсона стратегияҳо мебошанд
Алгоритмҳои ҳирисона стратегияҳое мебошанд, ки ҳалли масъаларо қадам ба қадам месозанд ва дар ҳар қадам варианти оптималии маҳаллӣ-ро интихоб мекунанд, бо умеди расидан ба натиҷаи оптималии глобалӣ. Онҳо пурқувват, содда ва аксар вақт нисбат ба барномасозии динамикӣ ё ҷустуҷӯи пурра хеле тезтаранд, аммо танҳо вақте кор мекунанд, ки масъала баъзе хосиятҳои сохториро қонеъ кунад (масалан, зерсохтори оптималӣ ва ``хосияти интихоби ҳирисона'').
Дар бисёр масъалаҳои классикӣ (банақшагирии фосилаҳо, кам кардани вақти интизорӣ, интихоби фаъолият, рамзгузории Ҳаффман), исбот шудааст, ки алгоритмҳои ҳирисона ҷавобҳои оптималӣ медиҳанд. Дар барномасозии рақобатӣ, мушкили асосӣ шинохтани он аст, ки кай ҳирисонагӣ дуруст аст ва меъёри дурусти ҳирисона кадом аст.
Ҳалҳои дурусти ҳирисона одатан ба исботҳо такя мекунанд, ба монанди:
- Далели мубодила: нишон додан, ки ҳар ҳалли оптималиро метавон аз нав тартиб дод, то қадамҳои ҳирисонаро пайравӣ кунад.
- Далели пешсаф мондан: нишон додан, ки ҳалли ҳирисона ҳамеша ҳадди ақал ба андозаи ҳар ҳалли қисмии дигар хуб аст.
Мисоли 1: Масъалаи интихоби фаъолият
Масъала: Ба шумо фаъолият бо вақтҳои оғоз ва анҷом дода шудааст. Шумораи максималии фаъолиятҳои беҳампӯшро интихоб кунед.