نمذجة مسألة على هيئة قيود

عامل مسارُ البحث المسألةَ معاملةَ الصندوق الأسود: حالة ابتدائية، ومجموعة أفعال، واختبار هدف. وذلك يعمل، غير أن الحلّال لا يتعلّم شيئًا عن سبب سوء حالةٍ ما. أما مسألة إرضاء القيود فتفتح الصندوق. صُغ المسألة في صورة قياسية، فيصير بوسع حلّال عامّ أن يستدلّ على بنيتها دون أن يعرف موضوعها.

الصورة القياسية

مسألة إرضاء القيود ثلاثة أشياء.

• مجموعة متغيّرات $X_1, \dots, X_n$.
• ومجال $D_i$ لكلٍّ منها، أي القيم التي يجوز أن يأخذها.
• ومجموعة قيود، يقيّد كلٌّ منها القيمَ التي يجوز لمجموعة جزئية من المتغيّرات أن تأخذها في آنٍ واحد.

والإسناد يعطي قيمًا لبعض المتغيّرات أو لها جميعًا. وهو متّسق إن لم يخرق أي قيد، وتامّ إن كان لكل متغيّر قيمة، وحلّ إن كان الأمرين معًا.

المثال: تلوين خريطة

لوّن كل إقليم من أقاليم أستراليا بحيث لا يشترك إقليمان متجاوران في لون. سبعة متغيّرات - أستراليا الغربية، والإقليم الشمالي، وكوينزلاند، ونيو ساوث ويلز، وفيكتوريا، وأستراليا الجنوبية، وتسمانيا - لكلٍّ منها المجال $\{\text{red}, \text{green}, \text{blue}\}$، وقيدٌ واحد لكل حدود مشتركة:

$$\mathrm{WA} \neq \mathrm{NT},\quad \mathrm{WA} \neq \mathrm{SA},\quad \mathrm{NT} \neq \mathrm{SA},\quad \mathrm{NT} \neq \mathrm{Q},\quad \mathrm{SA} \neq \mathrm{Q},$$ $$\mathrm{SA} \neq \mathrm{NSW},\quad \mathrm{SA} \neq \mathrm{V},\quad \mathrm{Q} \neq \mathrm{NSW},\quad \mathrm{NSW} \neq \mathrm{V} .$$

تسعة قيود. وتسمانيا جزيرة، فلا تظهر في أيٍّ منها.

بيان القيود

ارسم عقدة لكل متغيّر وحرفًا لكل قيد ثنائي، فيكون لديك بيان القيود. وشكله هو الخريطة الوحيدة التي يملكها الحلّال عن المسألة، وأنفع ما يُقرأ منه هو الدرجة، أي عدد القيود التي يشارك فيها المتغيّر:

$$\begin{array}{ll} \mathrm{SA} & 5 \\ \mathrm{NT},\ \mathrm{Q},\ \mathrm{NSW} & 3 \\ \mathrm{WA},\ \mathrm{V} & 2 \\ \mathrm{T} & 0 \end{array}$$

تحادّ أستراليا الجنوبية كل أقاليم البرّ الرئيس. واختيار لونها يقيّد خمسة متغيّرات أخرى فورًا، ولهذا يسند الدرسُ الثالث المتغيّراتِ عالية الدرجة أولًا. أما تسمانيا فلا تقيّد شيئًا، فلونها حرّ: وذلك وحده يخبرك أن الحلول تأتي في مجموعات من ثلاثة.

وهناك 18 تلوينًا صحيحًا في المجموع، أي ستة تلوينات متمايزة للبرّ الرئيس مضروبة في ثلاثة خيارات لتسمانيا.

لوّنها بنفسك أدناه، وراقب القراءة الثانية لا الأولى. فهي تعدّ التلوينات السليمة التي ما زالت تُتمّ ما أسندته، وهي تصحّح قراءتين للفقرة السابقة.

تثبيت منطقة واحدة أيًّا كانت يُبقي ستّ تتمّات بالضبط. أستراليا الجنوبيّة بحدودها الخمس، وتسمانيا بلا حدود: ستٌّ في الحالتين، لأنّ الألوان الثلاثة متبادلة، فكلّ منطقة تأخذ كلّ لون في ثلث الحلول. فالدرجة العالية تشتري بحثًا أقلّ لا أجوبة أقلّ. وهي دعوى أضعف ممّا تبدو، وهي التي يحتاجها درس الاستدلالات حقًّا.

ثمّ اضغط الطريق المسدود الصامت. أستراليا الغربيّة حمراء مع كوينزلاند خضراء لا تخرق أيّ قيد، ولها صفر من التتمّات: فالإقليم الشماليّ وأستراليا الجنوبيّة لا يبقى لكلّ منهما إلّا الأزرق، وهما متجاوران. فالإسناد الجزئيّ المتّسق ليس بالضرورة قابلًا للإتمام. ولا شيء في الصورة القياسيّة ينتبه لذلك، ولهذا بعينه وُجد الدرس التالي.

الإبدالية، ولماذا تساوي 5,040

يعامل البحث الساذج «أسند WA ثم NT» و«أسند NT ثم WA» فرعين مختلفين. وعُدّ أوراق تلك الشجرة: $n!$ ترتيبًا مضروبة في $d^n$ تركيبة قيم،

$$7! \times 3^7 = 5{,}040 \times 2{,}187 = 11{,}022{,}480 .$$

لكن مسائل إرضاء القيود إبدالية: فتطبيق مجموعة من الإسنادات بأي ترتيب يبلغ الإسنادَ الجزئي نفسه. ومن ثمّ فالترتيب لا يحمل أي معلومة، وللحلّال أن يثبّت متغيّرًا واحدًا في كل مستوى من الشجرة. فيصير عدد الأوراق

$$d^n = 3^7 = 2{,}187 ,$$

أي أصغر بعامل $5{,}040$، ودون أي تنازل. وهذا ليس إرشادًا ولا تقريبًا؛ بل هو حشو في الصياغة الساذجة ما كان ينبغي أن يوجد أصلًا. وكل خوارزمية في هذا المسار تفترضه.

الصورة نفسها، مسائل أخرى

والمقصود من الصورة القياسية أن تحطّ فيها مسائل لا صلة بين بعضها وبعض.

• الجدولة. متغيّر واحد لكل مهمّة، قيمته زمن بدئها. وقيدُ الأسبقية القائل بأن المهمّة $T_1$ ذات المدّة $d_1$ تنتهي قبل أن تبدأ $T_2$ هو $T_1 + d_1 \le T_2$. والموعد النهائي تقييد على كل مجال. والأداة المشتركة تصير قيدًا فصليًا: إمّا $A + 10 \le B$ وإمّا $B + 10 \le A$.
• السودوكو. واحد وثمانون متغيّرًا، واحد لكل مربّع، بالمجال $\{1, \dots, 9\}$ ومجالات أحادية للمعطيات. وسبعة وعشرون قيدَ اختلافٍ تامّ، واحد لكل صفّ وعمود وصندوق.
• الملكات الثماني. متغيّر واحد لكل عمود، قيمته الصفّ، مع قيود تمنع وجود ملكتين على صفّ واحد أو قطر واحد.

ولا تحتاج أيٌّ من هذه إلى حلّال مفصّل على قياسها. فالشيفرة نفسها تنطبق على الثلاث جميعًا، لأن الاستدلال الذي تجريه - تقليصَ المجالات، واختيارَ المتغيّر الذي يُجرَّب تاليًا - تسوقه القيودُ لا موضوع المسألة.

الصورة قياسية، أما الصعوبة فلا. إرضاء القيود تامّ في NP عمومًا، وكتابة مسألة في هذه الصورة لا تجعلها سهلة. وإنما الذي تشتريه هو أن كل البراعة يمكن أن تسكن في حلّال واحد بدل أن يُعاد اختراعها لكل مسألة على حدة.

أبعد من المجالات المنتهية

لا يلزم أن تكون المجالات صغيرة ولا حتى منتهية. فقد يكون المجال المنفصل غير منتهٍ، كالأعداد الصحيحة، وعندئذ لا يمكن سرد القيود أزواجًا مسموحة، بل تلزم لغة قيود للتعبير عن $T_1 + d_1 \le T_2$ مباشرةً. وللقيود الخطّية على الأعداد الصحيحة حلّالات مخصّصة؛ أما القيود غير الخطّية العامة على الأعداد الصحيحة فلا حلّالات لها، ولا يمكن أن تكون، إذ لا توجد خوارزمية لها أصلًا.

قبل الاختبار

كن قادرًا على كتابة مسألة بمتغيّرات ومجالات وقيود، ورسم بيان القيود وقراءة الدرجة منه، وشرح ما الذي تزيله الإبدالية وكم تساوي هنا، والتعرّف على الصورة نفسها في الجدولة والسودوكو.