سوال 12
حل تشریحی سوال شماره 12 طراحی الگوریتم
کنکور دکتری مهندسی کامپیوتر 1398
12.
فرض کنید گراف G همبند، بدون جهت و وزن دار است بهطوری که میتواند دور منفی هم داشته باشد. در مورد مسئله پیدا کردن کوتاهترین مسیر از یک رأس به رأس دیگر طوری که از هر رأسی حداکثر یک بار عبور کند چه می توان گفت؟
1)
یک مسئله ان پی - تمام است.
2)
یک مسئله ان پی - سخت است.
3)
به علت وجود دور منفی در گراف لزوماً چنین مسیری وجود ندارد.
4)
در زمان چند جملهای برحسب اندازه ورودی میتوان مسئله را حل کرد.
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،