persdollar
جمعه 09 دی 1390, 09:41 صبح
با سلام. من مشکلی داشتم، که احتیاج به کمک شما دوستان دارم. خواهش می کنم تمام کسانی که می تونن در حل این مشکل من را یاری کنند.
صورت مسئله را در ادامه واستون شرح می دهم. ببینید ما تعدادی فعالیت داریم که هر یک برای انجام احتیاج به تعدادی منبع دارند. تعداد فعالیت ها و منابع در هر بار اجرا متغیر است و تعداد آنها می تونه زیاد باشه.هر فعالیت تنها با در اختیار گرفتن تمامی مورد نیازش قابل اجراست.
فرض کنید 4 تا فعالیت با نام های A،B،C،D و 10 منبع با نام های r1 تا r10 داریم. که البته از هر یک از منابع تعدادی موجود می باشد. به عنوان مثال:
از r1 تعداد 14 تا داریم.
از r2 تعداد 4 تا داریم.
از r3 تعداد 32 تا داریم.
.
.
.
حال فرض کنید هر یک از فعالیت های ما برای انجام به تعدادی از این منابع احتیاج دارند. به عنوان مثال:
A به 5 تا r1، 3 تا r7، 2 تا r10 احتیاج دارد.
B به 12 تا r2، 12 تا r1، 5 تا r6، 3 تا r7، 2 تا r9، 2 تا r10 دارد.
C به 6 تا r6 احتیاج دارد.
D به 3 تا r8 احتیاج دارد.
هر یک از فعالیت ها تنها در صورتی قابل اجرا هستند که تمامی منابعشان را در اختیار داشته باشند. واضح است که ممکن است به دلیل کمبود منابع تمامی فعالیت ها نمی توانند اجرا گردند.
حال ما به دنبال مکانیزمی هستیم که با منابع موجود فعلی بتوانیم حداکثر کار ممکن را، از نظر تعداد انجام دهیم. حل این مسئله وقتی تعداد فعالیت ها و تعداد منابع (از لحاظ تعداد نوع ) زیاد می شود، تبدیل به یک np-complete می شه.
حالا از دوستان می خوام که زحمت بکشن، اگه راه حلی به نظرشون می رسه، بیان کنن (ژنتیک، تخصیص منابع، ...).
با تشکر از تمامی دوستان.
صورت مسئله را در ادامه واستون شرح می دهم. ببینید ما تعدادی فعالیت داریم که هر یک برای انجام احتیاج به تعدادی منبع دارند. تعداد فعالیت ها و منابع در هر بار اجرا متغیر است و تعداد آنها می تونه زیاد باشه.هر فعالیت تنها با در اختیار گرفتن تمامی مورد نیازش قابل اجراست.
فرض کنید 4 تا فعالیت با نام های A،B،C،D و 10 منبع با نام های r1 تا r10 داریم. که البته از هر یک از منابع تعدادی موجود می باشد. به عنوان مثال:
از r1 تعداد 14 تا داریم.
از r2 تعداد 4 تا داریم.
از r3 تعداد 32 تا داریم.
.
.
.
حال فرض کنید هر یک از فعالیت های ما برای انجام به تعدادی از این منابع احتیاج دارند. به عنوان مثال:
A به 5 تا r1، 3 تا r7، 2 تا r10 احتیاج دارد.
B به 12 تا r2، 12 تا r1، 5 تا r6، 3 تا r7، 2 تا r9، 2 تا r10 دارد.
C به 6 تا r6 احتیاج دارد.
D به 3 تا r8 احتیاج دارد.
هر یک از فعالیت ها تنها در صورتی قابل اجرا هستند که تمامی منابعشان را در اختیار داشته باشند. واضح است که ممکن است به دلیل کمبود منابع تمامی فعالیت ها نمی توانند اجرا گردند.
حال ما به دنبال مکانیزمی هستیم که با منابع موجود فعلی بتوانیم حداکثر کار ممکن را، از نظر تعداد انجام دهیم. حل این مسئله وقتی تعداد فعالیت ها و تعداد منابع (از لحاظ تعداد نوع ) زیاد می شود، تبدیل به یک np-complete می شه.
حالا از دوستان می خوام که زحمت بکشن، اگه راه حلی به نظرشون می رسه، بیان کنن (ژنتیک، تخصیص منابع، ...).
با تشکر از تمامی دوستان.