عامل التفرع

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

على سبيل المثال، في الشطرنج ، إذا اعتُبرت "العقدة" وضعًا قانونيًا، يُقال إن متوسط ​​عامل التفرع يبلغ حوالي 35، ^{[ 1 ] [ 2 ]} وقد كشف تحليل إحصائي لأكثر من 2.5 مليون مباراة عن متوسط ​​قدره 31. ^{[ 3 ]} هذا يعني أن اللاعب، في المتوسط، لديه ما بين 31 و35 نقلة قانونية متاحة له في كل دور. للمقارنة، يبلغ متوسط ​​عامل التفرع في لعبة غو 250. ^{[ 1 ]}

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

على سبيل المثال، إذا كان عامل التفرع 10، فسيكون هناك 10 عقد على مستوى واحد أسفل الموقع الحالي، و10 عقد على ^{مستويين} (أو 100 عقدة)، و10 ^عقد على ثلاثة مستويات (أو 1000 عقدة)، وهكذا. كلما زاد عامل التفرع، زادت سرعة هذا "التوسع". ويمكن تقليل عامل التفرع باستخدام خوارزمية تقليم .

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

• شجرة k-ary
• درجة خارجية
• تَسَلسُل
• التنظيم الهرمي