سلام و وقت بخیر ...

به نظرم این مساله همان مساله بهینه سازی کوله پشتی است با این تفاوت که در مساله کوله پشتی ما میخواستیم بیشترین ارزش ( بودجه ای ) را در کوله محدود خود قرار دهیم ( یعنی اجناسی با ارزش زیادتر در کوله قرار گیرد ) ولی در اینجا میخواهیم وزن اشیا بیشینه گردد ...

در اکثر منابع حل دقیق این سؤال، مسئله‌ای از نوع NP-complete است و راه حلی که هم درست و هم سریع باشد (با زمان اجرای چندجمله‌ای) برای هر ورودی دلخواه، ندارد.

در مورد حریصانه معمولا پاسخ بهینه حاصل نمیشود ( قطعی نیست ) .. و در مورد پویا راه حل شبه چند جمله ای برای آن وجود دارد ...

(۱۶ فروردین ۱۳۹۶ ۰۲:۴۷ ب.ظ)alireza01 نوشته شده توسط:  سلام و وقت بخیر ...

به نظرم این مساله همان مساله بهینه سازی کوله پشتی است با این تفاوت که در مساله کوله پشتی ما میخواستیم بیشترین ارزش ( بودجه ای ) را در کوله محدود خود قرار دهیم ( یعنی اجناسی با ارزش زیادتر در کوله قرار گیرد ) ولی در اینجا میخواهیم وزن اشیا بیشینه گردد ...

در اکثر منابع حل دقیق این سؤال، مسئله‌ای از نوع NP-complete است و راه حلی که هم درست و هم سریع باشد (با زمان اجرای چندجمله‌ای) برای هر ورودی دلخواه، ندارد.

در مورد حریصانه معمولا پاسخ بهینه حاصل نمیشود ( قطعی نیست ) .. و در مورد پویا راه حل شبه چند جمله ای برای آن وجود دارد ...

اینجا سوالی که به ذهن خطور می کند این است که مگر کلاس np کامل زیر مجموعه کلاس np سخت نیست؟ یعنی اگر مسئله کوله پشتی Np کامل باشد Np سخت هم هست یعنی اگر گزینه ۳ درست باشد گزینه ۴ هم درست است(در گزینه ۴ گفته در حالت کلی احتمالا به این موضوع اشاره دارد)

(۱۶ فروردین ۱۳۹۶ ۰۷:۰۶ ب.ظ)msour44 نوشته شده توسط:  اینجا سوالی که به ذهن خطور می کند این است که مگر کلاس np کامل زیر مجموعه کلاس np سخت نیست؟ یعنی اگر مسئله کوله پشتی Np کامل باشد Np سخت هم هست یعنی اگر گزینه ۳ درست باشد گزینه ۴ هم درست است(در گزینه ۴ گفته در حالت کلی احتمالا به این موضوع اشاره دارد)

سلام دوست عزیز
طبق تعریف مساله ای NP کامل است که جز اشتراک کلاس NP و NP سخت باشد .. با این توضیحات میشه گفت در یک حالت دیگر این مساله جز کلاس NP هم هست . ولی به نظرم بهتره مساله ای که براش دسته ای خاص ذکر شده هر چند جزو دسته های کلی تر باشد ، جزو همان دسته بمانیم در غیر این صورت تعریف دسته NP کامل چه لزومی دارد ، هر چند گزینه ۳ و ۴ هر دو صحیح هستند و حرف شما هم صحیح است .

(۱۶ فروردین ۱۳۹۶ ۰۷:۴۴ ب.ظ)alireza01 نوشته شده توسط:  

(16 فروردین ۱۳۹۶ ۰۷:۰۶ ب.ظ)msour44 نوشته شده توسط:  اینجا سوالی که به ذهن خطور می کند این است که مگر کلاس np کامل زیر مجموعه کلاس np سخت نیست؟ یعنی اگر مسئله کوله پشتی Np کامل باشد Np سخت هم هست یعنی اگر گزینه ۳ درست باشد گزینه ۴ هم درست است(در گزینه ۴ گفته در حالت کلی احتمالا به این موضوع اشاره دارد)

سلام دوست عزیز
طبق تعریف مساله ای NP کامل است که جز اشتراک کلاس NP و NP سخت باشد .. با این توضیحات میشه گفت در یک حالت دیگر این مساله جز کلاس NP هم هست . ولی به نظرم بهتره مساله ای که براش دسته ای خاص ذکر شده هر چند جزو دسته های کلی تر باشد ، جزو همان دسته بمانیم در غیر این صورت تعریف دسته NP کامل چه لزومی دارد ، هر چند گزینه ۳ و ۴ هر دو صحیح هستند و حرف شما هم صحیح است .

سلام
بله دوست گرامی
فقط منظورم این بود که گزینه ۴ گزینه ۳ را هم پوشش می دهد.(البته فقط به نظر این حقیر)
در مورد قرار گرفتن کوله پشتی در دسته np کامل در جایی خواندم(نام کتاب یادم نیست ولی یادم که از مقالات Richard M. karp از دانشمندان معروف نظریه محاسبات اقتباس شده بود ) که
"مساله کوله پشتی نسخه تصمیم پذیری ان np کامل است و نسخه محاسباتی ان np سخت است"
در مورد لزوم تعریف Np کامل این را بگم که این دسته بیشتر توسط دانشمندانی به وجود امد که سعی در اثبات P=np داشتند.
دوست گرامی با احترام به پاسخ تان من فقط برام یک سوال پیش امد و مثل بسیاری از دوستان ان را مطرح کردم.سپاس به خاطر نکاتی که عنوان کردید.

(۱۶ فروردین ۱۳۹۶ ۱۱:۲۳ ب.ظ)msour44 نوشته شده توسط:  سلام
بله دوست گرامی
فقط منظورم این بود که گزینه ۴ گزینه ۳ را هم پوشش می دهد.(البته فقط به نظر این حقیر)
در مورد قرار گرفتن کوله پشتی در دسته np کامل در جایی خواندم(نام کتاب یادم نیست ولی یادم که از مقالات Richard M. karp از دانشمندان معروف نظریه محاسبات اقتباس شده بود ) که
"مساله کوله پشتی نسخه تصمیم پذیری ان np کامل است و نسخه محاسباتی ان np سخت است"
در مورد لزوم تعریف Np کامل این را بگم که این دسته بیشتر توسط دانشمندانی به وجود امد که سعی در اثبات P=np داشتند.
دوست گرامی با احترام به پاسخ تان من فقط برام یک سوال پیش امد و مثل بسیاری از دوستان ان را مطرح کردم.سپاس به خاطر نکاتی که عنوان کردید.

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

گزینه ۳ یا ۴ ؟
حس میکنم ۳ باشه

این یه نوع کوله پشتیه که npc است. چون همه ان پی سی ها np هارد هستن،۳و۴هردو درستن....چون ۴ گفته در حالت کلی np هارده، گزینه ۴ درسته.

اون مساله فروشنده دوره گرده که تصمیم گیریش ان پی کامله و بهینه سازیش ان پی سخته....

(۲۵ فروردین ۱۳۹۶ ۱۲:۴۱ ب.ظ)*tarannom* نوشته شده توسط:  این یه نوع کوله پشتیه که npc است. چون همه ان پی سی ها np هارد هستن،۳و۴هردو درستن....چون ۴ گفته در حالت کلی np هارده، گزینه ۴ درسته.

اون مساله فروشنده دوره گرده که تصمیم گیریش ان پی کامله و بهینه سازیش ان پی سخته....

جالبه دکتر قدسی تو پاسخنامه گزینه ۳ رو جواب میدونه ولی تو راه حل گزینه ۴

(۲۵ فروردین ۱۳۹۶ ۰۱:۱۶ ب.ظ)Mohammad.93 نوشته شده توسط:  

(25 فروردین ۱۳۹۶ ۱۲:۴۱ ب.ظ)*tarannom* نوشته شده توسط:  این یه نوع کوله پشتیه که npc است. چون همه ان پی سی ها np هارد هستن،۳و۴هردو درستن....چون ۴ گفته در حالت کلی np هارده، گزینه ۴ درسته.

اون مساله فروشنده دوره گرده که تصمیم گیریش ان پی کامله و بهینه سازیش ان پی سخته....

جالبه دکتر قدسی تو پاسخنامه گزینه ۳ رو جواب میدونه ولی تو راه حل گزینه ۴

به نظرم چون گزینه ۴ گفته در حالت کلی،گزینه ی بهتریه..... ولی بعیده سر کنکور گزینه اینطوری بدن..... چون قدسیم خودش دچار دو گانگی شده