خوارزمية كنوت X

الخوارزمية X هي خوارزمية لحل مسألة التغطية الدقيقة . وهي خوارزمية بسيطة تكرارية ، غير حتمية ، تعتمد على البحث العميق أولاً ، وتستخدم التراجع، وقد استخدمها دونالد كنوث لعرض تطبيق فعال يُسمى DLX، والذي يستخدم تقنية الروابط الراقصة . ^{[ 1 ]}^{[ 2 ]}

الخوارزمية

تُمثل مشكلة التغطية الدقيقة في الخوارزمية X بمصفوفة وقوع A تتكون من 0 و1. والهدف هو اختيار مجموعة فرعية من الصفوف بحيث يظهر الرقم 1 في كل عمود مرة واحدة فقط.

تعمل الخوارزمية X على النحو التالي:

إذا لم يكن للمصفوفة A أي أعمدة، فإن الحل الجزئي الحالي هو حل صالح؛ يتم الإنهاء بنجاح.
وإلا فاختر العمود ج ( بشكل حتمي ).
اختر صفًا r بحيث يكون A _{r , c} = 1 ( بشكل غير حتمي ).
قم بتضمين الصف r في الحل الجزئي.
لكل عمود j بحيث يكون A _{r , j} = 1،
لكل صف i بحيث يكون A _{i , j} = 1،
حذف الصف i من المصفوفة A.
حذف العمود j من المصفوفة A.
كرر هذه الخوارزمية بشكل متكرر على المصفوفة المختزلة A.

يعني الاختيار غير الحتمي لـ r أن الخوارزمية تتكرر على خوارزميات فرعية مستقلة؛ ترث كل خوارزمية فرعية المصفوفة الحالية A ، ولكنها تُختزلها بالنسبة إلى صف مختلف r . إذا كان العمود c يساوي صفرًا بالكامل، فلا توجد خوارزميات فرعية وتنتهي العملية دون جدوى.

تُشكّل الخوارزميات الفرعية شجرة بحث بطريقة طبيعية، حيث تقع المشكلة الأصلية في الجذر، ويحتوي المستوى k على كل خوارزمية فرعية تُقابل k صفًا مُختارًا. التراجع هو عملية اجتياز الشجرة بترتيب ما قبل العمق.

أي قاعدة منهجية لاختيار العمود c في هذه العملية ستؤدي إلى إيجاد جميع الحلول، لكن بعض القواعد تعمل بشكل أفضل من غيرها. ولتقليل عدد التكرارات، يقترح كنوت أن تختار خوارزمية اختيار العمود العمود الذي يحتوي على أقل عدد من الرقم 1.

مثال

على سبيل المثال، ضع في اعتبارك مشكلة التغطية الدقيقة المحددة بواسطة الكون U = {1، 2، 3، 4، 5، 6، 7} ومجموعة المجموعات S = { A ، B ، C ، D ، E ، F }، حيث:

A = {1، 4، 7}؛
ب = {1، 4}؛
ج = {4، 5، 7}؛
D = {3، 5، 6}؛
E = {2، 3، 6، 7}؛ و
F = {2, 7}.

يتم تمثيل هذه المشكلة بالمصفوفة التالية:

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

تقوم الخوارزمية X مع الطريقة الاستدلالية التي اقترحها كنوت لاختيار الأعمدة بحل هذه المشكلة على النحو التالي:

المستوى 0

الخطوة 1 - المصفوفة ليست فارغة، لذا تستمر الخوارزمية.

الخطوة 2 - أقل عدد من الرقم 1 في أي عمود هو اثنان. العمود 1 هو أول عمود يحتوي على رقمين 1، وبالتالي يتم اختياره (بشكل حتمي):

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

الخطوة 3 - يحتوي كل من الصفين A و B على الرقم 1 في العمود 1 وبالتالي يتم اختيارهما (بشكل غير حتمي).

تنتقل الخوارزمية إلى الفرع الأول عند المستوى 1...

المستوى 1: حدد الصف أ

الخطوة 4 - الصف أ مُدرج في الحل الجزئي.

الخطوة 5 - يحتوي الصف A على الرقم 1 في الأعمدة 1 و4 و7:

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

يحتوي العمود 1 على القيمة 1 في الصفين A و B ؛ ويحتوي العمود 4 على القيمة 1 في الصفوف A و B و C ؛ ويحتوي العمود 7 على القيمة 1 في الصفوف A و C و E و F. لذا، يجب حذف الصفوف A و B و C و E و F ، والأعمدة 1 و4 و7.

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

يبقى الصف D كما هو، وتبقى الأعمدة 2 و3 و5 و6 كما هي:

	2	3	5	6
د	0	1	1	1

الخطوة 1 - المصفوفة ليست فارغة، لذا تستمر الخوارزمية.

الخطوة 2 - أقل عدد من الرقم 1 في أي عمود هو صفر، والعمود 2 هو أول عمود يحتوي على صفر من الرقم 1:

	2	3	5	6
د	0	1	1	1

وبالتالي، ينتهي هذا الفرع من الخوارزمية بشكل غير ناجح.

تنتقل الخوارزمية إلى الفرع التالي عند المستوى 1...

المستوى 1: حدد الصف ب

الخطوة 4 - الصف B مُدرج في الحل الجزئي.

يحتوي الصف B على الرقم 1 في العمودين 1 و 4:

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

يحتوي العمود 1 على القيمة 1 في الصفين A و B ؛ ويحتوي العمود 4 على القيمة 1 في الصفوف A و B و C. لذا، يجب حذف الصفوف A و B و C ، وحذف العمودين 1 و4.

	1	2	3	4	5	6	7
أ	1	0	0	1	0	0	1
ب	1	0	0	1	0	0	0
ج	0	0	0	1	1	0	1
د	0	0	1	0	1	1	0
هـ	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

تبقى الصفوف D و E و F ، وتبقى الأعمدة 2 و 3 و 5 و 6 و 7:

	2	3	5	6	7
د	0	1	1	1	0
هـ	1	1	0	1	1
F	1	0	0	0	1

الخطوة 1 - المصفوفة ليست فارغة، لذا تستمر الخوارزمية.

الخطوة 2 - أقل عدد من الرقم 1 في أي عمود هو واحد. العمود 5 هو أول عمود يحتوي على رقم 1 واحد، وبالتالي يتم اختياره (بشكل حتمي):

	2	3	5	6	7
د	0	1	1	1	0
هـ	1	1	0	1	1
F	1	0	0	0	1

الخطوة 3 - يحتوي الصف D على الرقم 1 في العمود 5 وبالتالي يتم اختياره (بشكل غير حتمي).

تنتقل الخوارزمية إلى الفرع الأول عند المستوى 2...

المستوى 2: حدد الصف د

الخطوة 4 - الصف D مدرج في الحل الجزئي.

الخطوة 5 - يحتوي الصف D على الرقم 1 في الأعمدة 3 و 5 و 6:

	2	3	5	6	7
د	0	1	1	1	0
هـ	1	1	0	1	1
F	1	0	0	0	1

يحتوي العمود 3 على القيمة 1 في الصفين D و E ؛ ويحتوي العمود 5 على القيمة 1 في الصف D ؛ ويحتوي العمود 6 على القيمة 1 في الصفين D و E. لذلك، يجب حذف الصفين D و E ، وحذف الأعمدة 3 و 5 و 6.

	2	3	5	6	7
د	0	1	1	1	0
هـ	1	1	0	1	1
F	1	0	0	0	1

يبقى الصف F كما هو، ويبقى العمودان 2 و7 كما هما:

	2	7
F	1	1

الخطوة 1 - المصفوفة ليست فارغة، لذا تستمر الخوارزمية.

الخطوة 2 - أقل عدد من الرقم 1 في أي عمود هو واحد. العمود 2 هو أول عمود يحتوي على رقم 1 واحد، وبالتالي يتم اختياره (بشكل حتمي):

	2	7
F	1	1

يحتوي الصف F على الرقم 1 في العمود 2 وبالتالي يتم اختياره (بشكل غير حتمي).

تنتقل الخوارزمية إلى الفرع الأول عند المستوى 3...

المستوى 3: حدد الصف F

الخطوة 4 - يتم تضمين الصف F في الحل الجزئي.

يحتوي الصف F على الرقم 1 في العمودين 2 و7:

	2	7
F	1	1

يحتوي العمود 2 على القيمة 1 في الصف F ؛ ويحتوي العمود 7 على القيمة 1 في الصف F. لذا، يجب حذف الصف F وحذف العمودين 2 و7.

	2	7
F	1	1

لم يتبق أي صفوف أو أعمدة:

الخطوة 1 - المصفوفة فارغة، وبالتالي ينتهي هذا الفرع من الخوارزمية بنجاح.

بما أنه تم اختيار الصفوف B و D و F (الخطوة 4)، فإن الحل النهائي في هذا الفرع هو:

	1	2	3	4	5	6	7
ب	1	0	0	1	0	0	0
د	0	0	1	0	1	1	0
F	0	1	0	0	0	0	1

بمعنى آخر، فإن المجموعة الفرعية { B , D , F } هي غطاء تام، لأن كل عنصر موجود في واحدة فقط من المجموعات B = {1, 4}، D = {3, 5, 6}، أو F = {2, 7}.

لم تعد هناك صفوف محددة في المستوى 3، وبالتالي تنتقل الخوارزمية إلى الفرع التالي في المستوى 2...

لم تعد هناك صفوف محددة في المستوى 2، وبالتالي تنتقل الخوارزمية إلى الفرع التالي في المستوى 1...

لم تعد هناك صفوف محددة في المستوى 1، وبالتالي تنتقل الخوارزمية إلى الفرع التالي في المستوى 0...

لا توجد فروع عند المستوى 0، وبالتالي تنتهي الخوارزمية.

باختصار، تحدد الخوارزمية وجود غطاء واحد دقيق فقط: S ^* = { B , D , F }.

التطبيقات

كان الهدف الرئيسي لكنوت من وصف الخوارزمية X هو إثبات جدوى الروابط المتحركة . وقد بيّن كنوت إمكانية تنفيذ الخوارزمية X بكفاءة على الحاسوب باستخدام هذه الروابط في عملية أطلق عليها اسم "DLX" . تستخدم DLX تمثيل المصفوفة لمسألة التغطية التامة ، والمُنفذة كقوائم مرتبطة ثنائياً للعناصر 1 في المصفوفة: كل عنصر 1 له رابط إلى العنصر 1 التالي له من الأعلى والأسفل واليسار واليمين. (من الناحية التقنية، ولأن القوائم دائرية، فإنها تُشكل سطحاً حلقياً ). ولأن مسائل التغطية التامة تميل إلى أن تكون متفرقة، فإن هذا التمثيل عادةً ما يكون أكثر كفاءة من حيث الحجم ووقت المعالجة المطلوب. ثم تستخدم DLX الروابط المتحركة لاختيار تباديل الصفوف بسرعة كحلول محتملة، وللتراجع (التراجع) بكفاءة عن التخمينات الخاطئة. ^{[ 1 ]}

انظر أيضاً

مراجع

1 2 كنوت، دونالد (2000). "الروابط الراقصة". arXiv : cs/0011047 .
↑ بانيرجي، بيكرامجيت؛ كريمر، لاندون؛ لايل، جيريمي (4 يوليو 2010). "التعرف على خطط الوكلاء المتعددين: الصياغة والخوارزميات" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 24 (1): 1059-1064 . doi : 10.1609/aaai.v24i1.7746 . ISSN 2374-3468 .

كنوت، دونالد إي. (2000)، "الروابط الراقصة"، في ديفيز، جيم؛ روسكو، بيل؛ وودكوك، جيم (محررون)، وجهات نظر الألفية في علوم الحاسوب: وقائع ندوة أكسفورد-مايكروسوفت لعام 1999 تكريمًا للسير توني هوار ، بالغراف، ص 187-214 ، arXiv : cs/0011047 ، Bibcode : 2000cs.......11047K ، ISBN 978-0-333-92230-9.

روابط خارجية

ورقة كنوت البحثية - ملف PDF (متوفرة أيضاً على arXiv : cs/0011047 )
ورقة كنوت التي تصف تحسين الروابط الراقصة - ملف بوستسكريبت مضغوط بصيغة Gzip.

[knuth-1] 1 2 كنوت، دونالد (2000). "الروابط الراقصة". arXiv : cs/0011047 .

[2] بانيرجي، بيكرامجيت؛ كريمر، لاندون؛ لايل، جيريمي (4 يوليو 2010). "التعرف على خطط الوكلاء المتعددين: الصياغة والخوارزميات" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 24 (1): 1059-1064 . doi : 10.1609/aaai.v24i1.7746 . ISSN 2374-3468 .

[ 1 ]

[ 2 ]