انتخاب بهینه فعالیت‌ها

مسئله انتخاب فعالیت‌ها از مسائل بهینه‌سازی ریاضی است که می‌توان برای آن الگوریتمی به روش حریصانه تولید کرد. برای نمونه فرض کنید n سخنران خود را به عنوان ورودی مسئله اعلام کرده‌اند. هدف انتخاب بیشترین تعداد سخنران به گونه‌ای است که هیچ دو سخنرانی با هم اشتراک بازهٔ زمانی نداشته باشند.

جهت عدم تداخل در زمان شروع یا پایان می‌توان بدون کم‌شدن از کلیت مسئله فرض کرد که پایان بازه سخنرانی‌ها باز است یعنی به صورت (...} است.

ورودی‌ها:

• si :شروع فعالیت iام
• Fi :پاین فعالیت iام
• n :تعداد فعالیت‌ها
• هدف : انتخاب بیشترین تعداد فعالیت به قسمی که اشتراک بازه زمانی نداشته باشند.

توضیح الگوریتم:

1. در ابتدا فعالیت‌ها را بر اساس زمان پایان آن‌ها مرتب کرده و سپس اولین فعالیت (زودترین زمان پایان) را انتخاب می‌کنیم.
2. به ازای i از 2تا n مرحله 3 را تکرار می‌کنیم
3. اگر فعالیت iام با آخرین فعالیت انتخاب شده تداخل بازه زمانی نداشت آن را انتخاب می‌کنیم.

شبه کد الگوریتم را در زیر می‌بینیم (فرض بر این است که فعالیت‌ها بر حسب صعودی زمان پایانشان مرتب شده‌اند):

Procedure Activity_selector (A, S, F, n) 
A {1} 
j 1 
for i 2 to n do 
if Si ≥Fj
then 
A   A ∪{i} 
j i 
endif 
repeat 
end.

تطابق با روش حریصانه: فعالیتی که زودترین زمان پایان را داشته باشد

Select :

با آخرین فعالیت انتخاب شده تداخل زمانی نداشته باشد

Feasibility :

اضافه کردن آن به مجموعه انتخاب شده‌ها

Union :

تحلیل زمانی :بیشترین زمان در الگوریتم مربوط به مرتب سازی ابتدای کار است و لذا الگوریتم دارای مرتبه زمانی (o(n log n می‌باشد.

منابع

www.prozhe.com *

www.irandisheh.com *

www.nooreaseman.com *

www.iran-stu.com *