الگوریتم سازگاری کمان - ویکی‌پدیا، دانشنامهٔ آزاد

الگوریتم سازگاری یال (به انگلیسی: 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 تعداد کمان‌ها است.

منابع[ویرایش]

• فصل ششم کتاب هوش مصنوعی: رهیافتی نوین – نوشته راسل و پیتر نورویگ – ویرایش سوم - ۲۰۰۹