B*
کمپیوٹر سائنس میں، بی * (جسے "بی اسٹار" کہا جاتا ہے) ایک بہترین-پہلا گراف سرچ الگورتھم ہے جو کسی دیئے گئے ابتدائی نوڈ سے کسی بھی گول نوڈ (ایک یا زیادہ ممکنہ اہداف میں سے) تک کم سے کم لاگت والا راستہ تلاش کرتا ہے۔ سب سے پہلے 1979 میں ہنس برلنر نے شائع کیا، اس کا تعلق اے * سرچ الگورتھم سے ہے۔ خلاصہ الگورتھم واحد پوائنٹ ویلیوڈ تخمینوں کے برخلاف درخت کے نوڈس کے لیے وقفے کو محفوظ کرتا ہے۔ پھر، درخت کے لیف نوڈس کو اس وقت تک تلاش کیا جا سکتا ہے جب تک کہ اوپری سطح کے نوڈس میں سے کسی ایک کا وقفہ نہ ہو جو واضح طور پر "بہترین" ہو۔ تفصیلات تخمینے کے بجائے وقفے کی تشخیص B *-درخت کے لیف نوڈس کی تشخیص کی جاتی ہے جو واحد اعداد کے بجائے وقفے ہوتے ہیں۔ وقفہ اس نوڈ کی صحیح قیمت پر مشتمل ہونا چاہیے۔ اگر لیف نوڈس سے منسلک تمام وقفے اس خاصیت کو پورا کرتے ہیں، تو B * گول اسٹیٹ کے لیے ایک بہترین راستے کی نشاندہی کرے گا۔ بیک اپ کا عمل درخت کے اندر وقفوں کا بیک اپ لینے کے لیے، والدین کی اوپری حد بچوں کی زیادہ سے زیادہ اوپری حدود پر مقرر کی جاتی ہے۔ والدین کی نچلی حد بچوں کی نچلی حد کے زیادہ سے زیادہ حد تک مقرر کی جاتی ہے۔ نوٹ کریں کہ مختلف بچے ان حدود کی فراہمی کر سکتے ہیں۔ تلاش B * کا خاتمہ "علیحدگی" پیدا کرنے کے لیے نوڈس کو منظم طریقے سے وسعت دیتا ہے، جو اس وقت ہوتا ہے جب جڑ کے براہ راست بچے کی نچلی حد کم از کم اتنی ہی بڑی ہوتی ہے جتنی کہ جڑ کے کسی دوسرے براہ راست بچے کی اوپری حد ہوتی ہے۔ ایک درخت جو جڑ سے علیحدگی پیدا کرتا ہے اس بات کا ثبوت رکھتا ہے کہ بہترین بچہ کم از کم اتنا ہی اچھا ہے جتنا کسی دوسرے بچے کا۔ عملی طور پر، پیچیدہ تلاشیں عملی وسائل کی حدود میں ختم نہیں ہو سکتی ہیں۔ لہذا الگورتھم کو عام طور پر مصنوعی اختتامی معیار جیسے وقت یا میموری کی حدود کے ساتھ بڑھایا جاتا ہے۔ جب کسی مصنوعی حد کو مارا جاتا ہے، تو آپ کو یہ فیصلہ کرنا چاہیے کہ کس اقدام کو منتخب کرنا ہے۔ عام طور پر، درخت آپ کو وسیع ثبوت فراہم کرے گا، جیسے جڑ کے نوڈس کے وقفے۔ توسیع بی * ایک بہترین پہلا عمل ہے، جس کا مطلب ہے کہ درخت کو عبور کرنا بہت موثر ہے، بار بار نیچے اترتے ہوئے پھیلنے کے لیے پتی تلاش کرنا۔ یہ سیکشن بیان کرتا ہے کہ توسیع کے لیے نوڈ کا انتخاب کیسے کیا جائے۔ (نوٹ: چاہے ٹری میموری رہائشی ہو یا نہ ہو، یہ عمل درآمد کی مجموعی کارکردگی کا ایک کام ہے، بشمول اسے حقیقی یا ورچوئل میموری کے ذریعے کیسے نقشہ بنایا جا سکتا ہے اور/یا منظم کیا جا سکتا ہے۔) درخت کی جڑ پر، الگورتھم دو حکمت عملیوں میں سے ایک کا اطلاق کرتا ہے، جسے ثابت بہترین اور غلط ثابت آرام کہا جاتا ہے۔ ثابت بہترین حکمت عملی میں، الگورتھم سب سے زیادہ اوپری باؤنڈ سے وابستہ نوڈ کا انتخاب کرتا ہے۔ امید یہ ہے کہ اس نوڈ کو وسعت دینے سے اس کی نچلی حد کسی بھی دوسرے نوڈ کی اوپری حد سے زیادہ بڑھ جائے گی۔ ڈس پروو-ریسٹ حکمت عملی جڑ کے بچے کا انتخاب کرتی ہے جس کی دوسری سب سے زیادہ اوپری حد ہوتی ہے۔ امید یہ ہے کہ اس نوڈ کو بڑھا کر آپ اوپری حد کو بہترین بچے کی نچلی حد سے کم کرنے کے قابل ہو سکتے ہیں۔ حکمت عملی کا انتخاب نوٹ کریں کہ ڈس پروو-ریسٹ حکمت عملی کا اطلاق اس وقت تک بے معنی ہے جب تک کہ چائلڈ نوڈ کی نچلی حد جس میں سب سے زیادہ اوپری حد ہوتی ہے وہ تمام نچلی حدود میں سب سے زیادہ ہوتی ہے۔ اصل الگورتھم کی تفصیل نے کون سی حکمت عملی منتخب کرنے کے بارے میں مزید رہنمائی نہیں دی۔ کئی معقول متبادل ہیں، جیسے کہ چھوٹے درخت والے انتخاب کو بڑھانا۔ غیر جڑ نوڈس پر حکمت عملی کا انتخاب ایک بار جڑ کے بچے کو منتخب کرنے کے بعد (ثابت بہترین یا غلط ثابت کرنے والے آرام کا استعمال کرتے ہوئے) پھر الگورتھم بار بار اس بچے کو منتخب کرکے لیف نوڈ پر اترتا ہے جس کی اوپری حد سب سے زیادہ ہوتی ہے۔ جب لیف نوڈ تک پہنچ جاتا ہے، تو الگورتھم تمام جانشین نوڈس تیار کرتا ہے اور تشخیصی فنکشن کا استعمال کرتے ہوئے انہیں وقفے تفویض کرتا ہے۔ پھر بیک اپ آپریشن کا استعمال کرتے ہوئے تمام نوڈس کے وقفوں کا بیک اپ لینا پڑتا ہے۔ جب منتقلی ممکن ہو، تو بیک اپ آپریشن کو نوڈس کی اقدار کو تبدیل کرنے کی ضرورت پڑ سکتی ہے جو سلیکشن پاتھ پر نہیں تھے۔ اس صورت میں، الگورتھم کو بچوں سے تمام والدین کو اشارے کی ضرورت ہوتی ہے تاکہ تبدیلیوں کو پھیلایا جا سکے۔ نوٹ کریں کہ پروپیگنڈا تب بند ہو سکتا ہے جب بیک اپ آپریشن نوڈ سے وابستہ وقفے کو تبدیل نہیں کرتا ہے۔ مضبوطی اگر وقفے غلط ہیں (اس معنی میں کہ نوڈ کی گیم تھیوریٹک ویلیو وقفے کے اندر موجود نہیں ہے)، تو B * صحیح راستے کی نشاندہی کرنے کے قابل نہیں ہوسکتا ہے۔ تاہم، الگورتھم عملی طور پر غلطیوں کے لیے کافی مضبوط ہے۔ میوین (سکریبل) پروگرام میں ایک اختراع ہے جو تشخیص کی غلطیاں ممکن ہونے پر بی * کی مضبوطی کو بہتر بناتا ہے۔ اگر علیحدگی کی وجہ سے کوئی تلاش ختم ہو جاتی ہے تو میوین تمام تشخیصی وقفوں کو تھوڑی مقدار میں وسیع کرنے کے بعد تلاش دوبارہ شروع کرتا ہے۔ یہ پالیسی بتدریج درخت کو وسیع کرتی ہے، بالآخر تمام غلطیوں کو مٹا دیتی ہے۔ دو کھلاڑیوں کے کھیلوں میں توسیع بی * الگورتھم دو کھلاڑیوں کے تعیناتی صفر رقم کے کھیلوں پر لاگو ہوتا ہے۔ درحقیقت، واحد تبدیلی یہ ہے کہ اس نوڈ میں حرکت کرنے والی طرف کے حوالے سے "بہترین" کی تشریح کی جائے۔ لہذا اگر آپ کی طرف حرکت کر رہی ہے تو آپ زیادہ سے زیادہ لیں گے، اور اگر مخالف حرکت کر رہا ہے تو کم سے کم۔ مساوی طور پر، آپ منتقل ہونے کے لیے سائیڈ کے نقطہ نظر سے تمام وقفوں کی نمائندگی کر سکتے ہیں، اور پھر بیک اپ آپریشن کے دوران اقدار کو مسترد کر سکتے ہیں۔ اینڈریو پیلے نے شطرنج میں B * کا اطلاق کیا۔ اختتامی نقطہ کی تشخیص صفر حرکت کی تلاشوں کو انجام دے کر تفویض کی گئی تھی۔ ایک ہی ہارڈ ویئر پر چلنے والے الفا بیٹا تراشنے والے سرچ انجنوں کے مقابلے میں اس نظام نے کتنی اچھی کارکردگی کا مظاہرہ کیا اس کی کوئی رپورٹ نہیں ہے۔ میوین (سکریبل) پروگرام نے اختتامی کھیلوں پر بی * سرچ کا اطلاق کیا۔ اختتامی نقطہ کی تشخیص ایک ہیورسٹک پلاننگ سسٹم کا استعمال کرتے ہوئے تفویض کی گئی تھی۔ B * سرچ الگورتھم کو مشترکہ کھیلوں کے ایک سیٹ کے مجموعے میں زیادہ سے زیادہ حکمت عملی کا حساب لگانے کے لیے استعمال کیا گیا ہے۔ برانچ اینڈ باؤنڈ ریفرنسز گراف الگورتھم روٹنگ الگورتھم سرچ الگورتھم کمبینٹوریئل آپٹیمائزیشن گیم مصنوعی ذہانت بھی دیکھیں۔