البرمجة المقيدة

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 21 صور
الموسوعة الحرة

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

تستمد البرمجة المقيدة جذورها من البرمجة المنطقية المقيدة ، ويمكن التعبير عنها في هذا السياق، حيث تُدمج القيود في برنامج منطقي . ويعود الفضل في هذا النوع من البرمجة المنطقية إلى جعفر ولاسيز [ 2 ] ، اللذين قاما في عام 1987 بتوسيع فئة محددة من القيود التي تم تقديمها في لغة برولوج 2. وكانت أولى تطبيقات البرمجة المنطقية المقيدة هي برولوج 3 ، و CLP(R) ، و CHIP .

بدلاً من البرمجة المنطقية، يمكن دمج القيود مع البرمجة الوظيفية ، وإعادة كتابة المصطلحات ، واللغات الإجرائية . تشمل لغات البرمجة التي تدعم القيود بشكل مدمج لغتي Oz (البرمجة الوظيفية) و Kaleidoscope (البرمجة الإجرائية). في الغالب، تُطبَّق القيود في اللغات الإجرائية عبر مجموعات أدوات حل القيود ، وهي مكتبات منفصلة للغة إجرائية موجودة.

برمجة المنطق المقيد

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

يكمن الاختلاف بينهما بشكل أساسي في أساليبهما ومنهجياتهما في نمذجة العالم. فبعض المسائل أسهل كتابةً (وبالتالي أبسط) باستخدام برامج منطقية، بينما يسهل كتابة مسائل أخرى باستخدام برامج قيود.

تعتمد منهجية البرمجة المقيدة على البحث عن حالة للعالم تُلبى فيها عدد كبير من القيود في آن واحد. تُصاغ المسألة عادةً على أنها حالة للعالم تحتوي على عدد من المتغيرات المجهولة. يبحث برنامج القيود عن قيم لجميع هذه المتغيرات.

البرمجة الزمنية المتزامنة (TCC) والبرمجة الزمنية المتزامنة غير الحتمية (MJV) هما نوعان من البرمجة المقيدة التي يمكنها التعامل مع الوقت.

مشكلة إرضاء القيود

القيد هو علاقة بين متغيرات متعددة تحد من القيم التي يمكن أن تأخذها هذه المتغيرات في وقت واحد.

التعريف — تُعرَّف مسألة إرضاء القيود على المجالات المحدودة (أو CSP) بواسطة ثلاثية(X،د،ج){\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}أين:

  • X={x1،...،xن}{\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}هي مجموعة متغيرات المسألة؛
  • د={د1،...،دن}{\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}هي مجموعة مجالات المتغيرات، أي لجميعك∈[1;ن]{\displaystyle k\in [1;n]}لديناxك∈دك{\displaystyle x_{k}\in {\mathcal {D}}_{k}};
  • ج={ج1،...،جم}{\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}هي مجموعة من القيود. قيدجأنا=(Xأنا،Rأنا){\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}يتم تعريفها بواسطة مجموعةXأنا={xأنا1،...،xأناك}{\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}من المتغيرات وعلاقةRأنا⊆دأنا1×⋯×دأناك{\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}ذلك يحدد مجموعة القيم المسموح بها في آن واحد لمتغيراتXأنا{\displaystyle {\mathcal {X}}_{i}}.

توجد ثلاث فئات من القيود:

  • القيود الامتدادية: يتم تعريف القيود عن طريق تعداد مجموعة القيم التي من شأنها أن تحققها؛
  • القيود الحسابية: تُعرَّف القيود بواسطة تعبير حسابي، أي باستخدام<،>،≤،≥،=،≠،...{\displaystyle <,>,\leq ,\geq ,=,\neq ,...};
  • القيود المنطقية: تُعرَّف القيود بدلالات صريحة، مثل: AllDifferent ، AtMost ، ...

التعريف — مهمة (أو نموذج)أ{\displaystyle {\mathcal {A}}}من مزود خدمة الاتصالاتP=(X،د،ج){\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}يتم تحديده من قبل الزوجينأ=(Xأ،Vأ){\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}أين:

  • Xأ⊆X{\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}هي مجموعة فرعية من المتغير؛
  • Vأ={vأ1،...،vأك}∈{دأ1،...،دأك}{\displaystyle {\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}}هي مجموعة القيم التي تأخذها المتغيرات المُخصصة.

التخصيص هو ربط متغير بقيمة من نطاقه. التخصيص الجزئي هو تخصيص مجموعة فرعية من متغيرات المسألة. أما التخصيص الكلي فهو تخصيص جميع متغيرات المسألة.

الملكية - المعطاةأ=(Xأ،Vأ){\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}تخصيص (جزئي أو كلي) لمزود خدمات الحوسبة السحابيةP=(X،د،ج){\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}، وجأنا=(Xأنا،Rأنا){\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}قيد منP{\displaystyle P}مثلXأنا⊆Xأ{\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}، المهمةأ{\displaystyle {\mathcal {A}}}يفي بالشرطجأنا{\displaystyle C_{i}}إذا وفقط إذا كانت جميع القيمVأأنا={vأنا∈Vأ بحيث xأنا∈Xأنا}{\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ such that }}x_{i}\in {\mathcal {X}}_{i}\}}من متغيرات القيدجأنا{\displaystyle C_{i}}ينتمي إلىRأنا{\displaystyle {\mathcal {R}}_{i}}.

التعريف — حل مسألة إرضاء القيود هو تعيين كامل يفي بجميع قيود المسألة.

أثناء البحث عن حلول لمزود خدمات الحوسبة السحابية، قد يرغب المستخدم في:

  • إيجاد حل (يلبي جميع القيود)؛
  • إيجاد جميع حلول المشكلة؛
  • إثبات عدم إمكانية حل المشكلة.

مشكلة التحسين المقيد

مشكلة تحسين القيود (COP) هي مشكلة إرضاء القيود المرتبطة بدالة الهدف.

الحل الأمثل لمسألة تقليل (زيادة) COP هو الحل الذي يقلل (يزيد) قيمة دالة الهدف .

أثناء البحث عن حلول لمشكلة شائعة، قد يرغب المستخدم في:

  • إيجاد حل (يلبي جميع القيود)؛
  • إيجاد الحل الأمثل فيما يتعلق بالهدف؛
  • إثبات أمثلية الحل الأمثل الذي تم التوصل إليه؛
  • إثبات عدم إمكانية حل المشكلة.

نماذج الاضطراب مقابل نماذج التحسين

تتبع لغات البرمجة القائمة على القيود أحد النهجين التاليين: [ 3 ]

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

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

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

النطاقات

تُستخدم القيود في البرمجة المقيدة عادةً ضمن نطاقات محددة. ومن بين النطاقات الشائعة للبرمجة المقيدة ما يلي:

تُعدّ المجالات المحدودة من أنجح مجالات البرمجة المقيدة. في بعض المجالات (مثل بحوث العمليات )، غالباً ما تُعرّف البرمجة المقيدة بأنها البرمجة المقيدة على المجالات المحدودة.

انتشار القيود

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

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

حل القيود

توجد ثلاث تقنيات خوارزمية رئيسية لحل مشاكل إرضاء القيود: البحث بالتراجع، والبحث المحلي، والبرمجة الديناميكية. [ 1 ]

البحث بالتراجع هو خوارزمية عامة لإيجاد جميع (أو بعض) الحلول لبعض المشكلات الحسابية ، وخاصة مشكلات إرضاء القيود ، والتي تقوم ببناء مرشحين للحلول بشكل تدريجي، وتتخلى عن المرشح ("تتراجع") بمجرد أن تحدد أنه لا يمكن إكمال المرشح إلى حل صالح.

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

البرمجة الديناميكية

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

مثال

تختلف صيغة التعبير عن القيود على نطاقات محدودة باختلاف لغة البرمجة. فيما يلي برنامج مكتوب بلغة برولوج يحل لغز SEND+MORE=MONEY الكلاسيكي في برمجة منطق القيود:

يعمل هذا الكود في كلٍ من YAP وSWI-Prolog باستخدام مكتبة حل القيود CLPFD المُضمّنة في البيئة . قد يتطلب تعديلات طفيفة ليعمل في بيئات Prolog أخرى أو باستخدام حلول قيود أخرى. :- use_module ( library ( clpfd )). sendmore ( Digits ) :- Digits = [ S , E , N , D , M , O , R , Y ], % إنشاء متغيرات Digits ins 0..9 , % ربط المجالات بالمتغيرات S # = 0 , % القيد: يجب أن تكون S مختلفة عن 0 M # = 0 , all_different ( Digits ), % يجب أن تأخذ جميع العناصر قيمًا مختلفة 1000 * S + 100 * E + 10 * N + D % قيود أخرى + 1000 * M + 100 * O + 10 * R + E # = 10000 * M + 1000 * O + 100 * N + 10 * E + Y , label ( Digits ). % بدء البحث

يُنشئ المُفسِّر مُتغيرًا لكل حرف في اللغز. insيُستخدم المُعامل لتحديد نطاقات هذه المُتغيرات، بحيث تتراوح قيمها ضمن المجموعة {0، 1، 2، 3، ...، 9}. تعني القيود S#\=0أن M#\=0هذين المُتغيرين لا يُمكن أن يأخذا القيمة صفر. عند تقييم المُفسِّر لهذه القيود، يُقلِّص نطاقات هذين المُتغيرين بإزالة القيمة صفر منهما. ثم يُؤخذ القيد all_different(Digits)في الاعتبار؛ فهو لا يُقلِّص أي نطاق، لذا يُخزَّن ببساطة. يُحدد القيد الأخير أن الأرقام المُخصصة للأحرف يجب أن تكون بحيث تتحقق العبارة "SEND+MORE=MONEY" عند استبدال كل حرف برقمه المُناسب. من هذا القيد، يستنتج المُحلِّل أن M=1. يتم تنشيط جميع القيود المُخزَّنة التي تتضمن المُتغير M: في هذه الحالة، يُزيل نشر القيد القيمة all_different1 من نطاق جميع المُتغيرات المُتبقية. قد يحل نشر القيود المشكلة بتقليص جميع المجالات إلى قيمة واحدة، وقد يثبت عدم وجود حل للمشكلة بتقليص أحد المجالات إلى المجموعة الفارغة، ولكنه قد ينتهي أيضًا دون إثبات إمكانية الحل أو عدمها. تُستخدم القيم الحرفية للتصنيف لإجراء البحث الفعلي عن الحل.

انظر أيضاً

مراجع

  1. 1 2 روسي، فرانشيسكا ؛ بيك، بيتر فان؛ والش، توبي (2006). دليل البرمجة المقيدة . إلسيفير. ISBN 978-0-08-046380-3.
  2. ↑ جعفر، جوكسان؛ لاسيز، جيه إل. (1987). "برمجة المنطق المقيد" . POPL87: الندوة السنوية الرابعة عشرة لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة . جمعية آلات الحوسبة. ص 111-119 . doi : 10.1145/41625.41635 . ISBN  978-0-89791-215-0.
  3. ↑ بورنينغ، أ.؛ فريمان-بنسون، ب.؛ ويلسون، م. (1993). "تسلسل القيود الهرمي" . في مايوه، ب.؛ تيوغو، إ.؛ بينجام، ج. (محررون). برمجة القيود . ناتو ASI F. المجلد 131. سبرينغر. ص 76. doi : 10.1007/978-3-642-85983-0_4 . ISBN   978-3-642-85983-0.
  4. ↑ لوبيز، ج.؛ فريمان-بينسون، ب.؛ بورنينغ، أ. (1993). "كاليديوسكوب: لغة برمجة إجرائية مقيدة" (ملف PDF) . في: مايوه، ب.؛ تيوغو، إ.؛ بينجام، ج. (محررون). البرمجة المقيدة . ناتو ASI F. المجلد 131. سبرينغر. الصفحات 313-329 . doi : 10.1007/978-3-642-85983-0_12 . ISBN   978-3-642-85983-0.
  5. ↑ باتيست، فيليب ؛ باب، كلود لو؛ نويتن، ويم (2012). الجدولة القائمة على القيود: تطبيق البرمجة المقيدة على مشاكل الجدولة . سبرينغر. ISBN 978-1-4615-1479-4.
  6. ↑ بيسيير، كريستيان (2006). "نشر القيود". دليل برمجة القيود . أسس الذكاء الاصطناعي. المجلد 2. إلسيفير. الصفحات 29-83 . CiteSeerX 10.1.1.398.4070 . doi : 10.1016/s1574-6526(06)80007-6 . ISBN    9780444527264.