TY - JOUR T1 - Inverse Max+Sum Spanning Tree Problem under Weighted Sum-Type Hamming Distance by Modifying the Max-Weight Vector TT - مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن JF - JAMLU JO - JAMLU VL - 19 IS - 2 UR - http://jamlu.liau.ac.ir/article-1-1911-fa.html Y1 - 2022 SP - 77 EP - 91 KW - Max+Sum Spanning Tree Problem KW - Inverse Optimization KW - Hamming Distance N2 - مساله درخت فراگیر ماکس + سام، یک درخت فراگیر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)برای حل آن پیشنهاد می‌شود. در آخر یک مثال عددی برای نشان دادن کارایی روش پیشنهادی ارایه می‌شود. M3 10.52547/jamlu.19.2.77 ER -