الگوریتمی ابتکاری برای ساخت درخت اشتاینر درون چند ضلعی ساده با وجود موانع

به طور کلی مسئله درخت اشتاینر ، عبارت است از پیدا کردن درخت کمینه ای که شامل نقاط مشخص می باشد و در صورت لزوم از تعدادی نقاط کمکی نیز برای کمینه کردن طول درخت استفاده کند . در این مقاله درخت اشتاینر در حالتی بررسی شده که رئوس و یال های درخت در داخل چند ضلعی سادهp قرار گرفته اندهمچنین فرض شده ، تعدادی مانع به شکل چند ضلعی ساده نیز داخل چند ضلعیpوجود دارند که یال های درخت اشتاینر نباید آنها را قطع کنند . بیان مسئله به این صورت ، بیان گر محدودیتها یی است که در عالم واقعی در مواردی همچون ساخت مدارهای مجتمع به عنوان قطعات مدار و یا در مسیر یابی های مختلفبه شکل مانع های جغرافیایی قابل مشاهده است . در این مقاله سعی شده با تبدیل این مسئله به مسئله گراف جواب های بهینه دست یابیم .

Keywords:

درخت اشتاینر , درخت اشتاینر کمینه اقلیدسی , درخت اشتاینر در گراف , گراف فرار