و/أو شجرة

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

شجرة الـ "و-أو":

يمثل هذا فضاء البحث لحل المشكلة P، باستخدام أساليب تقليل الهدف:

P إذا كان Q و R

P إذا S

س إذا كان ت

سؤال إذا كنت

بافتراض وجود مشكلة أولية P ₀ ومجموعة من طرق حل المشكلات على النحو التالي:

P إذا كان P ₁ و … و P _n

الشجرة المرتبطة بـ "و" أو "أو" هي مجموعة من العقد المصنفة بحيث:

1. جذر الشجرة هو عقدة تحمل العلامة P ₀ .
2. لكل عقدة N تحمل علامة مشكلة أو مشكلة فرعية P، ولكل طريقة من الشكل P إذا كانت P1 _و ... وPn _، توجد مجموعة من العقد الفرعية N1 _، ...، Nn _للعقدة N، بحيث تحمل كل عقدة Ni علامة Pi _{. وترتبط} هذه العقد بقوس لتمييزها عن العقد الفرعية لـ N التي قد تكون مرتبطة بطرق أخرى.

تُعتبر العقدة N، التي تحمل اسم المشكلة P، عقدة نجاح إذا وُجدت طريقة لحل المشكلة P إذا لم يكن هناك حل (أي أن P حقيقة). وتُعتبر عقدة فشل إذا لم توجد طريقة لحل المشكلة P.

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

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

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

يمكن استخدام أشجار "و-أو" لتمثيل فضاءات البحث في الألعاب الثنائية. تمثل العقدة الجذرية في هذه الشجرة مسألة فوز أحد اللاعبين، بدءًا من الحالة الابتدائية للعبة. بفرض وجود عقدة N، تحمل علامة المسألة P (فوز اللاعب من حالة لعب معينة)، توجد مجموعة واحدة من العقد الفرعية المتصلة، تُقابل جميع تحركات الخصم. لكل عقدة فرعية من هذه العقد، توجد مجموعة من العقد الفرعية غير المتصلة، تُقابل جميع تحركات اللاعب الدفاعية.

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

• لوغر، جورج ف.؛ ستابلفيلد، ويليام أ. (1993). الذكاء الاصطناعي: هياكل واستراتيجيات لحل المشكلات المعقدة (  الطبعة الثانية). بنجامين/كومينغز. ISBN 978-0-8053-4785-2تم الاطلاع عليه بتاريخ 28 فبراير 2013 .
• نيلسون، نيلز ج. (1998). الذكاء الاصطناعي: توليفة جديدة . مورغان كوفمان. ISBN 978-1-55860-467-4تم الاطلاع عليه بتاريخ 28 فبراير 2013 .
• راسل، إس. ونورفيج، ب.، 2021. الذكاء الاصطناعي: منهج حديث، الطبعة الأمريكية الرابعة. جامعة كاليفورنيا، بيركلي، ص 141.