طريقة الطماع (Greedy method)

ب) طريقة الطماع (Greedy method)

تستخدم هذه الطريقة غالبا لحل مسائل الامثلية (optimization problem). لهذه المسائل تعطى مجموعة قيود(constraints) ودالة هدف (objective function). مجموعة الحلول التي تحقق القيود تسمى حلولا ممكنة(feasible solution) والحل الممكن الذي يعطي افضل دالة هدف يسمى الحل الامثل(optimal (solution.

ملاحظة / اغلب المسائل التي تحلها طريقة الطماع تتكون من n من المداخل.

الفكرة/ يبنى الحل الامثل في طريقة الطماع على مراحل. في كل مرحلة يتخذ افضل قرار تبعا لمقياس امثلية مناسب (مقياس الطماع). وحيث ان القرار المتخذ لن يتغير لاحقا لذا يجب ان يضمن امكانية الحل.

يوجد نموذجان لطريقة الطماع :-
1) نموذج المجموعة الجزئية(Subset paradigm):- في هذا النموذج يتم انتقاء مجموعة جزئية مثلى من المدخلات تبعا لمقياس امثلية معين ويجب ان تحقق هذه المجموعة قيود المسالة. التجريد الضبطي التالي يوضح عمل هذا النموذج:
SolType Greedy(Type a[ ], int n)
// a[1:n] contains the n inputs.
{
SolType solution=Empty; // initialize the solution.
for(int i=1; i<=n; i++){
Type x=Select(a);
if feasible(solution, x)
solution=Union(solution, x);
}
return solution;
}
2) نموذج الترتيب(Ordering paradigm): في هذا النموذج يتم اتخاذ القرارات باعتبار المدخلات بترتيب معين. كل قرار يتم اتخاذه باستخدام مقياس للامثلية والذي يمكن حسابه من خلال القرارات المتخذه مسبقا.

امثلة على طريقة الطماع:-

1- مسألة الجراب(Knapsack problem)

المعطيات:
- n من الكيانات.
- جراب سعته C.
- للكيان i الوزن wi (1?i?n).
- اضافة الكسر xi (0?xi?1) يحقق فائدة pixi.
المطلوب:
ملء الجراب بحيث تعظم الفائدة الحاصلة.


- دالة الهدف
Maximize


- القيود

مثال/
C=20 , n=3 , P[1:3]=(25, 24, 15) , w[1:3]=(18, 15, 10)

توجد ثلاث حلول ممكنة باستعمال طريقة الطماع وكما مبين في الجدول التالي:

المقياس ?pixi ?wixi (x1, x2 , x3)
الفائدة الاعلى اولا 28.2 20 (1, 2/15, 0)
الوزن الاقل اولا 31 20 (0, 2/3, 1)
الفائدة الاكبر لكل وحدة وزن (pi/wi) اولا 31.5 20 (0, 1, 1/2)