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

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

Keywords:

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