مسئله درخت اشتاینر

دانشنامه عمومی

مسئله درخت اشتاینر ( به انگلیسی: Steiner tree problem یا minimum Steiner tree problem ) ، که به افتخار یاکوب اشتاینر مبدع آن نام گذاری شده، کوچکترین درخت وزن داری است که شامل تعدادی از گره های خاص به نام ترمینال باشد.
در این مسئله یک گراف وزن دار ( G= ( V، E و یک زیرمجموعه از رئوس گراف ( T⊆V ) که مجموعه ترمینال ها نام دارد ارائه می گردد و هدف پیدا کردن ( 'GT= ( V'، E با کمترین هزینه است که. E'⊆Eو T⊆V'⊆V
مسئله درخت اشتاینر دارای کاربردهای فراوانی نظیر مسیریابی یک به چند در شبکه های رایانه ای، سامانه های ترابری، پلیس امداد، ایستگاه های پستی و کاربردهای دیگر می باشد.
مسئله درخت اشتاینر با مسئله درخت پوشای مینیمم مشابهت دارد: فرض کنید مجموعه رئوس V داده شده اند، می خواهیم آنها را با یک گراف با کمترین وزن به هم متصل کنیم. به طوری که حاصل جمع وزنهای همه یالها کمینه شود. تفاوت بین مسئله درخت اشتاینر و مسئله درخت پوشای مینیمم این است که در مسئله درخت اشتاینر، رئوس میانه و یال ممکن است به گراف اضافه شوند تا وزن درخت پوشا را کاهش دهند. این رئوس جدید برای کاهش وزن کلی اتصالات معرفی می شوند و نقاط اشتاینر یا رئوس اشتاینر نام دارند. ثابت شده است که اتصالات به دست آمده یک درخت را تشکیل می دهند، که درخت اشتاینر نام دارد. ممکن است برای مجموعه ای از رئوس درختهای اشتاینر زیادی وجود داشته باشند.
مسئله درخت اشتاینر در طراحی فیزیکی مدارات VLSI یا شبکه نیز کاربرد فراوانی دارد. بسیاری از نسخه های مسئله اشتاینر ان پی کامل هستند.
این مسئله انواع مختلفی دارد. دریک نوع آن تعدادی نقطه بر روی صفحه دو بعدی به عنوان ورودی ارائه میگردد و هدف، تولید درختی بر روی صفحه اقلیدسی است، که دارای کمترین هزینه بوده و همه نقاط را در بر بگیرد. همین مسئله به صورت عمود بر هم نیز مطرح می شود که در آن باید خطوط درخت فقط به صورت عمودی یا افقی رسم شوند که این مسئله در طراحی فیزیکی مدارات VLSI کاربرد فراوانی دارد.
مشکل اصلی که ما با آن روبرو شدیم هندسه درخت اشتاینر بود: در طرح N نقطه داده شده است. هدف اتصال آنها به وسیله خطوطی است که کمترین وزن را داشته باشند. به طوری که هر دو نقطه یا به طور مستقیم ( مسیری به طول یک ) یا از طریق رئوس دیگر ( مسیری به طول بیشتر از یک ) به هم متصل هستند. این ممکن است به این صورت نشان داده شود که خطوط یکدیگر را قطع نمی کنند مگر در نقاط پایانی و درخت را تشکیل می دهند. برای مسئله اشتاینر اقلیدسی نقاطی که به گراف اضافه می شوند ( نقاط اشتاینر ) باید از درجه ۳ با شند. و سه لبهٔ متلاقی در یک نقطه باید با هم زاویه ۱۲۰ درجه را بسازند. این حد اکثر نقاط اشتاینر را به دنبال دارد که یک درخت اشتاینر می تواند حداکثر N - ۲ نقطه اشتاینر داشته باشد، که N تعداد نقاط داده شده است. مسئله اشتاینر اقلیدسی یک ان پی سخت است و بنابراین به عنوان جوابی بهینه برای الگوریتم های محسوب نمی شود.
عکس مسئله درخت اشتاینر
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس