کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4635690 | 1340713 | 2007 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The dragon war
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This article presents an approach to solve the travelling salesman problem using linear optimisation with a suitable set of constraints. Such approaches are well known as Cutting Plane methods but previously applied algorithms still suffer from the NP-completeness of the problem causing an exponential number of computational steps in the worst case. The method presented in this paper both tolerates non-integer results for a dedicated class of solutions (symmetric solutions) and avoids other ones (asymmetric solutions). It is thus able to deal with the inherent complexity of the travelling salesman problem.Therefore the overall complexity of the optimisation algorithm remains polynomial in the worst case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 186, Issue 1, 1 March 2007, Pages 907-914
Journal: Applied Mathematics and Computation - Volume 186, Issue 1, 1 March 2007, Pages 907-914
نویسندگان
Joachim Mertz,