کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141496 1489496 2015 35 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Shortest path algorithms for functional environments
ترجمه فارسی عنوان
کوتاهترین الگوریتم مسیر برای محیط های عملکردی
کلمات کلیدی
کوتاهترین الگوریتم مسیر، بهینه سازی ترکیبی، شبکه های، مشکلات تصمیم گیری متوالی جریان عمومی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی

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
نویسندگان
,