حل تشریحی سوال شماره 72 طراحی الگوریتم
کنکور ارشد مهندسی کامپیوتر 1401
72.
فرض کنید G یک گراف بدون جهت و بدون وزن با n راس و m یال باشد. مسئله زیر را در نظر بگیرید:
به ازای دو راس u و v داده شده و پارامتر ورودی k، ایا تعداد کوتاه ترین مسیرها بین u و v حداقل k است؟
کدام گزینه درموزد این مسئله درست است؟
1)
می توان الگوریتمی با زمان اجرای چندجمله ای برای این مسئله ارائه داد، اما زمان اجرای این الگوریتم نمی تواند برحسب n و m خطی باشد.
2)
می توان الگوریتمی با زمان اجرای O(m+n) برای این مسئله ارائه داد.
3)
این یک مسئله انپی-تمام است
4)
این یک مسئله انپی-سخت است
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،