عامل التفرع

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

وعلى صعيد آخر، مثلًا، إذا كان عامل التفرع هو 10، سيكون هناك 10 عقد بمستوى واحد أسفل من الموقع الحالي، 102 (أو 100) عقد مستويين أسفل،103 (أو 1,000) عقد ثلاثة مستويات لأسفل وهكذا. وكلما كان عامل التفرع أعلى، كان حدوث هذا «الانفجار» أسرع. يمكن خفض عامل التفرع عن طريق تشذيب الخوارزمية.

من جهة ثانية، ويمكن حساب متوسط عامل التفرع بسرعة على أنه عدد العقد غير الجذرية (حجم الشجرة ناقص واحد؛ أو عدد الحواف) مقسومًا على عدد العقد غير الورقية (عدد العقد ذات ال أبناء).

وعلى صعيد آخر، العوامل المتفرعة الأعلى تجعل الخوارزميات التي تتبع كل فرع في كل عقدة، مثل عمليات بحث القوة الغاشمة الشاملة، أكثر تكلفة حسابيا بسبب الزيادة الأسية في عدد العقد، مما يؤدي إلى انفجار توافقي.

في هذا الإطار، مثلًا، في لعبة الشطرنج، إذا اعتُبرت «العقدة» وضعا قانونيا، يُقال ان متوسط عامل التفرع يبلغ ٣٥ على وجه التقريب، كشف تحليل احصائي لما يزيد عن ٥، ٢ مليون مباراة ان المتوسط يبلغ ٣١ مباراة. وهذا يعني، في المتوسط، أن اللاعب لديه قرابة 31 إلى 35 حركة قانونية تحت تصرفه في كل منعطف. وبالمقارنة، فإن متوسط عامل التفرع للعبة غو هو 250.