بهینه سازی استوار
فهیمه باروقی؛ سودابه سیدی قمی
چکیده
در این مقاله، مساله مکانیابی مرکز-میانه مسیر استوار روی شبکههای درختی با وزنهای راسی بازهای یکسان برای هر دو مساله میانه مسیر و مرکز مسیر مورد بررسی قرار میگیرد. تابع هدف استفاده شده در این مقاله، جمع ساده تابع هدف مساله میانه مسیر و مرکز مسیر است. در کارهایی که در ادبیات تحقیقی صورت گرفته است، وزن رئوس برای هر دو مساله مکانیابی میانه ...
بیشتر
در این مقاله، مساله مکانیابی مرکز-میانه مسیر استوار روی شبکههای درختی با وزنهای راسی بازهای یکسان برای هر دو مساله میانه مسیر و مرکز مسیر مورد بررسی قرار میگیرد. تابع هدف استفاده شده در این مقاله، جمع ساده تابع هدف مساله میانه مسیر و مرکز مسیر است. در کارهایی که در ادبیات تحقیقی صورت گرفته است، وزن رئوس برای هر دو مساله مکانیابی میانه مسیر و مرکز مسیر مجزا در نظر گرفته شده است. رویکرد استفاده شده برای محاسبه جواب استوار، رویکرد مینیماکس پشیمانی است. با استفاده از رویکرد مینیماکس پشیمانی، یک الگوریتم ترکیبیاتی با زمان اجرای O(n^5) برای محاسبه جواب استوار مساله مرکز-میانه مسیر استوار روی شبکههای درختی ارائه میشود. در این مقاله، با استفاده از سناریوهای بدترین حالت مسائل مرکز مسیر و میانه مسیر، سناریوهای بدترین حالت مساله مرکز-میانه مسیر استوار پیدا شده و با استفاده از آن، یک جواب استوار برای مساله مورد نظر محاسبه میشود.
