حل تشریحی سوال شماره 43 دروس مشترک (ساختمانهای گسسته، ساختمان دادهها، طراحی الگوریتم، مهندسی نرمافزار، شبکههای کامپیوتری)
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1404
فرض کنید میخواهید یک گراف با n گره را با حداکثر رنگ رنگ آمیزی کنید به طوری که هیچ دو گره متصل به یکدیگر رنگ یکسانی نداشته باشند. برای این کار از الگوریتم عقب گرد (Backtracking) استفاده می کنید. در هر مرحله یک رنگ را به یک گره اختصاص میدهید و اگر تخصیص رنگ به بن بست برسد به گره قبلی برمی گردید و رنگ جدیدی را امتحان میکنید برای بهینه سازی الگوریتم کدام مورد بهترین روش است؟
در هر مرحله به صورت تصادفی یک گره انتخاب کنید و رنگ آمیزی آن را انجام دهید.
ابتدا گره های با کمترین تعداد همسایه را رنگ آمیزی کنید تا محدودیتهای کمتری برای گره های بعدی ایجاد شود.
ابتدا گره ها را بر اساس تعداد همسایگانشان مرتب کنید و گره های با بیشترین تعداد همسایه را زودتر رنگ آمیزی کنید.
در هر مرحله ابتدا رنگهایی را امتحان کنید که کمترین تعداد گره در کل گراف به آنها اختصاص یافته است. زیرا این کار تنوع رنگ در گراف را افزایش و احتمال بن بست را کاهش می دهد.