AI - خوارزميات البحث الشعبية

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

وكيل واحد مشاكل Pathfinding

الألعاب مثل 3X3 ثمانية البلاط ، 4X4 خمسة عشر قطعة ، و 5X5 24 قطعة من الألغاز هي تحديات للعثور على مسار وكيل واحد. تتكون من مصفوفة من البلاط مع بلاطة فارغة. يُطلب من اللاعب ترتيب البلاط عن طريق تحريك البلاط عموديًا أو أفقيًا في مساحة فارغة بهدف تحقيق بعض الأهداف.

الأمثلة الأخرى لمشكلات اكتشاف مسار الوكيل الفردي هي مشكلة البائع المتجول ومكعب روبيك وإثبات النظرية.

مصطلحات البحث

• مساحة المشكلة - هي البيئة التي يتم فيها البحث. (مجموعة من الحالات ومجموعة من العوامل لتغيير تلك الحالات)

• مثيل المشكلة - إنها الحالة الأولية + حالة الهدف.

• مخطط مساحة المشكلة - يمثل حالة المشكلة. يتم عرض الحالات بواسطة العقد ويتم إظهار المشغلين بواسطة الحواف.

• عمق المشكلة - طول أقصر مسار أو أقصر سلسلة من المشغلين من الحالة الأولية إلى حالة الهدف.

• تعقيد المساحة - الحد الأقصى لعدد العقد المخزنة في الذاكرة.

• تعقيد الوقت - الحد الأقصى لعدد العقد التي تم إنشاؤها.

• القبول - خاصية الخوارزمية لإيجاد الحل الأمثل دائمًا.

• عامل التفرع - متوسط ​​عدد العقد الفرعية في الرسم البياني لمساحة المشكلة.

• العمق - طول أقصر مسار من الحالة الأولية إلى حالة الهدف.

إستراتيجيات بحث القوة الغاشمة

إنها أبسط ، لأنها لا تحتاج إلى أي معرفة خاصة بالمجال. إنها تعمل بشكل جيد مع عدد قليل من الحالات الممكنة.

المتطلبات -

• وصف الحالة
• مجموعة من العوامل الصالحة
• الحالة الأولية
• وصف حالة الهدف

اتساع البحث الأول

يبدأ من عقدة الجذر ، ويستكشف العقد المجاورة أولاً ويتحرك نحو المستوى التالي من الجيران. يولد شجرة واحدة في كل مرة حتى يتم إيجاد الحل. يمكن تنفيذه باستخدام بنية بيانات قائمة انتظار FIFO. توفر هذه الطريقة أقصر طريق للحل.

إذا كان عامل التفرع (متوسط ​​عدد العقد الفرعية لعقدة معينة) = ب والعمق = د ، فإن عدد العقد عند المستوى د = ب د .

إجمالي عدد العقد التي تم إنشاؤها في أسوأ الحالات هو ب + ب 2 + ب 3 + ... + ب د .

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

يعتمد تعقيدها على عدد العقد. يمكنه التحقق من العقد المكررة.

عمق البحث الأول

يتم تنفيذه بالتكرار مع بنية بيانات مكدس LIFO. يقوم بإنشاء نفس مجموعة العقد مثل طريقة Breadth-First ، بترتيب مختلف فقط.

نظرًا لأنه يتم تخزين العقد الموجودة على المسار الفردي في كل تكرار من العقدة الجذرية إلى العقد الطرفية ، فإن متطلبات المساحة لتخزين العقد تكون خطية. مع عامل التفرع ب والعمق م ، تكون مساحة التخزين bm.

العيب - قد لا تنتهي هذه الخوارزمية وتستمر بلا حدود في مسار واحد. الحل لهذه المشكلة هو اختيار عمق القطع. إذا كان الحد المثالي هو d ، وإذا كان القطع المختار أقل من d ، فقد تفشل هذه الخوارزمية. إذا كان التوقف المختار أكثر من d ، يزداد وقت التنفيذ.

يعتمد تعقيدها على عدد المسارات. لا يمكن التحقق من العقد المكررة.

بحث ثنائي الاتجاه

يبحث للأمام من الحالة الأولية والخلف من حالة الهدف حتى يلتقي كلاهما لتحديد حالة مشتركة.

المسار من الحالة الأولية متسلسل مع المسار العكسي من حالة الهدف. يتم إجراء كل بحث حتى نصف إجمالي المسار فقط.

البحث الموحد عن التكلفة

يتم الفرز بزيادة تكلفة المسار إلى العقدة. إنه يوسع دائمًا العقدة الأقل تكلفة. إنه مماثل للبحث في "عرض النطاق الأول" إذا كان لكل عملية انتقال نفس التكلفة.

يستكشف المسارات بالترتيب المتزايد للتكلفة.

عيب - يمكن أن يكون هناك العديد من المسارات الطويلة مع التكلفة ≤ C *. يجب أن يقوم البحث الموحد عن التكلفة باستكشافها جميعًا.

العمق التكراري - البحث الأول

يقوم بإجراء بحث العمق أولاً إلى المستوى 1 ، ويبدأ من جديد ، وينفذ بحثًا كاملًا أولاً بالعمق إلى المستوى 2 ، ويستمر بهذه الطريقة حتى يتم العثور على الحل.

لا يقوم أبدًا بإنشاء عقدة حتى يتم إنشاء جميع العقد السفلية. يقوم فقط بحفظ كومة من العقد. تنتهي الخوارزمية عندما تجد حلاً في العمق د . عدد العقد التي تم إنشاؤها على العمق d هو b d وعند العمق d-1 يكون b d-1.

مقارنة تعقيدات الخوارزميات المختلفة

دعونا نرى أداء الخوارزميات بناءً على معايير مختلفة -

معيار	اتساع أولا	العمق أولا	ثنائي الاتجاه	التكلفة الموحدة	التعميق التفاعلي
زمن	ب د	ب م	ب د / 2	ب د	ب د
الفراغ	ب د	ب م	ب د / 2	ب د	ب د
أمثلية	نعم	لا	نعم	نعم	نعم
الاكتمال	نعم	لا	نعم	نعم	نعم

استراتيجيات البحث المستنيرة (الارشادية)

لحل المشكلات الكبيرة مع عدد كبير من الحالات المحتملة ، يجب إضافة المعرفة الخاصة بالمشكلة لزيادة كفاءة خوارزميات البحث.

وظائف التقييم الارشادي

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

بحث ارشادي محض

يوسع العقد بترتيب قيمها الاستكشافية. يقوم بإنشاء قائمتين ، قائمة مغلقة للعقد الموسعة بالفعل وقائمة مفتوحة للعقد التي تم إنشاؤها ولكن غير الموسعة.

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

بحث

إنه الشكل الأكثر شهرة لأفضل بحث أولاً. إنه يتجنب توسيع المسارات باهظة الثمن بالفعل ، ولكنه يوسع معظم المسارات الواعدة أولاً.

و (ن) = ز (ن) + ح (ن) ، أين

• ز (ن) التكلفة (حتى الآن) للوصول إلى العقدة
• ح (ن) التكلفة المقدرة للانتقال من العقدة إلى الهدف
• f (n) التكلفة الإجمالية المقدرة للمسار عبر n إلى الهدف. يتم تنفيذه باستخدام قائمة انتظار الأولوية عن طريق زيادة f (n).

أفضل بحث أولا طماع

يوسع العقدة التي يُقدر أنها أقرب إلى الهدف. يوسع العقد على أساس f (n) = h (n). يتم تنفيذه باستخدام قائمة انتظار الأولوية.

العيب - يمكن أن تتعثر في الحلقات. إنه ليس الأمثل.

خوارزميات البحث المحلي

يبدأون من حل محتمل ثم ينتقلون إلى حل مجاور. يمكنهم إرجاع حل صالح حتى لو تمت مقاطعته في أي وقت قبل أن ينتهي.

بحث تسلق التلال

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

دالة Hill-Climbing (مشكلة) ، تعيد حالة بحد أقصى محلي.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

العيب - هذه الخوارزمية ليست كاملة وليست مثالية.

البحث عن شعاع محلي

في هذه الخوارزمية ، تحتوي على عدد k من الحالات في أي وقت. في البداية ، يتم إنشاء هذه الحالات بشكل عشوائي. يتم حساب خلفاء هذه الحالات k بمساعدة الوظيفة الموضوعية. إذا كان أي من هؤلاء الخلفاء هو القيمة القصوى لوظيفة الهدف ، عندئذٍ تتوقف الخوارزمية.

وبخلاف ذلك ، يتم وضع (حالات k الأولية وعدد k من خلفاء الحالات = 2k) في مجموعة. ثم يتم فرز التجمع عدديًا. يتم تحديد أعلى حالات k كحالات أولية جديدة. تستمر هذه العملية حتى يتم الوصول إلى الحد الأقصى للقيمة.

دالة BeamSearch ( مشكلة ، k ) ، تعيد حالة الحل.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

محاكاة الصلب

التلدين هو عملية تسخين وتبريد معدن لتغيير هيكله الداخلي لتعديل خصائصه الفيزيائية. عندما يبرد المعدن ، يتم الاستيلاء على هيكله الجديد ، ويحتفظ المعدن بخصائصه التي تم الحصول عليها حديثًا. في عملية التلدين المحاكاة ، يتم الاحتفاظ بدرجة الحرارة متغيرة.

في البداية ، قمنا بتعيين درجة حرارة عالية ثم نسمح لها بـ `` التبريد '' ببطء مع تقدم الخوارزمية. عندما تكون درجة الحرارة عالية ، يُسمح للخوارزمية بقبول حلول أسوأ بتردد عالٍ.

بداية

• تهيئة k = 0 ؛ L = عدد صحيح من المتغيرات ؛
• من i → j ، ابحث عن اختلاف الأداء Δ.
• إذا كانت Δ <= 0 ثم اقبل else if exp (-Δ / T (k))> random (0،1) ثم اقبل ؛
• كرر الخطوتين 1 و 2 للخطوات L (k).
• ك = ك + 1 ؛

كرر الخطوات من 1 إلى 4 حتى يتم استيفاء المعايير.

النهاية

مشكلة بائع متجول

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

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end