عامل التفرع
 | هذه مقالة غير مراجعة. (أكتوبر 2021) |
عامل التفرع[1] في الحوسبة وهياكل بيانات الشجرة ونظرية الألعاب هو عدد الأبناء في كل عقدة، الدرجة الخارجية. إذا لم تكن هذه القيمة موحدة، يمكن حساب متوسط عامل التفرع.
على سبيل المثال، في لعبة الشطرنج، إذا اعتُبرت «العقدة» وضعا قانونيا، يُقال ان متوسط عامل التفرع يبلغ ٣٥ تقريبا، [2][3] كشف تحليل احصائي لما يزيد عن ٥، ٢ مليون مباراة ان المتوسط يبلغ ٣١ مباراة.[4] وهذا يعني، في المتوسط، أن اللاعب لديه حوالي 31 إلى 35 حركة قانونية تحت تصرفه في كل منعطف. وبالمقارنة، فإن متوسط عامل التفرع للعبة غو هو 250.[2]
العوامل المتفرعة الأعلى تجعل الخوارزميات التي تتبع كل فرع في كل عقدة، مثل عمليات بحث القوة الغاشمة الشاملة، أكثر تكلفة حسابيا بسبب الزيادة الأسية في عدد العقد، مما يؤدي إلى انفجار توافقي.
على سبيل المثال، إذا كان عامل التفرع هو 10، سيكون هناك 10 عقد بمستوى واحد أسفل من الموقع الحالي، 102 (أو 100) عقد مستويين أسفل،103 (أو 1,000) عقد ثلاثة مستويات لأسفل وهكذا. وكلما كان عامل التفرع أعلى، كان حدوث هذا «الانفجار» أسرع. يمكن خفض عامل التفرع عن طريق تشذيب الخوارزمية.
ويمكن حساب متوسط عامل التفرع بسرعة على أنه عدد العقد غير الجذرية (حجم الشجرة ناقص واحد؛ أو عدد الحواف) مقسومًا على عدد العقد غير الورقية (عدد العقد ذات ال أبناء).
المصادر
- ^ Q111421033، ص. 48، QID:Q111421033
- ^ أ ب ليفينوفيتز ، آلان (12 مايو 2014). "The Mystery of Go ، اللعبة القديمة التي لا تزال أجهزة الكمبيوتر غير قادرة على الفوز بها" . سلكي . تم الاسترجاع 2014/06/02 . معدل زيادة المراكز المحتملة يرتبط ارتباطًا مباشرًا "بعامل التفريع" للعبة ، أو متوسط عدد الحركات المتاحة في أي منعطف معين. عامل تفرع الشطرنج هو 35. Go's 250. الألعاب ذات العوامل المتفرعة العالية تجعل خوارزميات البحث الكلاسيكية مثل minimax مكلفة للغاية. نسخة محفوظة 2021-10-02 على موقع واي باك مشين.
- ^ لارامي ، فرانسوا دومينيك (6 أغسطس 2000). "برمجة الشطرنج الجزء الرابع: البحث الأساسي" . GameDev.net . تم الاسترجاع 2007-05-01 . نسخة محفوظة 2020-11-06 على موقع واي باك مشين.
- ^ بارنز ، ديفيد. "ما هو متوسط عدد الحركات القانونية لكل دور؟" . تبادل مكدس الشطرنج . تم الاسترجاع 2019/06/01 . نسخة محفوظة 2020-11-27 على موقع واي باك مشين.
