ब्रांचिंग फैक्टर
कम्प्यूटिंग, ट्री डेटा संरचनाओं और खेल सिद्धांत में, ब्रांचिंग फैक्टर प्रत्येक नोड (कंप्यूटर विज्ञान) पर चाइल्ड नोड की संख्या है, आउटडिग्री है। यदि यह मान एक समान नहीं है, तो औसत ब्रांचिंग फैक्टर की गणना की जा सकती है।
उदाहरण के लिए, शतरंज में, यदि एक "नोड" को कानूनी स्थिति माना जाता है, तो औसत शाखा फैक्टर लगभग 35 बताया गया है,[1][2] और 2.5 मिलियन से अधिक खेलों के सांख्यिकीय विश्लेषण से पता चला है कि औसतन 31[3] इसका मतलब यह है कि, औसतन, एक खिलाड़ी के पास प्रत्येक मोड़ पर लगभग 31 से 35 कानूनी चालें होती हैं। तुलनात्मक रूप से, गेम गो के लिए औसत ब्रांचिंग फैक्टर 250 है।[1]
उच्च ब्रांचिंग फैक्टर एल्गोरिदम बनाते हैं जो प्रत्येक नोड पर प्रत्येक शाखा का अनुसरण करते हैं, जैसे कि संपूर्ण जानवर-बल खोज, नोड्स की घातीय वृद्धि संख्या के कारण कम्प्यूटेशनल रूप से अधिक महंगा है, जिससे संयोजन विस्फोट होता है।
उदाहरण के लिए, यदि ब्रांचिंग फैक्टर 10 है, तो वर्तमान स्थिति से एक स्तर नीचे 10 नोड्स होंगे, 102(या 100) नोड्स दो स्तर नीचे, 103(या 1,000) नोड तीन स्तर नीचे, इत्यादि। ब्रांचिंग फैक्टर जितना अधिक होगा, यह विस्फोट उतनी ही तेजी से होता है। ब्रांचिंग फैक्टर को प्रूनिंग (एल्गोरिदम) द्वारा कम किया जा सकता है।
औसत ब्रांचिंग फैक्टर की गणना गैर-रूट नोड्स (ट्री का आकार, शून्य से एक; या किनारों की संख्या) की संख्या को गैर-लीफ नोड्स (चिल्ड्रन के साथ नोड्स की संख्या) की संख्या से विभाजित करके की जा सकती है।
यह भी देखें
- के-एरी ट्री
- आउटडिग्री
- पदानुक्रम
- पदानुक्रमित संगठन
संदर्भ
- ↑ 1.0 1.1 Levinovitz, Alan (12 May 2014). "The Mystery of Go, the Ancient Game That Computers Still Can't Win". Wired. Retrieved 2014-06-02.
The rate at which possible positions increase is directly related to a game's "branching factor," or the average number of moves available on any given turn. Chess's branching factor is 35. Go's is 250. Games with high branching factors make classic search algorithms like minimax extremely costly.
- ↑ Laramée, François Dominic (6 August 2000). "Chess Programming Part IV: Basic Search". GameDev.net. Retrieved 2007-05-01.
- ↑ Barnes, David. "What is the average number of legal moves per turn?". Chess Stack Exchange. Retrieved 2019-06-01.
