تبلیغات

سرو کوهی - The Knapsack Problem - تنها مسئله یک کوله پشتی است ؟
برای بهتر فهمیدن بیشتر بدانیم.
درباره وبلاگ


سخن روز

آرشیو

طبقه بندی





آخرین پستها

ساعت فلش

پیوندهای روزانه

نویسندگان

ابر برچسبها

نام شما :
ایمیل شما :
نام دوست شما:
ایمیل دوست شما:

Powered by web-abzar.ir
نظرسنجی



ابزار آپلود



آمار وبلاگ

الکسا


 ابزارهای زیبا سازی برای سایت و وبلاگ
Admin Logo
themebox


( شما چه انتخابی میکنید ؟ )

سلام.
مسئله ای ترکیبیاتی به نام کوله پشتی در بهینه سازی وجود دارد که ذهن بسیاری را در برهه اول به خود مشغول میکند.

در این مسئله فرض بر این است که تعداد n کیسه از اجناس مختلف به عنوان ورودی داده شده است
و هر کیسه دارای وزن و سود مشخصی است .

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

الگوریتم های زیادی بر پایه ی برنامه نویسی پویا ،  روش تقسیم و حد ، یا ترکیبی از هر دو روش برای این مسئله وجود دارند.

شکل معروف خاصی از این مسئله کوله پشتی صفر و یک است.




نکته حیرت  انگیز اینجاست که حل دقیق این سوال، مسئله ای از نوع  NP-complete  است. بنابراین پیش بینی شده که راه حلی که هم درست و هم سریع باشد - با زمان اجرای چند جمله ای -  برای هر ورودی دلخواه، وجود ندارد.

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

برای حل مسئله کوله پشتی ، توسط الگوریتم عقبگرد ابتدا قطعات را بر اساس Pi/Wi  به ترتیب غیر نزولی مرتب می کنیم. که در ان Wiو Piبه ترتیب وزن و ارزش  i  هستند.فرض کنید می خواهیم امید بخش بودن یک گره خاص را تعیین کنیم. برای این کار تعریف های زیر را در نظر بگیرید :

Profit: حاصل جمع ارزش قطعاتی می باشد که تا ان گره در نظر گرفته شده اند.

Weight  : حاصل جمع اوزان قطعاتی می باشد که تا ان گره در نظر گرفته شده اند.

Bound:  حد بالایی از بهره قابل دستیابی با استفاده از گسترش دادن گره است.  و به ان مقدار اولیه  profit  نسبت داده می شود.

Total weight: نشان دهنده ی وزن کلی قطعات بوده و به ان مقدار اولیه weight  نسبت داده می شود.

روش کار بدین صورت است که قطعات را بر اساس Pi/Wi انها انتخاب کرده سپس ارزش انها را به bound و وزن انها را به total weight  اضافه می کنیم تا به قطعه ای برسیم که اگر وزن ان را به مجموع وزن های قبلی اضافه کنیم total weight از wبیشتر شود .

و اگر maxprofit مقدار بهره در بهترین حلی باشد که تاکنون پیدا شده است ، در این صورت یک گره در سطح i ، غیر امید بخش خواهد بود هرگاه داشته  باشیم :

Bound<=max profit



( استفاده از روش بازگشتی در مسئله کوله پشتی )


شما هم می توانید با گسترش دادن این مسئله برای خود شروع به حل آن بکنید و خود را در چالش یک کد دشوار قرار دهید :)



آموزش 1 :( متاسفانه 50 ثانیه اول تبلیغات است! اما فیلم آموزشی مفیدی برای پیاده سازی در  زبان متلب است )

[http://www.aparat.com/v/YC6lD]



آموزش 2 : ( بخش اول آموزش )

[http://www.aparat.com/v/0gd6b]



آموزش 2 : ( بخش دوم آموزش )

[http://www.aparat.com/v/Fm6pY]

Detect language » Hungarian
Detect language » Hungarian
Detect language » Hungarian
Detect language » Hungarian
Detect language » Hungarian
Detect language » Hungarian
Detect language » Hungarian
Detect language » Hungarian


نوشته شده توسط :The Faludah
سه شنبه 29 اردیبهشت 1394-10:53 ب.ظ

How long will it take for my Achilles tendon to heal?
سه شنبه 28 شهریور 1396 06:31 ق.ظ
It's going to be finish of mine day, but before finish I am
reading this enormous article to increase my know-how.
sophieclare.hatenablog.com
سه شنبه 17 مرداد 1396 08:14 ق.ظ
Hi there every one, here every one is sharing these kinds of experience,
therefore it's nice to read this web site, and I used to
visit this weblog daily.
Why is my Achilles tendon burning?
شنبه 14 مرداد 1396 07:29 ق.ظ
excellent post, very informative. I wonder why the opposite experts of this sector don't
realize this. You should proceed your writing.
I'm sure, you have a great readers' base already!
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر