مقاله انگلیسی ترجمه شده کامپیوتر : روش های دقیق مربوط به حل مسئله فروشنده دوره گرد نامتقارن

سال نشر: ۲۰۱۳

تعداد صفحه انگلیسی: ۳۷

تعداد صفحه ترجمه فارسی:   ۴۵    صفحه word

(دانلود رایگان مقاله انگلیسی)

کد محصول:CM30

عنوان فارسی:

مقاله انگلیسی ترجمه شده روش های دقیق مربوط به حل مسئله فروشنده دوره گرد نامتقارن

عنوان انگلیسی:

Exact methods for the asymmetric traveling salesman problem

چکیده فارسی:

در این بررسی ما تمرکز خود را بر روی روش های دقیق حل مسئله فروشنده دوره گرد نامتقارن در بررسی های انجام شده، به دنبال تحقیقات افرادی چون بالاس و توس، قرار می دهیم. در بخش ۲، دو روش خاص شاخه و کران، بر مبنای حل مرتبط به مسئله گمارش بر مبنای ترمیم، نشان داده و مقایسه می گردد. در بخش ۳، روش شاخه و کران بر مبنای محاسبه کران جمع پذیر شرح داده می شود، در حالی که در بخش ۴ روش شاخه و بُرش به بحث گذاشته می شود. در نهایت در بخش ۵،  تمام این روش ها از نظر محاسباتی  بر روی مجموعه بزرگی از نمونه ها تست شده، و با کدهای قابل اجرا شاخه و بُرش برای مسئله فروشنده دوره گرد نامتقارن، مقایسه می گردند.

تعریف رسمی این مسئله به صورت زیر می باشد. فرض کنید G = (V, A) گراف جهت دار کامل باشد، به این ترتیب  به عنوان مجموعه رئوس بوده و   مجموعه کمان (منحنی) می باشد، و فرض کنید  هزینه مرتبط به کمان   باشد.

ص ۲

سیکل جهت دار هامیلتون از G به عنوان سیکل هدایت شده هر کمان v دقیقا با یک سیکل می باشد، یعنی زیرگراف جهت دار فراگیر  از G به گونه ای که  و   شدیدا مرتبط به هم می باشند، یعنی برای هر کمان مجزا   دو مسیر از i تا j و از j تا i  در   وجود دارد.

مسئله فروشنده دوره گرد نامتقارن( ATSP) بر مبنای یافتن سیکل جهت دار هامیلتون   از G بوده که هزینه  حداقل می باشد. بدون از دست رفتن عمومیت، ما  را برای هر کمان در نظر می گیریم. فرمول برنامه نویسی خطی اعداد صحیح زیر از ATSP شناخته شده می باشد.

تمامی حقوق مادی و معنوی ترجمه ها برای پارس ترجمه محفوظ می باشد

تمامی حقوق مادی و معنوی ترجمه ها برای پارس ترجمه محفوظ می باشد