خوارزمية AC-3

في مجال إرضاء القيود ، تُعد خوارزمية AC-3 (اختصارًا لخوارزمية اتساق القوس رقم 3) إحدى الخوارزميات المستخدمة لحل مسائل إرضاء القيود (CSPs). وقد طوّرها آلان ماكوورث عام 1977. غالبًا ما تُعتبر خوارزميات AC السابقة غير فعّالة، ويصعب تطبيق العديد من الخوارزميات اللاحقة، لذا تُعدّ AC-3 الأكثر شيوعًا في التدريس والاستخدام في برامج حل القيود البسيطة. يجب عدم الخلط بين خوارزمية AC-3 وخوارزمية A3C المستخدمة في التعلّم الآلي والتي تحمل اسمًا مشابهًا . ^{[ 1 ]}

يعتمد نظام AC-3 على القيود والمتغيرات ونطاقات هذه المتغيرات. يمكن للمتغير أن يأخذ أيًا من عدة قيم منفصلة؛ وتُعرف مجموعة القيم لمتغير معين بنطاقه . أما القيد فهو علاقة تحدد أو تقيد القيم التي يمكن أن يأخذها المتغير. وقد يشمل القيد قيم متغيرات أخرى.

يمكن تمثيل الحالة الحالية لمسألة إرضاء القيود (CSP) أثناء تنفيذ الخوارزمية كرسم بياني موجه ، حيث تمثل العقد متغيرات المسألة، وترتبط هذه المتغيرات بقيود متناظرة عبر الحواف أو الأقواس. يمثل كل قوس في قائمة العمل قيدًا يجب التحقق من اتساقه . تبدأ خوارزمية AC-3 بفحص الأقواس بين أزواج المتغيرات ( x ، y ). وتزيل القيم غير المتسقة مع القيود بين x و y من نطاق x . تحتفظ الخوارزمية بمجموعة من الأقواس التي لم يتم التحقق منها بعد؛ فعندما تُزال أي قيم من نطاق متغير ما، تُضاف جميع أقواس القيود التي تشير إلى هذا المتغير المُزال (باستثناء قوس القيد الحالي) إلى المجموعة. ولأن نطاقات المتغيرات محدودة، ويتم إزالة قوس واحد أو قيمة واحدة على الأقل في كل خطوة، فإن هذه الخوارزمية مضمونة الانتهاء .

للتوضيح، إليك مثال على مسألة قيود بسيطة للغاية: المتغير X له القيم الممكنة {0، 1، 2، 3، 4، 5}، ومجموعة هذه القيم هي مجال X ، أو D( X ). المتغير Y له المجال D( Y ) = {0، 1، 2، 3، 4، 5، 6، 7، 8، 9}. مع القيدين C1 = " يجب أن يكون X زوجيًا" و C2 = " يجب أن يكون مجموع X و Y يساوي 4"، نحصل على مسألة إرضاء قيود (CSP) يمكن لـ AC-3 حلها. لاحظ أن الرسم البياني الفعلي للقيود الذي يمثل هذه المسألة يجب أن يحتوي على ضلعين بين X و Y لأن C2 غير موجه، بينما تمثيل الرسم البياني الذي يستخدمه AC-3 موجه.

يحلّ AC-3 المشكلة بإزالة القيم غير الزوجية من نطاق X كما هو مطلوب في C1 ، ليصبح D( X ) = {0, 2, 4}. ثم يفحص الأقواس بين X و Y التي يُشير إليها C2 . تُطابق الأزواج ( X = 0, Y = 4)، و( X = 2, Y = 2)، و( X = 4, Y = 0) فقط القيد C2 . وبذلك ينتهي AC-3، حيث D( X ) = {0, 2, 4} وD( Y ) = {0, 2, 4}.

يُعبّر عن AC-3 بلغة شبه رمزية كما يلي:

المدخلات: مجموعة من المتغيرات X مجموعة من المجالات D(x) لكل متغير x في X. تحتوي D(x) على القيم الممكنة لـ x، من vx0 إلى vxn. مجموعة من القيود الأحادية R1(x) على المتغير x التي يجب استيفاؤها مجموعة من القيود الثنائية R2(x, y) على المتغيرين x و y التي يجب استيفاؤها الناتج: نطاقات متسقة مع قوس لكل متغير. دالة ac3(X, D, R1, R2) // يتم جعل المجالات الأولية متوافقة مع القيود الأحادية. لكل x في X D(x) := { vx in D(x) | vx satifies R1(x) } // تحتوي قائمة العمل على جميع الأقواس التي نرغب في إثبات اتساقها أو عدم اتساقها. قائمة العمل := { (س، ص) | توجد علاقة R2(س، ص) أو علاقة R2(ص، س) } يفعل حدد أي قوس (س، ص) من قائمة العمل قائمة العمل := قائمة العمل - (س، ص) إذا كان arc-reduce (x, y) صحيحًا، وإذا كانت D(x) فارغة، فأرجع فشلًا. وإلا قائمة العمل := قائمة العمل + { (z, x) | z != y ويوجد علاقة R2(x, z) أو علاقة R2(z, x) } طالما أن قائمة العمل ليست فارغة دالة arc-reduce(x, y) منطقي change = خطأ لكل vx في D(x) أوجد قيمة vy في D(y) بحيث تحقق vx و vy القيد R2(x, y) إذا لم يكن هناك مثل هذا vy { D(x) := D(x) - vx التغيير := صحيح } إرجاع المبلغ

تتمتع الخوارزمية بتعقيد زمني في أسوأ الحالات يبلغ O ( ed ³ ) وتعقيد مكاني يبلغ O ( e )، حيث e هو عدد الأقواس و d هو حجم أكبر مجال.

• أ. ك. ماكوورث. الاتساق في شبكات العلاقات . الذكاء الاصطناعي ، 8:99-118، 1977.
• ستيوارت ج. راسل وبيتر نورفيج . الذكاء الاصطناعي: منهج حديث ، 202-233، 2003.