ब्रांचिंग फैक्टर: Difference between revisions

From Vigyanwiki
 
No edit summary
Line 1: Line 1:
[[Image:Red-black tree example.svg|thumb|शाखा कारक 2 वाला एक लाल-काला पेड़]][[ कम्प्यूटिंग ]], ट्री डेटा संरचनाओं और [[ खेल सिद्धांत ]] में, ब्रांचिंग कारक प्रत्येक [[नोड (कंप्यूटर विज्ञान)]] पर [[चाइल्ड नोड]] की संख्या है, [[आउटडिग्री]]। यदि यह मान एक समान नहीं है, तो ''औसत शाखाकरण कारक'' की गणना की जा सकती है।
[[Image:Red-black tree example.svg|thumb|शाखा फैक्टर 2 वाला एक लाल-काला ट्री]][[ कम्प्यूटिंग | कम्प्यूटिंग]], ट्री डेटा संरचनाओं और [[ खेल सिद्धांत |खेल सिद्धांत]] में, '''ब्रांचिंग फैक्टर''' प्रत्येक [[नोड (कंप्यूटर विज्ञान)]] पर चाइल्ड नोड की संख्या है, आउटडिग्री है। यदि यह मान एक समान नहीं है, तो ''औसत ब्रांचिंग फैक्टर'' की गणना की जा सकती है।


उदाहरण के लिए, [[शतरंज]] में, यदि एक नोड को कानूनी स्थिति माना जाता है, तो औसत शाखाकरण कारक लगभग 35 बताया गया है,<ref name="wired"/><ref>{{cite web | url=http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 | title=Chess Programming Part IV: Basic Search | date= 6 August 2000 |first=François Dominic |last=Laramée | publisher=GameDev.net | accessdate=2007-05-01}}</ref> और 2.5 मिलियन से अधिक खेलों के सांख्यिकीय विश्लेषण से औसतन 31 का पता चला।<ref>{{cite web |last1=Barnes |first1=David |title=What is the average number of legal moves per turn? |url=https://chess.stackexchange.com/a/24325 |website=Chess Stack Exchange |accessdate=2019-06-01}}</ref> इसका मतलब यह है कि, औसतन, एक खिलाड़ी के पास प्रत्येक मोड़ पर लगभग 31 से 35 कानूनी चालें होती हैं। तुलनात्मक रूप से, गेम [[ जाओ (खेल) ]] के लिए औसत ब्रांचिंग कारक 250 है।<ref name="wired"/>


उच्च शाखाकरण कारक एल्गोरिदम बनाते हैं जो प्रत्येक नोड पर प्रत्येक शाखा का अनुसरण करते हैं, जैसे कि संपूर्ण जानवर-बल खोज, नोड्स की [[घातीय वृद्धि]] संख्या के कारण कम्प्यूटेशनल रूप से अधिक महंगा है, जिससे संयोजन विस्फोट होता है।
उदाहरण के लिए, शतरंज में, यदि एक "नोड" को कानूनी स्थिति माना जाता है, तो औसत शाखा फैक्टर लगभग 35 बताया गया है,<ref name="wired" /><ref>{{cite web | url=http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 | title=Chess Programming Part IV: Basic Search | date= 6 August 2000 |first=François Dominic |last=Laramée | publisher=GameDev.net | accessdate=2007-05-01}}</ref> और 2.5 मिलियन से अधिक खेलों के सांख्यिकीय विश्लेषण से पता चला है कि औसतन 31<ref>{{cite web |last1=Barnes |first1=David |title=What is the average number of legal moves per turn? |url=https://chess.stackexchange.com/a/24325 |website=Chess Stack Exchange |accessdate=2019-06-01}}</ref> इसका मतलब यह है कि, औसतन, एक खिलाड़ी के पास प्रत्येक मोड़ पर लगभग 31 से 35 कानूनी चालें होती हैं। तुलनात्मक रूप से, गेम गो के लिए औसत ब्रांचिंग फैक्टर 250 है।<ref name="wired" />


उदाहरण के लिए, यदि शाखाकरण कारक 10 है, तो वर्तमान स्थिति से एक स्तर नीचे 10 नोड्स होंगे, 10<sup>2</sup>(या 100) नोड्स दो स्तर नीचे, 10<sup>3</sup>(या 1,000) नोड तीन स्तर नीचे, इत्यादि। शाखाकरण कारक जितना अधिक होगा, यह विस्फोट उतनी ही तेजी से होता है। शाखाकरण कारक को प्रूनिंग (एल्गोरिदम) द्वारा कम किया जा सकता है।


औसत शाखाकरण कारक की गणना गैर-रूट नोड्स (पेड़ का आकार, शून्य से एक; या किनारों की संख्या) की संख्या को गैर-पत्ती नोड्स (बच्चों के साथ नोड्स की संख्या) की संख्या से विभाजित करके की जा सकती है।
उच्च ब्रांचिंग फैक्टर एल्गोरिदम बनाते हैं जो प्रत्येक नोड पर प्रत्येक शाखा का अनुसरण करते हैं, जैसे कि संपूर्ण जानवर-बल खोज, नोड्स की [[घातीय वृद्धि]] संख्या के कारण कम्प्यूटेशनल रूप से अधिक महंगा है, जिससे संयोजन विस्फोट होता है।
 
उदाहरण के लिए, यदि ब्रांचिंग फैक्टर 10 है, तो वर्तमान स्थिति से एक स्तर नीचे 10 नोड्स होंगे, 10<sup>2</sup>(या 100) नोड्स दो स्तर नीचे, 10<sup>3</sup>(या 1,000) नोड तीन स्तर नीचे, इत्यादि। ब्रांचिंग फैक्टर जितना अधिक होगा, यह विस्फोट उतनी ही तेजी से होता है। ब्रांचिंग फैक्टर को प्रूनिंग (एल्गोरिदम) द्वारा कम किया जा सकता है।
 
औसत ब्रांचिंग फैक्टर की गणना गैर-रूट नोड्स (ट्री का आकार, शून्य से एक; या किनारों की संख्या) की संख्या को गैर-लीफ नोड्स (चिल्ड्रन के साथ नोड्स की संख्या) की संख्या से विभाजित करके की जा सकती है।


== यह भी देखें ==
== यह भी देखें ==
* के-एरी वृक्ष
* के-एरी ट्री
* आउटडिग्री
* आउटडिग्री
* [[पदानुक्रम]]
* [[पदानुक्रम]]

Revision as of 18:16, 10 August 2023

शाखा फैक्टर 2 वाला एक लाल-काला ट्री

कम्प्यूटिंग, ट्री डेटा संरचनाओं और खेल सिद्धांत में, ब्रांचिंग फैक्टर प्रत्येक नोड (कंप्यूटर विज्ञान) पर चाइल्ड नोड की संख्या है, आउटडिग्री है। यदि यह मान एक समान नहीं है, तो औसत ब्रांचिंग फैक्टर की गणना की जा सकती है।


उदाहरण के लिए, शतरंज में, यदि एक "नोड" को कानूनी स्थिति माना जाता है, तो औसत शाखा फैक्टर लगभग 35 बताया गया है,[1][2] और 2.5 मिलियन से अधिक खेलों के सांख्यिकीय विश्लेषण से पता चला है कि औसतन 31[3] इसका मतलब यह है कि, औसतन, एक खिलाड़ी के पास प्रत्येक मोड़ पर लगभग 31 से 35 कानूनी चालें होती हैं। तुलनात्मक रूप से, गेम गो के लिए औसत ब्रांचिंग फैक्टर 250 है।[1]


उच्च ब्रांचिंग फैक्टर एल्गोरिदम बनाते हैं जो प्रत्येक नोड पर प्रत्येक शाखा का अनुसरण करते हैं, जैसे कि संपूर्ण जानवर-बल खोज, नोड्स की घातीय वृद्धि संख्या के कारण कम्प्यूटेशनल रूप से अधिक महंगा है, जिससे संयोजन विस्फोट होता है।

उदाहरण के लिए, यदि ब्रांचिंग फैक्टर 10 है, तो वर्तमान स्थिति से एक स्तर नीचे 10 नोड्स होंगे, 102(या 100) नोड्स दो स्तर नीचे, 103(या 1,000) नोड तीन स्तर नीचे, इत्यादि। ब्रांचिंग फैक्टर जितना अधिक होगा, यह विस्फोट उतनी ही तेजी से होता है। ब्रांचिंग फैक्टर को प्रूनिंग (एल्गोरिदम) द्वारा कम किया जा सकता है।

औसत ब्रांचिंग फैक्टर की गणना गैर-रूट नोड्स (ट्री का आकार, शून्य से एक; या किनारों की संख्या) की संख्या को गैर-लीफ नोड्स (चिल्ड्रन के साथ नोड्स की संख्या) की संख्या से विभाजित करके की जा सकती है।

यह भी देखें

  • के-एरी ट्री
  • आउटडिग्री
  • पदानुक्रम
  • पदानुक्रमित संगठन

संदर्भ

  1. 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.
  2. Laramée, François Dominic (6 August 2000). "Chess Programming Part IV: Basic Search". GameDev.net. Retrieved 2007-05-01.
  3. Barnes, David. "What is the average number of legal moves per turn?". Chess Stack Exchange. Retrieved 2019-06-01.