![]() |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - نسخهی قابل چاپ صفحهها: ۱ ۲ |
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - لهمشد - ۱۱ اسفند ۱۳۹۰ ۱۱:۴۸ ب.ظ
(۰۴ دى ۱۳۹۰ ۱۲:۳۷ ق.ظ)Nargeskl نوشته شده توسط: سلامبا اجازه اساتید: مساله توقف پذیری (halting problem ) یه مثالی از این نوع هستش .که هدف نوشتن برنامه اجرایی هستش که بتونه بگه یه برنامه دیگه خاتمه پیدا میکنه یا خیر. |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - alidata - 12 اسفند ۱۳۹۰ ۰۱:۵۲ ق.ظ
TSP هم جز np-hard ها محسوب میشه؟ |
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - لهمشد - ۱۴ اسفند ۱۳۹۰ ۰۲:۲۵ ق.ظ
(۱۲ اسفند ۱۳۹۰ ۰۱:۵۲ ق.ظ)alidata نوشته شده توسط: TSP هم جز np-hard ها محسوب میشه؟بله .مسله فروشنده دوره گردد از جمله مسائل NP_hard بشمار میره |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - mamad0917762 - 01 آبان ۱۳۹۱ ۱۲:۲۴ ق.ظ
با سلام.در موردمبحث اینکه بخواهیم مسائل براساس نوع پیچیدگی(np/np-hard/np-complete)دسته بندی کنیم راهنمایی میخوام؟و چند تا مساله بهینه سازی ترکیباتی؟ |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - marmar3 - 07 آذر ۱۳۹۲ ۱۲:۰۷ ب.ظ
سلام من یه سوالی داشتم وقتی یک مسئله ایی دارای مسئله تصمیم شد میگیم اون مسئله یک NP Complete هست حالا من از کجا متوجه بشم که آیا اون مسئله NP hard هست یا نه؟ مثالشم مثلا مسئله Partition آقای دکتر یه سوال دیگه هم داشتم مسئله ای رو داریم که NP hard باشه ولی NP نباشه؟؟؟؟؟؟ میشه یه مثال بزنید کلا این مسائل رو چطوری میتونم تشخیص بدم؟؟؟؟ ازتون تشکر میکنم منو راهنمایی کنید |
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - انرژی مثبت - ۰۴ دى ۱۳۹۲ ۰۱:۰۳ ب.ظ
(۲۴ تیر ۱۳۹۰ ۱۲:۰۷ ق.ظ)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 می شه؟ |
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - equilibrium - 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 ( مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. - سکشن ۴، خط اول) |
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - انرژی مثبت - ۰۴ دى ۱۳۹۲ ۰۷:۱۰ ب.ظ
(۰۴ دى ۱۳۹۲ ۰۴:۱۶ ب.ظ)Ghiasoddin نوشته شده توسط:ممنون (لینک رو قبلا دیده بودم واسه این شک ام بیشتر شد با توجه به توضیحات دوستان که نقل قول کرده بودم!)(04 دى ۱۳۹۲ ۰۱:۰۳ ب.ظ)انرژی مثبت نوشته شده توسط: اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟اگه سوال به این صورت نوشته بشه: می شه گفت سوالم اینه که بین P و NPC بودن فرق هست اینجا؟ یعنی توی جمله بعدم گفتم که با فرض این که A در زمان چند جمله ای به B کاهش پیدا می کنه، باید B مساله P باشه که A هم P باشه؟ ولی در مورد NPC باید A مساله NPC باشه تا B مساله NPC بشه؟ |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - equilibrium - 04 دى ۱۳۹۲ ۰۸:۵۶ ب.ظ
در مورد مسائل P که بدیهیه؛ وقتی A از کلاس P هست یعنی یه الگوریتم قطعی چندجمله ای میتونه اونو حل کنه؛ حالا اگه مسئله B در زمان چندجمله ای به A کاهش پیدا کنه، یعنی B هم از کلاس P هست؛ حالت بر عکسش اینه که اگه A در زمان چندجمله ای به B کاهش پیدا کنه و از طرفی الگوریتم چندجمله ای برای A وجود نداشته باشه (A عضو P نباشه)، در این صورت B هم نمیتونه در چندجمله ای حل بشه (عضو P نیست)؛ |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - newwink - 13 آذر ۱۳۹۵ ۰۵:۵۸ ب.ظ
سلام دوستان چه گرد و خاکی گرفته اینجا!! میگم چطور میشه اثبات کرد که توقف پذیری یه مسئله np-hard هست؟ |
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete - amin1.darabi - 28 مهر ۱۳۹۶ ۱۲:۲۲ ق.ظ
سلام دوستان من ۴ تا مسئله الگوریتم پیشرفته دارم اگه کسی بلده بهم پیام بده ممنون میشم کمکم کنه یکی مرتب سازی احمقانه هس یکی هم کارت شماره ۳ یکی هم دومینوی ۲ و ۳ بعدی آی دی تلگرام niam_d3@ |