کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543784 | 1489581 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Incremental versus non-incremental dynamic programming
ترجمه فارسی عنوان
برنامه نویسی پویا و غیر افزایشی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه نویسی دینامیک، برنامه شاخه ای گرمسیری، مرزهای کمبود پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Many dynamic programming algorithms for discrete optimization problems are pure in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even incremental in that one of the inputs to the addition operations is a variable. We present an explicit optimization problem such that it can be solved by a pure DP algorithm using a polynomial number of operations, but any incremental DP algorithm for this problem requires a super-polynomial number of operations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 46, Issue 3, May 2018, Pages 278-281
Journal: Operations Research Letters - Volume 46, Issue 3, May 2018, Pages 278-281
نویسندگان
Stasys Jukna,