آموزش طراحی و تحلیل الگوریتم قسمت هشتم

1395/1/18 --- 2475

به نام خدا

سلام عرض میکنم خدمت همه ی شما دوستان عزیز

با جلسه ی هشتم از سری آموزش های طراحی و تحلیل الگوریتم ها در خدمت شما هستم .

در این جلسه قصد داریم درباره ی مسئله ی کوله پشتی و کمی هم کد هافمن صحبت کنیم و در آخر اشاره ای به رویکرد عقبگرد در الگوریتم ها خواهیم داشت .

ببینید دوستان ، همونطور که در جلسه ی قبل خدمت شما عرض کردم ، مسئله ی کوله پشتی ، دارای 2 شکل هست یا بهتره بگم 2 نوع . یکی کوله پشتی "صفر و یک" هست و دیگری کوله پشتی "کسری" هست . الان میخوایم هر دو نوع رو توضیح بدیم . این مسئله میتونه یک مثال خوب برای مقایسه ی دو روش "برنامه ریزی پویا" و "رویکرد حریصانه" باشه .

اول کوله پشتی صفر و یک رو بررسی میکنیم :

فرض کنید میخوایم به مسافرت بریم و فقط میتونیم یک کوله پشتی با خودمون ببریم . یک سری وسایل هم در اختیار ما هست که با توجه به ظرفیت کوله پشتی چند تا رو میتونیم انتخاب کنیم . هر وسیله ای هم دارای ارزش خاص خودش هست . هدف ما این هست که وسایل رو طوری انتخاب کنیم که هم بیشترین ارزش رو داشته باشند و هم از ظرفیت کوله فراتر نریم . هر وسیله هم یا انتخاب میشه و یا انتخاب نمیشه . برای همین دو وضعیت صفر و یک داریم ! .

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

فرض کنیم n وسیله داریم به طوری که مجموعه ی L شامل این وسایل باشه :

L={item1 , item2 , …. , item n{

 

نشان دهنده ی وزن وسیله ی i ام هست .(wi)

 نشان دهنده  ی ارزش وسیله ی i ام هست .(pi)

ظرفیت کوله پشتی هست .(W)

کاملا هم واضح هست که مجموعه وزن همه ی اشیا ی انتخاب شده باید کمتر یا مساوی W باشند و این یک شرط  هست .همچنین باید وسایل طوری انتخاب بشن که علاوه بر رعایت کردن این شرط ، بیشترین ارزش ممکن ( مجموعه ارزش های اشیا ) بیشترین مقدار ممکن بشه .

یک راه حل کلی برای حل چنین مسئله ای ، این هست که بیایم همه ی زیر مجموعه های مجموعه ی L رو به دست بیاریم و اونایی که دارای مجموع وزن بیشتر از W هستند رو کنار بذاریم و برای بقیه ی زیرمجموعه مقدار مجموع ارزش ها رو حساب کنیم و بیشترین رو انتخاب کنیم . از طرفی ما میدونیم که تعداد زیرمجموعه های یک مجموعه ی n عضوی ، 2 به توان n هست . پس میتونیم بگیم که چنین راه حلی دارای پیچیدگی حداقل 2 به توان n هست .

حالا رویکرد حریصانه رو انتخاب میکنیم . مفهوم رویکرد حریصانه چی بود؟ الان توی این مثال رویکرد حریصانه چیکار میکنه ؟ ببنید دوستان مگه ملاک و معیار این مسئله و درواقع هدف مسئله ، ارزش وسایل نیست؟ خب بنابراین هدف ما ماکسیمم سازی ارزش وسایل و شرط ما فراتر نرفتن از گنجایش و ظرفیت کوله پشتی هست . بنابراین به دو کلمه ی "هدف" و "شرط" دقت کنید . رویکرد حریصانه هم میاد "بهترین" انتخاب رو در هر مرحله با توجه به هدف مسئله انتخاب میکنه . حالا توی این مسئله ی کوله پشتی صفر و یک به این صورت میشه که چنین الگوریتمی میاد و  به ترتیب افزایش ارزش وسایل رو برمیداره . یعنی اول از همه میره سراغ اونهایی که ارزش بیشتری دارند . اما ما یه شرط دیگه هم داریم و همون مارو محدود میکنه . اونم گنجایش کوله هست . یعنی باید به وزن هم توجه داشت . چون گاهی ممکنه یک وسیله دارای ارزش زیادی باشه اما وزنش هم فوق العاده زیاد باشه . ولی شاید یک وسیله وجود داشته باشه که ارزشش کمتر از خیلی از وسایل دیگه باشه ولی وزنش ناچیز باشه . اینجا باید دید که شاید انتخاب جسم دومی بهتر باشه تحت یک شرایطی . چون نسبت ارزشش به وزنش خیلی خوبه .(البته این نسبت، خیلی قابل اطمینان نیس چون گاهی انتخاب شی اول بهتره . فقط با این نسبت خواستم بگم که نمیشه همیشه دنبال بیشترین ارزش بود .) الگوریتم حریصانه فقط به ارزش نگاه میکنه .

بیاید یه مثال عددی بزنیم . فرض کنیم 3 وسیله داریم . وسیله ی 1 دارای 23 کیلو وزن و ارزش 11 هست . وسیله ی 2 دارای 10 کیلو وزن و ارزش 8 هست و وسیله ی 3 هم دارای 10 کیلو وزن و ارزش 9 هست . همچنین ظرفیت کوله هم 30 کیلو هست . خب الگوریتم حریصانه میاد به خاطر ارزش بیشتر وسیله ی 1 رو اول انتخاب میکنه . ولی چون وزن 23 کیلو داره دیگه نمیتونیم وسیله ای رو انتخاب کنیم . در حالیه که میدونیم بهینه ترین حالت ، انتخاب وسایل 2 و 3 به صورت تواما هست که ارزش 17 رو برامون به ارمغان میاره .

خب یک راه هم اینه که به الگوریتم حریصانه یک هدف دیگه بدیم. یعنی بگیم به جای اینکه بیشترین ارزش رو انتخاب کنه ، کمترین وزن رو انتخاب کنه . یعنی درواقع معیار مسئله رو عوض کردیم . خب اینجا چه مشکلی وجود خواهد داشت ؟ خب به طریق مشابه ممکنه وسایل طوری باشند که اشیای سبک ، بسیار کم ارزش باشند . پس اینجا هم مسئله ، جواب بهینه رو نمیده .

یک راه هم اینه که بازم معیار رو عوض کنیم و بگیم ملاک اینه که نسبت ارزش به وزن تعیین کننده باشه . یعنی اونایی رو اول انتخاب کنیم که دارای نسبت ارزش به وزن بیشتری هستند . اینجا هم ممکنه به مشکل بر بخوریم . برای این هم میشه مثال عددی زد . فرض کنید شی 1 داری وزن 5 و ارزش 50 باشه . شی 2 دارای وزن 10 و ارزش 60 باشه .  شی 3 هم دارای وزن 20 و ارزش 140 باشه . خب کافیه ارزش رو تقسیم بر وزن کنیم که اگر نسبت رو A بگیریم ، A1 میشه 10 .  A2 میشه 6  و A3 میشه 7. حالا اگه گنجایش 30 کیلو باشه ، الگوریتم میاد اشیای 1 و 3 رو انتخاب میکنه .اینجا ارزش 150 رو داریم . ولی خب جواب بهینه انتخاب اشیا 2و3 هست که ارزش 200 رو خواهیم داشت .

پس دیدیم که دراین نوع از مسئله ، الگوریتم حریصانه به طور کامل جواب نمیده . البته این به این معنا نیست که اصلا جواب نمیده . ولی خب نمیتونیم بگیم همیشه جواب بهینه رو به ما خواهد داد . تنها کاری هم که میتونیم در این الگوریتم بکنیم ، تغییر در ملاک هست که اونم کارساز نبود . خب حالا بیایم الگوریتم برنامه ریزی پویا رو به کار بگیریم . ببینید دوستان اگه بتونیم ثابت کنیم که اصل بهینگی در اینجا برقرار هست ، اونوقت میتونیم بگیم که این مسئله رو میشه با استفاده از برنامه ریزی پویا حل کرد . فرض کنیم مجموعه ی S دارای یک زیرمجموعه ی بهینه از n شی باشه . خب اینجا دو حالت داریم :

حالت 1) مجموعه ی S دارای شی item n هست

حالت 2) مجموعه ی S دارای شی item n نیست .

در حالت 2 چی میشه ؟ مجموعه ی S با زیرمجموعه ی بهینه از n-1 شی اول برابر هست .

توی حالت یک چی میشه؟ سود کل حاصل از اشیای موجود در S برابر هست با Pn به علاوه ی سود بهینه در زمانی که بتوان اشیا را از n-1 شی اول انتخاب کرد . این رو هم در نظر داشته باشید که وزن کل نباید از W-Wn بیشتر بشه .حالا همین چیزایی که گفتیم رو به این صورت بیان میکنیم :

اگه برای iوw های مثبت ، P[i][w] سود بهینه ی حاصل از انتخاب i قطعه ی اول و شرط عدم تجاوز وزن کل از w باشه ، خواهیم داشت :

اگه wi≤w            

P[i][w]=max(P[i-1][w], pi+P[i-1][w-wi])

در غیر این صورت

P[i][w]=P[i-1][w]

بیشترین سود هم برابر با P[n][W] هست . حالا میشه به همین صورت وسایل رو انتخاب کرد و کاملا هم مشخصه که این مسئله به صورت پویا داره حل میشه . پیچیدگی زمانی این الگوریتم از مرتبه ی تتای nW هست .

 

پس دیدیم که اینجا میشه گفت برنامه ریزی پویا داره بهتر از روش حریصانه عمل میکنه . چون همیشه جواب درست و بهینه رو به ما میده . اما توی مسئله ی کوله پشتی کسری روش حریصانه درست کار میکنه . چون مجبور نیستیم یک شی رو به طور کامل انتخاب کنیم .بلکه میتونیم هر کسری از شی رو برداریم . کافیه در این مسئله ملاک رو نسبت ارزش به وزن در نظر بگیریم . در این صورت هرگز ظرفیت و گنجایش کوله هدر نمیره و همون مشکلی که باعث میشد در مسئله ی صفر و یک مشکل داشته باشیم برطرف میشه و مطمئن خواهیم شد که جواب بهینه رو خواهیم داشت .

اما بیاید یکم درباره ی کد هافمن صحبت کنیم . کدگذاری هافمن در علوم کامپیوتر ، کاربرد های زیادی داره . کد هافمن در فشرده سازی داده ها ( بدون اتلاف ) ، پردازش تصویر ، ساختمان داده ها و ... کاربرد داره. در کدگذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده میشه. به این روش ، روش کد های پیشوندی میگن . در این روش نویسه‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به اونایی که کاربردشون کمتره، نشون داده میشن . همچنین الگوریتم هافمن برای تعیین درخت با حداقل طول مسیر و وزن هم استفده میشه .

در این روش برای تعیین درخت مینیمم ، در هر مرحله ، دو درختی که دارای ریشه ی مینیمم هستن رو انتخاب میکنیم و در شروع هم باید از گره های خارجی استفاده کنیم .

مثلا فرض کنید چند حرف با جدول فراوانی به ما دادن به شکل زیر :

جدول فراوانی

اون وقت درخت هافمن چنین داده هایی به شکل زیر میشه :

درخت

مرحله ی 1 : a,b مینیمم هستن و انتخاب میشن و ریشه با مقدار 0.15 اینجاد میکنن .

مرحله ی 2 : در بین ریشه های باقی مونده ، ریشه های ab و c مینیمم هستن و اونهارو به هم وصل میکنیم و حاصل اونها میشه 0.4

مرحله ی 3 : در بین ریشه های باقیمونده ، ریشه های d وe مینیمم هستن و اونا رو وصل میکنیم . پس مقدار 0.6 رو جایگزین میکنیم .

مرحله ی 4: به ریشه میرسیم .

 

یکی از کاربرد های مهم درخت هافمن ، فشرده سازی داده ها هست . برای کدگذاری n عنصر اطلاعاتی حداقل به r بیت نیاز داریم که از رابطه ی زیر به دست میاد :

 

مثلا برای کدگذاری 5 تا کاراکتر ،حداقل به 3 بیت نیاز داریم .

روش کدگذاری هم به صورت زیر هست :

1- درخت هافمن با حداقل طول مسیر وزن رو تشکیل میدیم .

2- از ریشه شروع میکنیم و به تمام اتصال های چپ مقدار 0 و تمام اتصال های راست مقدار 1 میدیم .

برای پیدا کردن کد هر عضو ، از ریشه تا همون عضو 0 ها و 1 هارو پشت سر هم مینویسیم .

مثلا برای مثال قبلی داریم :

a=000

b=001

c=01

d=10

e=11

 

که شکل حل به صورت زیر هست .

درخت

کاملا هم مشخصه که 3 بیت داریم استفاده میکنیم برای ذخیره سازی 5 کاراکتر . یک نکته ی مهم دیگه هم اینه که عناصری که تکرار کمتری دارند ، دارای کد پیشوندی یکسانی هستن و فقط دارای قسمت انتهایی متفاوتی هستن .

تکنیک عقبگرد

از این تکنیک برای حل مسائلی استفاده میشه که توی اونها دنباله ای از اشیا از یک مجموعه ی مشخص انتخاب میشه ، به طوری که این دنباله ، ملاکی رو در بر میگیره . یک مثال کلاسیک ، مسئله ی n وزیر هست در این تکنیک .

این مسئله اینه که باید n مهره ی وزیر رو در یک صفحه ی n*n بچینیم به طوری که در هیچ سطر و ستون و قطری نباید وزیر ها همدیگرو پوشش بدن . خیلی جاها برای این مسئله ، خود صفحه ی شطرنج رو درنظر میگیرن و برای همین میگن مسئله ی 8 وزیر . ( صفحه ی شطرنج 8*8 هست ) .

خب دوستان برای این جلسه کافیه

در جلسه ی بعدی درباره ی تکنیک عقبگرد ، مسئله ی n وزیر ، مسئله ی حاصل جمع زیر مجموعه ها و الگوریتم مونت کارلو صحبت خواهیم کرد انشاءالله .

با تشکر از همه ی شما دوستان ، التماس دعا و خدانگهدار.