حل تشریحی سوال شماره 93 مجموعه دروس تخصصی مشترک
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1401
از الگوریتم با تابع هیوریستیک قابل قبول h برای حل یک مسئله بهینه سازی استفاده میشود. از یک گراف برای نمایش مسئله استفاده میشود که در آن هر رأس نشان دهنده یک حالت عدد درون هر رأس نشان دهنده مقدار تابع هیوریستیک برای آن حالت و عدد روی هر یال نشان دهنده هزینه آن یال است. فرض کنید هزینه مسیر یافته شده توسط الگوریتم در این حالت و تعداد گامهای آن است. در صورتی که مقدار ثابت به کلیه مقادیر تابع هیوریستیک (اعداد درون رأسها) و مقادیر هزینه گامها (اعداد روی یالها) اضافه شود کدام گزینه درست است؟
مسیر بهینه مسئله نسبت به حالت قبل تغییر نخواهد کرد اما هزینه آن نخواهد بود.
جوابی که الگوریتم در حالت جدید پیدا میکند نسبت به حالت قبل تغییری نخواهد کرد، اما هزینه آن بیشتر از خواهد بود.
اگر هزینه مسیر بهینه گراف جدید باشد داریم:
تابع هیوریستیک جدید در کلیه حالتها رأسهای گراف جز حالتهای هدف، قابل قبول خواهد بود.