نمايش پست تنها
قديمي ۰۸-۱-۱۳۸۸, ۰۶:۲۱ بعد از ظهر   #2 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Question

مسئله کوله پشتی چیست؟
فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از 1 تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند بصورت مساله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متاسفانه تعداد چنین بردارهایی است.بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این وجود ،با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100 000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده است:
raha90 (۰۳-۸-۱۳۹۰)