B*
கணினி அறிவியலில், பி * ("பி ஸ்டார்" என்று உச்சரிக்கப்படுகிறது) என்பது ஒரு சிறந்த-முதல் வரைபடத் தேடல் வழிமுறையாகும், இது கொடுக்கப்பட்ட ஆரம்ப முனையிலிருந்து எந்தவொரு இலக்கு முனையிலும் (ஒன்று அல்லது அதற்கு மேற்பட்ட சாத்தியமான இலக்குகளில்) குறைந்த விலை பாதையைக் கண்டறிகிறது. 1979 ஆம் ஆண்டில் ஹான்ஸ் பெர்லினரால் முதன்முதலில் வெளியிடப்பட்டது, இது ஏ * தேடல் வழிமுறையுடன் தொடர்புடையது. சுருக்கம் அல்காரிதம் ஒற்றை புள்ளி மதிப்புள்ள மதிப்பீடுகளுக்கு மாறாக மரத்தின் முனைகளுக்கான இடைவெளிகளை சேமிக்கிறது. பின்னர், மரத்தின் இலை முனைகளை மேல் நிலை முனைகளில் ஒன்று தெளிவாக "சிறந்த" இடைவெளியைக் கொண்டிருக்கும் வரை தேடலாம். விவரங்கள் மதிப்பீடுகளை விட இடைவெளி மதிப்பீடுகள் ஒரு பி * மரத்தின் இலை முனைகள் ஒற்றை எண்களை விட இடைவெளிகளாக இருக்கும் மதிப்பீடுகள் வழங்கப்படுகின்றன. இடைவெளி அந்த முனையின் உண்மையான மதிப்பைக் கொண்டிருக்க வேண்டும். இலை முனைகளுடன் இணைக்கப்பட்டுள்ள அனைத்து இடைவெளிகளும் இந்த பண்பை திருப்திப்படுத்தினால், B * இலக்கு நிலைக்கு உகந்த பாதையை அடையாளம் காணும். காப்புப்பிரதி செயல்முறை மரத்திற்குள் உள்ள இடைவெளிகளை காப்புப் பிரதி எடுக்க, பெற்றோரின் மேல் வரம்பு குழந்தைகளின் மேல் வரம்புகளின் அதிகபட்சமாக அமைக்கப்பட்டுள்ளது. ஒரு பெற்றோரின் கீழ் வரம்பு குழந்தைகளின் கீழ் வரம்பின் அதிகபட்சமாக அமைக்கப்பட்டுள்ளது. வெவ்வேறு குழந்தைகள் இந்த வரம்புகளை வழங்கலாம் என்பதை நினைவில் கொள்க. தேடல் B * ஐ நிறுத்துவது "பிரிப்பை" உருவாக்குவதற்காக முனைகளை முறையாக விரிவுபடுத்துகிறது, இது வேரின் நேரடி சைல்டின் கீழ் வரம்பு குறைந்தபட்சம் வேரின் வேறு எந்த நேரடி சைல்டின் மேல் வரம்பைப் போல பெரியதாக இருக்கும்போது நிகழ்கிறது. வேரில் பிரிப்பை உருவாக்கும் ஒரு மரம், சிறந்த குழந்தை குறைந்தபட்சம் மற்ற குழந்தைகளைப் போலவே சிறந்தது என்பதற்கான ஆதாரத்தைக் கொண்டுள்ளது. நடைமுறையில், சிக்கலான தேடல்கள் நடைமுறை வள வரம்புகளுக்குள் முடிவடையாமல் போகலாம். எனவே வழிமுறை பொதுவாக நேரம் அல்லது நினைவக வரம்புகள் போன்ற செயற்கை முடித்தல் அளவுகோல்களுடன் அதிகரிக்கப்படுகிறது. ஒரு செயற்கை வரம்பு தாக்கப்படும்போது, எந்த நகர்வைத் தேர்ந்தெடுக்க வேண்டும் என்பது குறித்து நீங்கள் ஒரு ஹூரிஸ்டிக் தீர்ப்பை வழங்க வேண்டும். பொதுவாக, வேர் முனைகளின் இடைவெளிகள் போன்ற விரிவான ஆதாரங்களை மரம் உங்களுக்கு வழங்கும். விரிவாக்கம் பி * ஒரு சிறந்த-முதல் செயல்முறையாகும், அதாவது மரத்தை கடந்து செல்வது மிகவும் திறமையானது, விரிவுபடுத்த ஒரு இலையைக் கண்டுபிடிக்க மீண்டும் மீண்டும் இறங்குகிறது. இந்த பகுதி விரிவுபடுத்த முனையை எவ்வாறு தேர்வு செய்வது என்பதை விவரிக்கிறது. (குறிப்புஃ மரம் நினைவக-குடியிருப்பாளராக இருந்தாலும் இல்லாவிட்டாலும், அது உண்மையான அல்லது மெய்நிகர் நினைவகம் வழியாக எவ்வாறு வரைபடமாக்கப்படலாம் மற்றும்/அல்லது நிர்வகிக்கப்படலாம் என்பது உட்பட ஒட்டுமொத்த செயல்படுத்தல் செயல்திறனின் செயல்பாடாகும். மரத்தின் வேரில், வழிமுறை இரண்டு உத்திகளில் ஒன்றைப் பயன்படுத்துகிறது, இது நிரூபித்தல்-சிறந்தது மற்றும் நிரூபித்தல்-ஓய்வு என்று அழைக்கப்படுகிறது. நிரூபிக்கப்பட்ட சிறந்த மூலோபாயத்தில், வழிமுறை மிக உயர்ந்த மேல் வரம்புடன் தொடர்புடைய முனையைத் தேர்ந்தெடுக்கிறது. அந்த முனையை விரிவுபடுத்துவது அதன் கீழ் வரம்பை வேறு எந்த முனையின் மேல் வரம்பையும் விட அதிகமாக உயர்த்தும் என்பது நம்பிக்கை. மறுப்பு-ஓய்வு மூலோபாயம் இரண்டாவது மிக உயர்ந்த மேல் வரம்பைக் கொண்ட வேரின் குழந்தையைத் தேர்ந்தெடுக்கிறது. அந்த முனையை விரிவுபடுத்துவதன் மூலம் நீங்கள் மேல் வரம்பை சிறந்த குழந்தையின் கீழ் வரம்பை விட குறைவாக குறைக்க முடியும் என்ற நம்பிக்கை உள்ளது. அனைத்து கீழ் வரம்புகளிலும் மிக உயர்ந்த மேல் வரம்பைக் கொண்ட குழந்தை முனையின் கீழ் வரம்பு மிக உயர்ந்ததாக இருக்கும் வரை தவறான-ஓய்வு மூலோபாயத்தைப் பயன்படுத்துவது அர்த்தமற்றது என்பதைக் கவனியுங்கள். அசல் அல்காரிதம் விளக்கம் எந்த மூலோபாயத்தைத் தேர்ந்தெடுப்பது என்பது குறித்த கூடுதல் வழிகாட்டுதல்களை வழங்கவில்லை. சிறிய மரத்தைக் கொண்ட விருப்பத்தை விரிவுபடுத்துவது போன்ற பல நியாயமான மாற்று வழிகள் உள்ளன. வேர் அல்லாத முனைகளில் மூலோபாயம் தேர்வு ரூட்டின் ஒரு குழந்தை தேர்ந்தெடுக்கப்பட்டவுடன் (நிரூபணம்-சிறந்த அல்லது நிரூபிக்காத-ஓய்வைப் பயன்படுத்தி) பின்னர் வழிமுறை மிக உயர்ந்த மேல் வரம்பைக் கொண்ட குழந்தையை மீண்டும் மீண்டும் தேர்ந்தெடுப்பதன் மூலம் ஒரு இலை முனைக்கு இறங்குகிறது. ஒரு இலை முனையை அடையும் போது, வழிமுறை அனைத்து வாரிசு முனைகளையும் உருவாக்குகிறது மற்றும் மதிப்பீட்டு செயல்பாட்டைப் பயன்படுத்தி அவற்றுக்கு இடைவெளிகளை ஒதுக்குகிறது. பின்னர் அனைத்து முனைகளின் இடைவெளிகள் காப்புப்பிரதி செயல்பாட்டைப் பயன்படுத்தி காப்புப்பிரதி எடுக்கப்பட வேண்டும். இடமாற்றங்கள் சாத்தியமாகும்போது, காப்புப்பிரதி செயல்பாடு தேர்வு பாதையில் இல்லாத முனைகளின் மதிப்புகளை மாற்ற வேண்டியிருக்கலாம். இந்த வழக்கில், வழிமுறைகளுக்கு குழந்தைகளிடமிருந்து அனைத்து பெற்றோர்களுக்கும் சுட்டிகள் தேவை, இதனால் மாற்றங்களைப் பரப்ப முடியும். ஒரு காப்புப்பிரதி செயல்பாடு ஒரு முனையுடன் தொடர்புடைய இடைவெளியை மாற்றாதபோது பரப்புதல் நிறுத்தப்படலாம் என்பதை நினைவில் கொள்க. இடைவெளிகள் தவறாக இருந்தால் (முனையின் விளையாட்டு-கோட்பாட்டு மதிப்பு இடைவெளிக்குள் இல்லை என்ற பொருளில்), பின்னர் B * சரியான பாதையை அடையாளம் காண முடியாமல் போகலாம். இருப்பினும், நடைமுறையில் உள்ள பிழைகளுக்கு வழிமுறை மிகவும் வலுவானது. மாவென் (ஸ்கிராப்பிள்) திட்டம் ஒரு புதுமையைக் கொண்டுள்ளது, இது மதிப்பீட்டு பிழைகள் சாத்தியமாகும்போது பி * இன் வலுவான தன்மையை மேம்படுத்துகிறது. பிரித்தல் காரணமாக ஒரு தேடல் நிறுத்தப்பட்டால், அனைத்து மதிப்பீட்டு இடைவெளிகளையும் ஒரு சிறிய அளவு விரிவுபடுத்திய பிறகு மாவென் தேடலை மீண்டும் தொடங்குகிறது. இந்தக் கொள்கை படிப்படியாக மரத்தை விரிவுபடுத்துகிறது, இறுதியில் அனைத்து பிழைகளையும் அழிக்கிறது. இரண்டு வீரர்கள் விளையாட்டுகளுக்கான நீட்டிப்பு பி * வழிமுறை இரண்டு வீரர்கள் தீர்மானிக்கும் பூஜ்ஜிய-தொகை விளையாட்டுகளுக்கு பொருந்தும். உண்மையில், அந்த முனையில் நகரும் பக்கத்தைப் பொறுத்தவரை "சிறந்தது" என்று விளக்குவதே ஒரே மாற்றமாகும். எனவே உங்கள் பக்கம் நகர்ந்தால் அதிகபட்சத்தையும், எதிரணி நகர்ந்தால் குறைந்தபட்சத்தையும் நீங்கள் எடுப்பீர்கள். சமமாக, நீங்கள் நகர்த்த வேண்டிய பக்கத்தின் கண்ணோட்டத்தில் அனைத்து இடைவெளிகளையும் பிரதிநிதித்துவப்படுத்தலாம், பின்னர் காப்புப்பிரதி செயல்பாட்டின் போது மதிப்புகளை நிராகரிக்கலாம். பயன்பாடுகள் ஆண்ட்ரூ பாலே சதுரங்கத்திற்கு பி * ஐப் பயன்படுத்தினார். பூஜ்ய நகர்வு தேடல்களைச் செய்வதன் மூலம் இறுதிப் புள்ளி மதிப்பீடுகள் ஒதுக்கப்பட்டன. அதே வன்பொருளில் இயங்கும் ஆல்பா-பீட்டா சீரமைப்பு தேடுபொறிகளுடன் ஒப்பிடும்போது இந்த அமைப்பு எவ்வளவு சிறப்பாக செயல்பட்டது என்பது குறித்து எந்த அறிக்கையும் இல்லை. மாவென் (ஸ்கிராப்பிள்) நிரல் இறுதி விளையாட்டுகளுக்கு பி * தேடலைப் பயன்படுத்தியது. இறுதிப் புள்ளி மதிப்பீடுகள் ஒரு ஹூரிஸ்டிக் திட்டமிடல் முறையைப் பயன்படுத்தி ஒதுக்கப்பட்டன. ஒருங்கிணைந்த விளையாட்டுகளின் தொகுப்பின் கூட்டுத்தொகையில் உகந்த மூலோபாயத்தைக் கணக்கிட பி * தேடல் வழிமுறை பயன்படுத்தப்பட்டுள்ளது. மேலும் காண்க கிளை மற்றும் பிணைக்கப்பட்ட குறிப்புகள் வரைபட வழிமுறைகள் ரூட்டிங் வழிமுறைகள் தேடல் வழிமுறைகள் ஒருங்கிணைந்த உகப்பாக்கம் விளையாட்டு செயற்கை நுண்ணறிவு