مساله مكان‌يابي مركز- ميانه مسير استوار با وزن‌هاي راسي بازه‌اي روي شبكه هاي درختي

هدف: در اين مقاله، مساله مكان يابي مركز-ميانه مسير استوار روي شبكه هاي درختي با وزن هاي راسي بازه اي يكسان براي هر دو مساله ميانه مسير و مركز مسير مورد بررسي قرار مي گيرد. تابع هدف استفاده شده در اين مقاله، جمع ساده تابع هدف مساله ميانه مسير و مركز مسير است. در كارهايي كه در ادبيات تحقيقي صورت گرفته است، وزن ريوس براي هر دو مساله مكان يابي ميانه مسير و مركز مسير مجزا در نظر گرفته شده است. روش شناسي پژوهش: رويكرد استفاده شده براي محاسبه جواب استوار، رويكرد مينيماكس پشيماني است. در اين رويكرد، بيشترين مقدار پشيماني براي هر مسير انتخاب شده روي شبكه ي درختي، به ازاي تمامي رخدادهاي ممكن براي وزن هاي راسي گراف هاي درختي مينيمم مي شود. يافته ها: با استفاده از رويكرد مينيماكس پشيماني، يك الگوريتم تركيبياتي با زمان اجراي O(n^5) براي محاسبه جواب استوار مساله مركز-ميانه مسير استوار روي شبكه هاي درختي ارائه مي شود. اصالت/ارزش افزوده علمي: در اين مقاله، با استفاده از سناريوهاي بدترين حالت مسايل مركز مسير و ميانه مسير، سناريوهاي بدترين حالت مساله مركز-ميانه مسير استوار پيدا شده و با استفاده از آن، يك جواب استوار براي مساله مورد نظر محاسبه مي شود.