بررسی مسأله آتش نشان روی گراف های وزن دار

یکی از مسائل مورد بحث در بهینه سازی ترکیبیاتی مسأله آتش نشان است که دارای کاربردهای فراوان از جمله مهار آتش، مهار سیل، جلوگیری از انتشار ویروس (اطلاعات مخرب) در دستگاههای اطلاعاتی و کنترل رشد بیماریهای واگیردار مانند و با است. این مسأله روی گرافهای عمومی NP-سخت است. برای این مسأله روی برخی گرافهای خاص مطالعات گستردهای انجام شده است. هدف از مسأله آتش نشان روی گرافها، مهار آتش است به طوری که بیشترین تعداد رئوس گراف از آتش در امان بماند. ما در این مقاله به بررسی مسأله آتش نشان روی گرافهای وزن دار می پردازیم و یک الگوریتم ابتکاری برای این مسأله روی درختهای وزن دار ارائه می کنیم. در پایان نیز جهت درک بهتر الگوریتم ارائه شده، مثال عددی بیان می کنیم.

Keywords:

مساله آتش نشان , الگوریتم ابتکاری , مکان یابی