الگوریتم کوله پشتی

الگوریتم کوله پشتی

اسلاید 1: بسمه تعالیالگوریتم کوله پشتی چیست؟تهیه شده توسط : علی فخری و محمد میریدرس : شیوه ارائهاستاد : آقای هرمزی

اسلاید 2: مقدمهمسئله کوه پشتی،که با عنوان های Knapsack یا Rucksack مطرح می شود.مسئله ای در بهینه سازی ترکیباتی است. فرض کنید مجموعه ای از اشیا،که هر کدام دارای وزن و ارزش خاصی هستند در اختیار دارید. به هر شئ تعدادی را تخصیص دهید به طوریکه وزن اشیا انتهاب شده کوجکتر یا مساوری حدی از پیش تعیین شده،وارزش آن ها بیشینه شود. علت نامگذاری این مسئله،جهانگردی است که کوله پشتی ای با اندازه محدود دارد و باید آن را با مفید ترین صورت ممکن از اشیا پر کند. معمولا در تخصیص منابع با محدودیت های مالی،با این مسئله روبرو هستیم.همچنین مسائلی از این قبیب در ترکیبات، نظریه پیچیدگی محاسباتی،رمزنگاری و ریاضیات کاربردی به چشم میخورد

اسلاید 3: تاریخچهمسئلهٔ کوله پشتی بیش از یک قرن مورد مطالعه قرار گرفته و اولین بررسی در سال ۱۸۹۷ انجام گرفته‌است. هر چند اولین داده‌های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (1884–1956) Tobias Dantzi برمی گردد، چیزی با عنوان مسئله کوله پشتی قبلاً در میان عامه مردم وجود داشته‌است.مسئله کوله پشتی درجه دوم، اولین بار توسط Hammer، Gallo وSimeone در سال ۱۹۶۰ مطرح شد.در سال ۱۹۸۸، تحقیقی از دانشگاه استونی بروک بر روی مجموعه‌ای از الگوریتم‌ها، نشان داد که از میان ۷۵ مسئله الگوریتمی، مسئله کوله پشتی، ۱۸ امین مسئله معروف و ۴ امین مسئله پرکاربرد بعد از درخت کی دی، درخت پیشوندی و bin packing problemاست.

اسلاید 4: تعریفمسئله کوله پشتی چیست؟ فرض کنید که جهانگردی می‌خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می‌سازند پر کند. این مسئله می‌تواند با شماره‌گذاری این وسائل از 1 تا n و تعریف برداری از متغیرهای دو دوی به صروت ریاضی فرمول بندی میشود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ام فراهم می‌آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است، که محدودیت را برآورده کند. بطوری‌که تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه‌ای از مسائلی که می‌توانند به صورت مسئله کوله پشتی فرمول بندی شوند،

اسلاید 5: ادامه _ تعریف 2در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می‌کند، عبارت از برنامه‌نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می‌کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است.

اسلاید 6: ادامه_تعریف3 بطوری‌که یک کامپیوتر فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای = n۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای = n۶۱ و ده‌ها قرن برای = n۶۵ والی آخر. با این وجود، با استفاده از الگوریتمهایی خاص می‌توان در بسیاری موارد مسئله‌ای با = n 100000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد.

اسلاید 7: ادامه_تعریف4 بطوری‌که یک کامپیوتر فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای = n۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای = n۶۱ و ده‌ها قرن برای = n۶۵ والی آخر. با این وجود، با استفاده از الگوریتمهایی خاص می‌توان در بسیاری موارد مسئله‌ای با = n 100000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد.معروف‌ترین نوع از این مسئله، مسئله کوله پشتی ۰ و ۱ است. یعنی تعداد از هر شی، یا ۰ است (آن شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود).