حل مسایل درخت اشتاینر در بهینه سازی شبکه های ارتباطات کامپیوتری با استفاده از روش های فراابتکاری

مرتبط کردن یک مجموعه از نقاط داده شده با کمترین هزینه، به عنوان یکی از مهمترین مسایل در طراحی شبکههای ارتباطات کامپیوتری یا به طور خاص مخابراتی مطرح است. مسایل مرتبط را می توان هم در فضاهای متریکا و هم در گراف ها مدل سازی نمود. مسیله ی درخت اشتاینر برای گراف های وزن دار، به دنبال یک زیر گراف پوششی برای یک مجموعه از راس های مشخص به نام نقاط ترمینال می باشد. مسیله ی درخت اشتاینر کلاسیک، عبارتست از پیدا کردن کوتاهترین شبکه، به طوریکه این نقاط را طوری به هم مرتبط کند که مجموع طول یالها در این شبکه کمینه شود. این مقاله به معرفی مسیله و برخی ازروشهای فراابتکاری (meta-heuristics) موجود می پردازد.

Keywords:

مسایل بهینه سازی ترکیباتی , مسیله ی درخت اشتاینر , روشی های فراابتکاری