مسأله معکوس میانه با حفظ میانه موجود روی درختها

در این مقاله حالت خاصی از مسأله معکوس ۱- میانه، تحت عنوان مسأله معکوس ۱- میانه با حفظ رأس میانه موجود روی درختهای وزن دار را بررسی می کنیم. هدف از این مسأله تغییر وزن رئوس درخت مفروض در محدوده کران داده شده با کمترین هزینه است، به طوری که رأس از پیش مشخص شده روی درخت مفروض، رأس ۱- میانه درخت تغییر یافته شود و شرط بھینگی برای رأس ۱- میانه درخت اولیه تحت تغییرات صورت گرفته حفظ شود. در ابتدا ما مدل ریاضی این مسأله را بیان می کنیم و سپس یک الگوریتم حریصانه برای این مسأله ارائه می کنیم. در نهایت نیز جهت درک بهتر مدل و کارایی الگوریتم ارائه شده مثال عددی بیان می کنیم.

Keywords:

مسأله معکوس ۱- میانه , شرط بهینگی , درخت , زیردرخت ماکسیمال