سال انتشار: ۱۳۹۱

محل انتشار: کنفرانس بین المللی مدل سازی غیر خطی و بهینه سازی

تعداد صفحات: ۱۰

نویسنده(ها):

وحیده پرتوی –
جواد وحیدی –

چکیده:

مسئله کوله پشتی از مسائل شناخته شده می باشد.یکی از انواع آن مسئله subset_sum است که از نوع مسائل NP-Hard می باشد.ارائه راه کار موازی برای حل این مسئله در پیچیدگی زمانی کمتر هدف این مقاله است.برای این کار از مدل PRAM استفاده کردیم تا بتوان آن را روی سخت افزارهای متفاوت اجرا کرد.این الگوریتم به تعداد پردازنده ها وابسته نیست. در فصل اول کارهای وابسته به موضوع بررسی شده.و در فصل دوم الگوریتم پیشنهادی معرفی می شود.در فصل سوم یک مثال با آن حل میشود.