کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
376882 | 658329 | 2014 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The unbiased black-box complexity of partition is polynomial
ترجمه فارسی عنوان
پیچیدگی سیاه و سفید بی طرف پارتیشن چندجملهای است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جستجوی اکتشافی، تجزیه و تحلیل زمان اجرا، محاسبات تکاملی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
Unbiased black-box complexity was introduced as a refined complexity model for random-ized search heuristics (Lehre and Witt (2012) [24]). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste et al. (2006) [10].We show that for some problems the unbiased black-box complexity remains artificially small. More precisely, for two different formulations of an NPNP-hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O(nlogn)O(nlogn). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 216, November 2014, Pages 275–286
Journal: Artificial Intelligence - Volume 216, November 2014, Pages 275–286
نویسندگان
Benjamin Doerr, Carola Doerr, Timo Kötzing,