الگوریتم سازگاری کمان
الگوریتم سازگاری یال (به انگلیسی: Arc consistency) که سازگاری قوس یا سازگاری گنبدی نیز ترجمه شده است. الگوریتمی برای حل مسائل ارضای محدودیت یا (Constraint satisfaction problem) میباشد. در این روش سازگاری حالتها با کمان نشان داده شده و سعی میشود با حذف تدریجی مقادیر ناسازگار جواب مناسب را پیدا کرد. اگر X و Y دو متغیر در یک مسئله ارضای محدودیت باشند آنگاه X → Y سازگار کمان است، اگر و فقط اگر به ازای تمامی مقادیر x از X، مقداری مجاز برای Y موجود باشد. معروفترین الگوریتم برای این کار الگوریتم سازگاری کمان ۳ یا به اختصار AC-3 میباشد.
الگوریتم سازگاری یال ۳
الگوریتم یک صف از کمانها تشکیل میدهد.
هر بار یک کمان X → Y از صف انتخاب شده و سازگاری کمان برای آن بررسی میشود.
اگر دامنه X تغییری نکرد، به سراغ کمان بعدی میرود.
اگر دامنه X تغییر کرد، کمانهای Z → X برای تمام همسایههای X را به صف اضافه میکند.
اگر دامنه X تهی شد، مسئله جواب ندارد.
الگوریتم AC-3 در بدترین مورد از مرتبه(O (ed است که d حداکثر اعضای دامنه هر گره و c تعداد کمانها است.
منابع
- فصل ششم کتاب هوش مصنوعی: رهیافتی نوین – نوشته راسل و پیتر نورویگ – ویرایش سوم - ۲۰۰۹
- Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice Hall, 2009