سوال 72

حل تشریحی سوال شماره 72 طراحی الگوریتم

کنکور ارشد مهندسی کامپیوتر 1401

72.

فرض کنید G یک گراف بدون جهت و بدون وزن با n راس و m یال باشد. مسئله زیر را در نظر بگیرید:

به ازای دو راس u و v داده شده و پارامتر ورودی k، ایا تعداد کوتاه ترین مسیرها بین u و v حداقل k است؟

کدام گزینه درموزد این مسئله درست است؟

1)

می توان الگوریتمی با زمان اجرای چندجمله ای برای این مسئله ارائه داد، اما زمان اجرای این الگوریتم نمی تواند برحسب n و m خطی باشد.

2)

می توان الگوریتمی با زمان اجرای O(m+n) برای این مسئله ارائه داد.

3)

این یک مسئله ان‌پی-تمام است

4)

این یک مسئله ان‌پی-سخت است

پاسخ ها

0 پاسخ
تا کنون پاسخی برای این سوال وارد نشده است،

ارسال پاسخ