سلام
وقت به خیر
ببخشید من الگوریتم کلاسیک
مسیر هامیلتونی را می خواستم و اینکه سریع ترین الگوریتم متوالی ای که برای مسیر هامیلتونی موجود است
با پیچیدگی زمانی اش ( سریع ترین )
میشه کمکم کنین؟
یا اگر مقاله ای در موردش هست بهم معرفی کنین؟
مرسی
سلام
مسئله ی وجود یک مسیر همیلتنی یک مسئله ی NP است (و NP_Complete است)
یعنی می توان آن را به صورت
غیر قطعی در زمان چند جمله ای حل کرد و به قول سیپسر هیچ کس راه حلی در زمان چندجمله ای برای آن نمی داند.
و روش غیر قطعی آن بنابر گفته ی سیپسر این گونه است که ابتدا وجود مسیر بین این دو راس را به قطعی در زمان چندجمله ای با روش زیر تعیین کنیم:
اگر بخواهیم ببینیم آیا مسیری همیلتنی بین دو راس s و t در گراف G وجود دارد یا نه بدین صورت عمل می کنیم:
راس s را مارک کن
مادامی که راسی برای مارک کردن وجود نداشته باشد این کار را انجام بده: هر b ای که یک یال (a,b) موجود باشد و a مارک شده باشد را نیز مارک کن
اگر t مارک شده بود یعنی مسیری بین این دو راس وجود داشته
(واضح است که مرحله دوم نهایتا به تعداد رئوس تکرار می شود )
سپس چک کنیم که آیااین مسیر همیلتتنی است یا نه.
اثبات این مطالب را می توانید در صفحات ۲۶۰-۲۶۴و۲۸۶ کتاب سیپسر مطالعه کنید(شماره صفحات پی دی اف آن به ترتیب ۲۷۲-۲۷۶و ۲۹۸ است).
لینک کتاب سیپسر:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینم ۳ مقاله ی کوتاه در مورد این مسئله:
مرسی ممنونم مقاله ها رو حتما مطالعه می کنم
بهترین پیچیدگی زمانی ای که برای الگوریتم پیدا کردن مسیر هاملیتونی هست چه مقداری است؟ همچنین پیچیدگی فضایی؟؟
بهترین الگوریتم های موجودش را می شه به من بدید؟
(24 تير 1393 07:36 ب.ظ)student-cs نوشته شده توسط: [ -> ]مرسی ممنونم مقاله ها رو حتما مطالعه می کنم
بهترین پیچیدگی زمانی ای که برای الگوریتم پیدا کردن مسیر هاملیتونی هست چه مقداری است؟ همچنین پیچیدگی فضایی؟؟
بهترین الگوریتم های موجودش را می شه به من بدید؟
تا اونجایی که می دونم معمولا وقتی یه مسئله NP_COMPLETE است دیگه اصلا دنبال پیاده سازی ش نمی رن چون این مسائل اغلب نمایی، فاکتوریل، متعای یا حتی پیچیده ترن و نمیشه و کامپیوترهای معمولی اجراشون کرد.
اما اگه از اجرا بگذریم و فقط به صرف یافتن الگوریتم و مرتبه زمانی بپردازیم خب یکی همین روشی که تو کتاب سیپسره هست یه روش دیگه هم با تکنیک backtracking است که تصویر توضیحات کتاب پورانو براتون می ذارم احتمالا روش های دیگه ای هم هست
