دانلود مقاله ISI انگلیسی شماره 79783
عنوان فارسی مقاله

بازنگری برنامه نویسی پویا برای یافتن زیر درخت مطلوب در درختان ☆

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79783 2007 14 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Revisiting dynamic programming for finding optimal subtrees in trees ☆
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : European Journal of Operational Research, Volume 177, Issue 1, 16 February 2007, Pages 102–115

کلمات کلیدی
ابتکارات؛ برنامه نویسی پویا؛ بهینه سازی ترکیبی
پیش نمایش مقاله
پیش نمایش مقاله بازنگری برنامه نویسی پویا برای یافتن زیر درخت مطلوب در درختان ☆

چکیده انگلیسی

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.