تمرینات تحویلی درس طراحی و تحلیل الگوریتم ها

اعضای گروه:

کیان رضایی

علی داداش زاده

سید وحید عقیل زاده

سینا پیمان

مسئله کوله پشتی 0,1

مقدمه:

مسئله کوله پشتی 0,1 را میخواهیم به روش برنامه نویسی پویا حل کنیم. برنامه نویسی پویا یک روش قدرتمند حل مسئله به ویژه برای مسائل بهینه سازی میباشد. در برنامه نویسی پویا، ابتدا مسائل کوچک حل میشوند و در یک مکان ذخیره میشوند و سپس به تدریج به حل مسئله اصلی میرسیم. در این الگوریتم ها یک مسئله کوچک فقط یکبار محاسبه میشود. ابتدا به اجزایی که هر مسئله برنامه نویسی پویا احتیاج دارد، میپردازیم و سپس به کشف این اجزا در مسئله داده شده خواهیم پرداخت.
شباهت روش تقسیم و غلبه و برنامه نویسی پویا این است که هر دو نیاز به یک رابطه بازگشتی دارند و تفاوت آنها این است که روش تقسیم وغلبه مسئله را از بالا به پایین حل میکند، در صورتی که برنامه نویسی پویا آن را از پایین به بالا حل میکند. پس برای آنکه برنامه نویسی پویا بتواند مسائل را از پایین به بالا حل کند، نیاز به یک ماتریس (آرایه) دارد تا جواب زیر مسائل خود را داشته باشد. پس برای حل مسئله کوله پشتی 0,1 به روش برنامه نویسی پویا احتیاج به طرح یک فرمول بازگشتی و تعریف یک ماتریس داریم تا بعد از حل هر زیر مسئله مقدار آن را در ماتریس ذخیره کنیم.

مسئله کوله پشتی:

مسئله کوله پشتی 0,1 بدین شکل مطرح میشود:
یک دزد در هنگام دزدی از یک مفازه n شی پیدا میکند. i امین شی ، v_i دلار ارزش و w_i پوند ظرفیت دارد، که v_i و w_i اعداد صحیح هستند. او میخواهد با ارزش ترین بار ممکن را بر دارد، اما بیشترین باری را که میتواند در کوله پشتی اش حمل کند، W پوند است که که مقداری صحیح است. چه اشیایی را باید بردارد؟

حل مسئله کوله پشتی 0,1:

برای حل این مسئله هر بار کوله ای به ظرفیت w=0,...,W انتخاب میکنیم و سعی میکنیم با i شی اول کوله را به طوری پر کنیم که بیشترین سود حاصل شود. همانطور که در بالا گفته شد، برای حل به روش برنامه نویسی پویا به یک ماتریس نیاز داریم تا مقدار حل شده هر زیر مسئله را در آن قرار دهیم. ماتریسی به ابعاد n+1 سطر و W+1 ستون ایجاد میکنیم. که n تعداد اشیا و W ظرفیت کوله است. به عنوان مثال K[3][2] نشان دهنده کوله ای به ظرفیت 2 و 3 نشان دهنده ماکسیمم سود از انتخاب شی اول تا سوم است.

ماتریسی به ابعاد n+1 و W+1 ستون می سازیم:

K = [[0 for x in range(W + 1)] for x in range(n + 1)]

رابطه بازگشتی را به صورت زیر تعریف میکنیم:

if i == 0 or w == 0:
    K[i][w] = 0
elif wt[i - 1] <= w:
    K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
else:
    K[i][w]=K[i - 1][w]

شرط پایه: در صورتی که کوله پشتی به ظرفیت صفر داشته باشیم یا با صفر شی بخواهیم کوله را پر کنیم سود برابر صفر می شود.

if i == 0 or w == 0:
    K[i][w] = 0

رویه بازگشتی: در صورتی که جرم شی i ام کمتر مساوی ظرفیت کوله باشد، مقدار K[i][w] را برابر با ماکسیمم (ارزش شی i ام به اضافه ماکسیمم سود کسب شده با i-1 شی و ظرفیت کوله منهای جرم شی i ام خواهد شد یا ماکسیمم سود کسب شده با i-1 شی و ظرفیت w).
در غیر این صورت K[i][w] برابر باماکسیمم سود کسب شده با i-1 شی و ظرفیت w خواهد شد.

elif wt[i - 1] <= w:
    K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
else:
    K[i][w]=K[i - 1][w]

پیاده سازی نهایی الگوریتم:

def knapsack1():
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]

ظرفیت کوله پشتی : W
تعداد شی : n
جرم هر شی : wt
ارزش هر شی : val

مرتبه زمانی و حافظه مصرفی:

مرتبه زمانی : O(nW)
مرتبه حافظه مصرفی : O(nW)

بهینه کردن الگوریتم ارائه شده:

همانطور که در بالا دیدیم مرتبه زمان اجرا و مرتبه حافظه مصرفی O(nW) میباشد. اما در رویکرد جدید سعی میکنیم که مرتبه حافظه مصرفی را کاهش دهیم. در الگوریتم بالا برای هر شی یک سطر در نظر میگرفتیم و برای محاسبه سطر های بعد از سطر بالایی آن استفاده میکردیم، برای بهینه سازی میتوانیم فقط سطر آخر را ‌ذخیره کنیم و سطر جدید را روی همان سطر بازنویسی کنیم. در انتها Kp برابر با K[n] در الگوریتم قبل میشود و در این روش از n-1 سطر کمتر استفاده میشود که میزان حافظه استفاده شده برابر یک ماتریس با ابعاد 1 در w استفاده میشود.

پیاده سازی نهایی الگوریتم:

def knapsack2(W, wt, val, n):
    Kp = [0 for i in range(W + 1)]

    for i in range(1, n + 1):
        for w in range(W, 0, -1):
            if wt[i - 1] <= w:
                Kp[w] = max(K[w], Kp[w - wt[i - 1]] + val[i - 1])
            else:
                break
    return Kp[W]

مرتبه زمانی و حافظه مصرفی:

مرتبه زمانی : O(nW)
مرتبه حافظه مصرفی : O(W)

حل مسئله n کار بر روی m ماشین :

صورت مسئله :

-فرض کنید مجموعه ای از n کار را در اختیار داشته باشیم. هر کار i زمان اجرای p_i را دارد. می خواهیم این کارها را بر روی m ماشین اجرا کنیم به گونه ای که مجموع زمان اتمام کارها مینیمم شود. به عبارت دیگر تابع هدف به صورت زیر است :

که در آن c_i زمان اتمام کار i است. همه کارها در لحظه شروع در دسترس هستند و هر ماشین در هر لحظه بیش از یک کار نمی تواند انجام دهد.

حل مسئله به روش حریصانه :

یک الگوریتم حریصانه، همانطور که از اسم آن مشخص است، حریص است و همیشه انتخابی که در آن لحظه بهترین به نظر می‌رسد را بر می‌گزیند. به این معنی که انتخاب را به گونه ای انجام می دهد که به صورت محلی و در همان موقعیت بهینه باشد، به امید آن که این انتخاب باعث شود جواب نهایی هم بهینه شود. تصور کنید که شما یک تابع هدف (objective function) دارید که لازم است مقدار نهایی آن در نقطه ای بهینه شود (بیشینه یا کمینه). یک الگوریتم حریصانه در هر مرحله یک انتخاب طمع کارانه انجام می دهد تا مطمئن شود تابع هدف بهینه شده است. الگوریتم حریصانه برای به دست آوردن مقدار بهینه فقط یک شانس دارد چرا که نمی تواند به عقب برگردد و انتخاب های قبلی را تغییر دهد. پس در طراحی الگوریتم با تکنیک حریصانه، پس از مشخص و تعریف شدن تابع هدف، در هر مرحله باید سعی کرد بیشتر/کمترین مقدار را برای تابع به دست آورد. ابتدا ایده حل مسئله داده شده را مطرح میکنیم و روی یک مثال توضیح میدهیم که چرا رویکرد ما حریصانه است. ایده الگوریتم به شرح زیر است : ابتدا n کار را برحسب p_iها به صورت صعودی در یک لیست مرتب میکنیم و از کوچکترین عضو لیست ایجاد شده شروع به تخصیص کار به تک تک ماشین ها میکنیم. یعنی m کار اول به m ماشین تخصیص داده میشود و کار m+1 مجدد به ماشین اول تخصیص داده میشود.

چرا الگوریتم معرفی شده حریصانه است؟

با یک مثال سعی میکنیم نشان دهیم که چرا رویکرد معرفی شده حریصانه است. فرض کنید n=5 کار و m=3 ماشین داریم:

در گام اول تمامی هیچ کاری به ماشینی اختصاص نیافته است. با ماشین اول شروع میکنیم. میخواهیم کاری را انتخاب کنیم که در همین مرحله جواب مورد نظر ما باشد یعنی مجموع c_i آن مینیمم باشد. از کارها بدیهی است که باید کار a را به ماشین اول اختصاص دهیم. زیرا c_i=1 خواهد بود و در صورتی که کار دیگری انتخاب میکردیم این مقدار بیشتر میشد. حال در مرحله بعدی برای ماشین دوم میخواهیم کاری را انتخاب کنیم که در همین مرحله کمترین مقدار c_i را داشته باشد. پس کار b را به ماشین دوم میدهیم. این رویکرد نشان میدهد که ما در هر مرحله جواب بهینه ممکن را صرف نظر از جواب نهایی در نظر میگیریم که همان رویکرد حریصانه است. حال فرض کنید سه کار اول به سه ماشین اختصاص یافته است. در تخصیص کار بعدی به ماشین اول دو حالت ممکن را بررسی میکنیم : اگر کار d را به ماشین اول بدهیم، مجموع c_i ها در این ماشین برابر 1+5=6 خواهد بود. در صورتی که اگر کار e را به ماشین اول تخصیص میدادیم این مقدار برابر 1+6=7 می بود که با رویکرد حریصانه در تضاد است. پس الگوریتم به این صورت است که کار ها را ابتدا بر حسب p_i ها به صورت صعودی مرتب میکنیم و به ترتیب از ابتدا کار ها به ماشین ها میدهیم.

پیاده سازی نهایی الگوریتم:

def greedy(n, m, p):
    ans = 0
    machines = [[0] for _ in range(m)]
    for w, i in zip(p, range(n)):
        machines[i % m].append(w + machines[i % m][-1])
        ans += machines[i % m][-1]
    m = [0]
    return ans

حل مسئله به روش برنامه نویسی پویا :

همانطور که در بالا ذکر شد برای حل یک مسئله به روش برنامه نویسی پویا به یک ماتریس و یک رابطه بازگشتی نیاز است. ابتدا ماتریسمان را تعریف میکنیم و سپس به وسیله رابطه بازگشتی سعی در پر کردن عناصر این ماتریس داریم. ماتریس دارای ابعاد m*n که m نشان دهنده تعداد ماشین ها و n نشان دهنده تعداد کارها است . dp[3][5] نشان دهنده ماشین سوم و کار پنجم است. حال رابطه بازگشتی مسئله را بررسی میکنیم.
یک ماتریس به نام dp با ابعاد m*n میسازیم :

dp = [[0 for _ in range(n)] for _ in range(m)]

چون زمانی که i=j است هر کار به یک ماشین تخصیص داده میشود پس مجموع اتمام زمان کار ها برابر مجموع زمان خود کار ها است:

if i == j:
    dp[i][j] = dp[i][j - 1] + p[j]

در صورتی که i>j باشد یعنی تعداد ماشین ها بیشتر از کار هاست که باید با عنصر بالایی خود پر شود:

elif i > j:
    dp[i][j] = dp[i - 1][j]

و درصورتی که هیچکدام برقرار نبود (یا i کوچکتر از j بود)، عنصر مورد نظر برابر است با یک عنصر قبل خود به اضافه تفاضل i-1 ستون قبل خود و i-2 ستون قبل خود بعلاوه کار j ام (p_j)

else:
    dp[i][j] = dp[i][j - 1] + (dp[i][j - i - 1] - dp[i][j - i - 2]) + p[j]

پیاده سازی نهایی کد:

def dp(n, m, p):
    dp = [[0 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == j:
                dp[i][j] = dp[i][j - 1] + p[j]
            elif i > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1] + (dp[i][j - i - 1] - dp[i][j - i - 2]) + p[j]
    return dp[-1][-1]

kiyan-rezaee/knapsack-and-n-job-m-machine

تمرینات تحویلی درس طراحی و تحلیل الگوریتم ها

اعضای گروه:

مسئله کوله پشتی 0,1

پیاده سازی نهایی الگوریتم:

بهینه کردن الگوریتم ارائه شده:

پیاده سازی نهایی الگوریتم:

پیاده سازی نهایی الگوریتم: