انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Greedy method

Share |
الكلية كلية تكنولوجيا المعلومات     القسم قسم البرامجيات     المرحلة 4
أستاذ المادة احمد خلفة عبيد العجيلي       2/14/2012 5:08:56 PM


تستخدم هذه الطريقة غالبا لحل مسائل الامثلية (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)

Algorithm GreedyKnapsack(P, W, C, n):
Input: Positive integers n and C; arrays w[1:n] and
p[1:n], and each containing positive real sorted
in nonincreasing order according to the values of
p[i]/w[i].
Output: an array x[1:n] where 0?xi?1; an real maxprofit
that is the maximum profit
1. for i 1 to n
2. x[i] 0.0
3. endfor
4. U C
5. maxprofit 0.0
6. for i 1 to n
7. if w[i]>U then goto step 13
8. x[i] 1.0
9. U U-w[i]
10. maxprofit maxprofit + p[i]
11. endif
12. endfor
13. if i ? n then
14. x[i] U/w[i]
15. maxprofit maxprofit + p[i]*x[i]
16. endif
17. return array x and maxprofit

تتطلب هذه الخوارزمية بغض النظر عن وقت ترتيب الكيانات ابتدائيا O(n) من الوقت فقط. حيث تعطي هذه الخوارزمية حلا امثل دائما. لمسألة (0/1 kanpsack) تحذف تعليمة if الاخيرة وفي هذه الحالة لن يكون هناك ضمان للحصول على حل امثل.


المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
download lecture file topic