کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141496 | 1489496 | 2015 | 35 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Shortest path algorithms for functional environments
ترجمه فارسی عنوان
کوتاهترین الگوریتم مسیر برای محیط های عملکردی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کوتاهترین الگوریتم مسیر، بهینه سازی ترکیبی، شبکه های، مشکلات تصمیم گیری متوالی جریان عمومی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
This research generalises classic shortest path algorithms to network environments in which arc-costs are governed by functions, rather than fixed weights. We show that the asymptotic efficiency of our algorithms is identical to their classic counterparts. Previous results, since Knuth in 1976, require several restrictive assumptions on the functions permitted in the network. In contrast, our algorithms require only monotonicity. We present examples illustrating that this is the largest class of functions to which classic algorithms can be generalised. Applications of this work include critical path extensions to solve sequential decision-problems, and generalised network flow with nonlinear gain functions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 18, November 2015, Pages 217–251
Journal: Discrete Optimization - Volume 18, November 2015, Pages 217–251
نویسندگان
Louis Boguchwal,