انجمنصفحه اولجستجوی انجمن

[لهمشد]

(۰۴ دى ۱۳۹۰ ۱۲:۳۷ ق.ظ)Nargeskl نوشته شده توسط:  سلام
میشه به من کمک کنید
لطفایه نمونه مساله از Np-Hard برام مثال بزنید

با اجازه اساتید:
مساله توقف پذیری (halting problem ) یه مثالی از این نوع هستش .که هدف نوشتن برنامه اجرایی هستش که بتونه بگه یه برنامه دیگه خاتمه پیدا میکنه یا خیر.

[alidata]

TSP هم جز np-hard ها محسوب میشه؟

[لهمشد]

(۱۲ اسفند ۱۳۹۰ ۰۱:۵۲ ق.ظ)alidata نوشته شده توسط:  TSP هم جز np-hard ها محسوب میشه؟

بله .مسله فروشنده دوره گردد از جمله مسائل NP_hard بشمار میره

[mamad0917762]

با سلام.در موردمبحث اینکه بخواهیم مسائل براساس نوع پیچیدگی(np/np-hard/np-complete)دسته بندی کنیم راهنمایی میخوام؟و چند تا مساله بهینه سازی ترکیباتی؟

[marmar3]

سلام
من یه سوالی داشتم
وقتی یک مسئله ایی دارای مسئله تصمیم شد میگیم اون مسئله یک NP Complete هست
حالا من از کجا متوجه بشم که آیا اون مسئله NP hard هست یا نه؟
مثالشم مثلا مسئله Partition

---

آقای دکتر یه سوال دیگه هم داشتم
مسئله ای رو داریم که NP hard باشه ولی NP نباشه؟؟؟؟؟؟
میشه یه مثال بزنید

کلا این مسائل رو چطوری میتونم تشخیص بدم؟؟؟؟

ازتون تشکر میکنم منو راهنمایی کنید

[انرژی مثبت]

(۲۴ تیر ۱۳۹۰ ۱۲:۰۷ ق.ظ)admin نوشته شده توسط:  در نظریه محاسبه پذیری اگر A به B در زمان چند جمله‌ای کاهش پذیر بوده و B تصمیم ناپذیر باشد آن گاه Aنیز تصمیم ناپذیر خواهد بود.

(۲۴ تیر ۱۳۹۰ ۰۴:۲۶ ب.ظ)parimehraban نوشته شده توسط:  در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود .همین طوراگر A تصمیم پذیر نبوده و به B کاهش یابد، آنگاه B نیز تصمیم پذیر نخواهد بود .

(۲۷ آذر ۱۳۹۰ ۱۱:۳۹ ب.ظ)psps1368 نوشته شده توسط:  مثلا Halting Problem یک مسئله NP-Hard است، چرا که SAT به آن در زمان چند جمله ای کاهش پیدا می کند. واضح هست که Halting Problem، یک مسئله NP نیست.

با توجه به توضیحات بالا، یه سوال دارم.
اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟

در واقع سوالم اینه که اگر A و B هر دو تصمیم پذیر باشند یعنی جزو P باشند اونوقت اگر A جزو مسائل P باشه، B هم P می شه و اگر B تصمیم پذیر یا جزو NPC باشه اونوقت َA هم NPC می شه؟

[equilibrium]

(۰۴ دى ۱۳۹۲ ۰۱:۰۳ ب.ظ)انرژی مثبت نوشته شده توسط:  اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟

اگه سوال به این صورت نوشته بشه:
فرض کنید A یک مساله NPC است؛ اگر A در زمان چندجمله ای به B کاهش پیدا کند، می توان گفت B نیز یک مساله NPC است؟
پاسخ مثبته:
.To prove that a problem is NP-complete, we typically reduce a problem that is known to be NP-complete to it

(
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
- سکشن ۴، خط اول)

[انرژی مثبت]

(۰۴ دى ۱۳۹۲ ۰۴:۱۶ ب.ظ)Ghiasoddin نوشته شده توسط:  

(04 دى ۱۳۹۲ ۰۱:۰۳ ب.ظ)انرژی مثبت نوشته شده توسط:  اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟

اگه سوال به این صورت نوشته بشه:
فرض کنید A یک مساله NPC است؛ اگر A در زمان چندجمله ای به B کاهش پیدا کند، می توان گفت B نیز یک مساله NPC است؟
پاسخ مثبته:
.To prove that a problem is NP-complete, we typically reduce a problem that is known to be NP-complete to it

(
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
- سکشن ۴، خط اول)

ممنون (لینک رو قبلا دیده بودم واسه این شک ام بیشتر شد با توجه به توضیحات دوستان که نقل قول کرده بودم!)
می شه گفت سوالم اینه که بین P و NPC بودن فرق هست اینجا؟ یعنی توی جمله بعدم گفتم که با فرض این که A در زمان چند جمله ای به B کاهش پیدا می کنه، باید B مساله P باشه که A هم P باشه؟ ولی در مورد NPC باید A مساله NPC باشه تا B مساله NPC بشه؟

[equilibrium]

در مورد مسائل P که بدیهیه؛ وقتی A از کلاس P هست یعنی یه الگوریتم قطعی چندجمله ای میتونه اونو حل کنه؛ حالا اگه مسئله B در زمان چندجمله ای به A کاهش پیدا کنه، یعنی B هم از کلاس P هست؛
حالت بر عکسش اینه که اگه A در زمان چندجمله ای به B کاهش پیدا کنه و از طرفی الگوریتم چندجمله ای برای A وجود نداشته باشه (A عضو P نباشه)، در این صورت B هم نمیتونه در چندجمله ای حل بشه (عضو P نیست)؛

[newwink]

سلام دوستان
چه گرد و خاکی گرفته اینجا!!
میگم چطور میشه اثبات کرد که توقف پذیری یه مسئله np-hard هست؟

[amin1.darabi]

سلام دوستان من ۴ تا مسئله الگوریتم پیشرفته دارم اگه کسی بلده بهم پیام بده ممنون میشم کمکم کنه
یکی مرتب سازی احمقانه هس
یکی هم کارت شماره ۳
یکی هم دومینوی ۲ و ۳ بعدی
آی دی تلگرام
niam_d3@