الگوریتم های بهینه با زمان اجرای O(nlogn) برای مدل های مکان یابی p- ماکسین معکوس روی درخت ها تحت نرم های چبی شف و همینگ

در این مقاله مدل مکان یابی p - ماکسین معکوس با تغییرات طول یالی روی شبکه درختی مورد مطالعه قرار می گیرند. در این مسیله هدف تغییر طول های یالی درخت تحت مطالعه با صرف کمترین هزینه کلی است به طوری که یک مجموعه از پیش تعیین شده p- عضوی از راس های درخت به مکان p- ماکسین درخت تبدیل گردد. ابتدا الگوریتم های جواب بهینه با زمان اجرای O(nlog n) برای مدل تحت مطالعه روی شبکه های درختی تحت نرم چبی شف و فاصله همینگ تنگنا ارایه می شود. در ادامه نشان داده می شود اگر ضرایب هزینه اعداد فازی تعمیم یافته باشند، آنگاه می توان مدل p- ماکسین معکوس فازی را تحت نرم های چبی شف و همینگ تنگا در زمان O(n log n_) حل کرد.

Keywords:

مکان p- ماکسین , بهینه سازی ترکیباتی , بهینه سازی معکوس , بهینه سازی فازی , آنالیز پیچیدگی