پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,245 |
| تعداد مقالات | 67,896 |
| تعداد مشاهده مقاله | 115,552,585 |
| تعداد دریافت فایل اصل مقاله | 90,322,935 |
Speeding up the Arc Consistency algorithm in Constraint Satisfaction Problems: A New Modification of AC-3 | ||
| Journal of Algorithms and Computation | ||
| دوره 54، شماره 1، شهریور 2022، صفحه 125-138 اصل مقاله (1.54 M) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2022.88375 | ||
| نویسنده | ||
| Yaser Shokri Kalandaragh,* | ||
| Department of Advanced Technologies, University of Mohaghegh Ardabili. | ||
| چکیده | ||
| Dealing with constraints is always very common in real-world implementation issues. Search algorithms for real problems are also no exception. Because of the constraints in search problems (named Constraint Satisfaction Problems (CSPs)), their main solving algorithm is presented in backtracking form. The constraint propagation algorithm is an auxiliary tool to avoid facing constraint conditions as well as reducing search options. This algorithm has been presented in almost seven versions so far. In this paper, we have updated the third version of this algorithm, which is presented under the title of AC-3, from five aspects and have increased its capabilities. The most important feature of our proposed algorithm is its low time complexity. This feature has been made possible by two auxiliary criteria introduction for detecting more critical binary constraints. Faster investigation of critical constraints leads to early detection of dead-end in the search path and the search continues in this direction stops. | ||
| کلیدواژه‌ها | ||
| Search Algorithm؛ Constraint Satisfaction؛ Constraint Propagation؛ Arc Consistency؛ Binary Constraint | ||
|
آمار تعداد مشاهده مقاله: 127 تعداد دریافت فایل اصل مقاله: 228 |
||