کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
376955 | 658346 | 2012 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A general model and thresholds for random constraint satisfaction problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we study the relation among the parameters in their most general setting that define a large class of random CSP models d-k-CSP where d is the domain size and k is the length of the constraint scopes. The model d-k-CSP unifies several related models such as the model RB and the model k-CSP. We prove that the model d-k-CSP exhibits exact phase transitions if increases no slower than the logarithm of the number of variables. A series of experimental studies with interesting observations are carried out to illustrate the solubility phase transition and the hardness of instances around phase transitions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 193, December 2012, Pages 1-17
Journal: Artificial Intelligence - Volume 193, December 2012, Pages 1-17