عامل التفرع

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

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

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

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

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

المصادر 

أشجار (بنى معطيات)
تحليل الخوارزميات
شطرنج الحاسوب