خوارزمية الحد الأدنى من التعارضات

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

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

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

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

الخوارزمية

خوارزمية MIN-CONFLICTS هي المدخلات التالية: console.csp ، وهي مسألة إرضاء قيود. max_steps ، وهو عدد الخطوات المسموح بها قبل الاستسلام. current_state ، وهي تعيين أولي لقيم المتغيرات في مسألة إرضاء القيود. المخرجات: مجموعة حلول من القيم للمتغير أو الفشل . لـ i ← 1 إلى max_steps ، إذا كانت الحالة الحالية حلاً لمسألة إرضاء القيود (CSP) ، فأرجع الحالة الحالية . عيّن المتغير var ← متغيرًا مختارًا عشوائيًا من مجموعة المتغيرات المتضاربة CONFLICTED[ csp ]. عيّن القيمة value ← القيمة v للمتغير var التي تُقلل من CONFLICTS( var , v , current_state , csp ). عيّن المتغير var ← القيمة في الحالة الحالية.فشل الإرجاع

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

تاريخ

على الرغم من أن الذكاء الاصطناعي والتحسين المتقطع كانا على دراية بمسائل إرضاء القيود وفهمها لسنوات عديدة، إلا أنه لم يتم تقنين هذه العملية لحل مسائل إرضاء القيود الكبيرة في شكل خوارزمي إلا في أوائل التسعينيات. في وقت مبكر، بحث مارك جونستون من معهد علوم تلسكوب الفضاء عن طريقة لجدولة عمليات الرصد الفلكي على تلسكوب هابل الفضائي . وبالتعاون مع هانز مارتن أدورف من مرفق التنسيق الأوروبي لتلسكوب الفضاء ، أنشأ شبكة عصبية قادرة على حل مسألة الملكات n البسيطة (لـ 1024 ملكة). [ 3 ] [ 4 ] قام ستيفن مينتون وآندي فيليبس بتحليل خوارزمية الشبكة العصبية وفصلاها إلى مرحلتين: (1) التخصيص الأولي باستخدام خوارزمية جشعة، و(2) مرحلة تقليل التعارضات (والتي سُميت لاحقًا "تقليل التعارضات"). كُتبت ورقة بحثية وعُرضت في مؤتمر AAAI-90؛ وقدم فيليب ليرد التحليل الرياضي للخوارزمية.

وفي وقت لاحق، استخدم مارك جونستون وفريق عمل معهد علوم تلسكوب الفضاء (STScI) نظام الحد الأدنى من التعارضات لجدولة وقت مراقبة علماء الفلك على تلسكوب هابل الفضائي.

مثال

عرض متحرك لحل التعارضات الدنيا في لعبة الملكات الثمانية. المرحلة الأولى تُخصص الأعمدة بطريقة جشعة لتقليل التعارضات، ثم يتم الحل.

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

يعتمد أداء هذه الخوارزمية بشكل كبير على اختيار موضع البداية. يمكن توليد موضع بداية جيد عن طريق تعيين الملكات عمودًا تلو الآخر، بحيث يكون كل تعيين لصف يقلل من عدد انتهاكات القيود. ينتج عن ذلك موضع بداية بمتوسط ​​عدد انتهاكات قيود صغير بشكل ملحوظ، ويزداد ببطء شديد مع ازدياد قيمة n (على سبيل المثال، 12.8 عندما n = 10⁶ ) .

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

أدى هذا الاكتشاف والملاحظات إلى إجراء كمٍّ هائل من الأبحاث في عام 1990، وبدأ البحث في مسائل البحث المحلي والتمييز بين المسائل السهلة والصعبة. تُعدّ مسألة الملكات N سهلةً في البحث المحلي لأن الحلول موزعة بكثافة في جميع أنحاء فضاء الحالة. كما أنها فعّالة في المسائل الصعبة. على سبيل المثال، استُخدمت لجدولة عمليات الرصد لتلسكوب هابل الفضائي ، مما قلّل الوقت اللازم لجدولة أسبوع من عمليات الرصد من ثلاثة أسابيع إلى حوالي 10 دقائق. [ 5 ]

انظر أيضاً

مراجع

  1. ↑ مينتون، ستيفن؛ مارك د. جونستون؛ أندرو ب. فيليبس؛ فيليب ليرد (1990). "حل مشكلات إرضاء القيود وجدولة المهام واسعة النطاق باستخدام طريقة إصلاح استدلالية" (ملف PDF) . المؤتمر الوطني الثامن للذكاء الاصطناعي (AAAI-90)، بوسطن، ماساتشوستس : 17-24 . تاريخ الاسترجاع: 27 مارس 2013 .
  2. ↑ مينتون، ستيفن؛ مارك د. جونستون؛ أندرو ب. فيليبس؛ فيليب ليرد (1992). "تقليل التعارضات: طريقة إصلاح استدلالية لمشاكل إرضاء القيود وجدولة المهام" (ملف PDF) . الذكاء الاصطناعي . 58 (1): 161-205 . CiteSeerX 10.1.1.308.6637 . doi : 10.1016/0004-3702(92)90007-k . S2CID 14830518. تاريخ الاسترجاع: 27 مارس 2013 .  
  3. ↑ جونستون، دكتور في الطب؛ أدورف، هـ.-م. (1989). "التعلم في الشبكات العصبية العشوائية لمشاكل إرضاء القيود". مؤتمر ناسا حول الروبوتات الفضائية عن بعد 1989، باسادينا، كاليفورنيا؛ جي. رودريغيز، هـ. سراجي (محرران) : 367-376 المجلد الثاني.
  4. ↑ أدورف، هـ. م.؛ جونستون، م. د. (1990). "خوارزمية شبكة عصبية عشوائية منفصلة لحل مسائل إرضاء القيود". المؤتمر الدولي المشترك للشبكات العصبية 1990. الصفحات 917-924، المجلد 3. doi : 10.1109/IJCNN.1990.137951 . S2CID 26917432 .  
  5. ↑ ستيوارت راسل، بيتر نورفيج، "الذكاء الاصطناعي: نهج حديث (الطبعة الثالثة)"، الصفحات 220-222، 11 ديسمبر 2009.
  • الميكروفيلم الاستدلالي للحد الأدنى من التضاربات  : نتائج تجريبية ونظرية / ستيفن مينتون ... [وآخرون]. وكالة ناسا، مركز أبحاث أميس، فرع أبحاث الذكاء الاصطناعي. تم توزيعه على المكتبات الإيداعية على شكل ميكروفيلم.