دوره 19، شماره 2 - ( 2-1401 )
جلد 19 شماره 2 صفحات 91-77 |
برگشت به فهرست نسخه ها
دانشگاه صنعتی سهند، گروه ریاضی کاربردی، تبریز
چکیده: (821 مشاهده)
مساله درخت فراگیر ماکس + سام، یک درخت فراگیرT* را در گراف G پیدا می‌کند که دارای مینیمم وزن ترکیبی max w(e)+Sum c(e) است و در آن w(e) وزن و c(e) هزینه یالe ͼE می‌باشند. این مساله در زمان O(mlog n) حل می‌شود که در آن m تعداد یال‌ها و n تعداد رئوس گراف می‌باشد. در مساله درخت فراگیر ماکس + سام معکوس یک درخت فراگیر مفروض از گراف G که یک درخت فراگیر ماکس + سام بهینه نیست، در نظر گرفته می‌شود. سپس بردار وزنw به w̅ اصلاح می‌شود به‌طوری‌که درخت مفروض به یک درخت فراگیر ماکس + سام بهینه تبدیل گردد. هدف این است که هزینه تغییرات||w̅-w|| تحت فاصله همینگ مینیمم شود. در این مقاله هدف ارایه یک روش جدید برای حل مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن نوع تنگنا می‌باشد. ابتدا مساله را فرمول‌بندی کرده و سپس یک الگوریتم ترکیبیاتی با زمان اجرای O(mlog n)برای حل آن پیشنهاد می‌شود. در آخر یک مثال عددی برای نشان دادن کارایی روش پیشنهادی ارایه می‌شود.
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |