B*
কম্পিউটার বিজ্ঞানে, বি * (উচ্চারিত "বি স্টার") একটি সেরা-প্রথম গ্রাফ অনুসন্ধান অ্যালগরিদম যা প্রদত্ত প্রাথমিক নোড থেকে যে কোনও লক্ষ্য নোডে (এক বা একাধিক সম্ভাব্য লক্ষ্যের মধ্যে) সর্বনিম্ন ব্যয়ের পথ খুঁজে পায়। 1979 সালে হান্স বার্লিনার দ্বারা প্রথম প্রকাশিত, এটি এ * অনুসন্ধান অ্যালগরিদমের সাথে সম্পর্কিত। সারসংক্ষেপ অ্যালগরিদম একক বিন্দু-মূল্যবান অনুমানের বিপরীতে গাছের নোডের জন্য ব্যবধান সংরক্ষণ করে। তারপর, গাছের পাতার নোডগুলি অনুসন্ধান করা যেতে পারে যতক্ষণ না শীর্ষ স্তরের নোডগুলির মধ্যে একটির একটি ব্যবধান থাকে যা স্পষ্টভাবে "সেরা"। বি *-ট্রি-র লিফ নোডগুলি অনুমানের পরিবর্তে ব্যবধান মূল্যায়ন দেওয়া হয় যা একক সংখ্যার পরিবর্তে ব্যবধান। ব্যবধানটি সেই নোডের প্রকৃত মান ধারণ করে বলে মনে করা হয়। যদি লিফ নোডের সাথে সংযুক্ত সমস্ত ব্যবধান এই বৈশিষ্ট্যটি সন্তুষ্ট করে, তবে বি * লক্ষ্য অবস্থার একটি সর্বোত্তম পথ চিহ্নিত করবে। ব্যাকআপ প্রক্রিয়া গাছের মধ্যে ব্যবধানগুলি ব্যাক আপ করার জন্য, পিতামাতার উপরের সীমাটি শিশুদের উপরের সীমানার সর্বোচ্চ সীমাতে সেট করা হয়। একজন পিতামাতার নিম্ন সীমা শিশুদের নিম্ন সীমার সর্বাধিক হিসাবে নির্ধারণ করা হয়। মনে রাখবেন যে বিভিন্ন শিশু এই সীমা সরবরাহ করতে পারে। অনুসন্ধান বি *-এর সমাপ্তি পদ্ধতিগতভাবে "পৃথকীকরণ" তৈরি করার জন্য নোডগুলিকে প্রসারিত করে, যা তখন ঘটে যখন মূলের সরাসরি চাইল্ডের নীচের সীমাটি মূলের অন্য কোনও সরাসরি চাইল্ডের উপরের সীমানার মতো কমপক্ষে বড় হয়। একটি গাছ যা শিকড়ে বিচ্ছেদ সৃষ্টি করে তাতে প্রমাণ থাকে যে সেরা শিশু অন্তত অন্য যে কোনও শিশুর মতোই ভাল। বাস্তবে, জটিল অনুসন্ধানগুলি ব্যবহারিক সম্পদ সীমার মধ্যে শেষ নাও হতে পারে। সুতরাং অ্যালগরিদমটি সাধারণত সময় বা মেমরি সীমার মতো কৃত্রিম সমাপ্তি মানদণ্ডের সাথে বর্ধিত করা হয়। যখন একটি কৃত্রিম সীমাকে আঘাত করা হয়, তখন আপনাকে অবশ্যই কোন পদক্ষেপটি নির্বাচন করতে হবে সে সম্পর্কে একটি অনুসন্ধানমূলক সিদ্ধান্ত নিতে হবে। সাধারণত, গাছটি আপনাকে রুট নোডের ব্যবধানের মতো বিস্তৃত প্রমাণ সরবরাহ করবে। সম্প্রসারণ বি * একটি সর্বোত্তম-প্রথম প্রক্রিয়া, যার অর্থ গাছটি অতিক্রম করা খুব কার্যকর, প্রসারিত করার জন্য একটি পাতা খুঁজে বার বার নেমে আসা। এই বিভাগটি বর্ণনা করে যে কীভাবে সম্প্রসারণের জন্য নোডটি বেছে নেওয়া যায়। (দ্রষ্টব্যঃ গাছটি মেমরি-রেসিডেন্ট হোক বা না হোক, এটি সামগ্রিক বাস্তবায়ন দক্ষতার একটি ফাংশন, যার মধ্যে এটি কীভাবে বাস্তব বা ভার্চুয়াল মেমরির মাধ্যমে ম্যাপ করা এবং/অথবা পরিচালিত হতে পারে।) গাছের মূলে, অ্যালগরিদম দুটি কৌশলের মধ্যে একটি প্রয়োগ করে, যাকে প্রুফ-বেস্ট এবং ডিসপ্রুভ-রেস্ট বলা হয়। প্রমাণ-সেরা কৌশলে, অ্যালগরিদম সর্বোচ্চ উপরের সীমানার সাথে যুক্ত নোড নির্বাচন করে। আশা করা যায় যে, সেই নোডের সম্প্রসারণ তার নিম্ন সীমা অন্য যে কোনও নোডের উপরের সীমার চেয়ে বেশি বাড়িয়ে দেবে। ডিসপ্রুভ-রেস্ট কৌশলটি মূলের সন্তানকে নির্বাচন করে যার দ্বিতীয় সর্বোচ্চ উপরের সীমা রয়েছে। আশা করা যায় যে সেই নোডটি প্রসারিত করার মাধ্যমে আপনি উপরের সীমাটি সেরা সন্তানের নীচের সীমার চেয়ে কম করতে সক্ষম হতে পারেন। কৌশল নির্বাচন লক্ষ্য করুন যে ডিসপ্রুভ-রেস্ট কৌশল প্রয়োগ করা অর্থহীন যতক্ষণ না চাইল্ড নোডের নিম্ন সীমাটি সমস্ত নিম্ন সীমার মধ্যে সর্বোচ্চ হয়। মূল অ্যালগরিদম বিবরণ কোন কৌশলটি নির্বাচন করতে হবে সে সম্পর্কে আর কোনও নির্দেশনা দেয়নি। বেশ কয়েকটি যুক্তিসঙ্গত বিকল্প রয়েছে, যেমন ছোট গাছ রয়েছে এমন পছন্দটি প্রসারিত করা। নন-রুট নোডগুলিতে কৌশল নির্বাচন একবার মূলের একটি শিশু নির্বাচিত হয়ে গেলে (প্রুফ-বেস্ট বা ডিসপ্রুভ-রেস্ট ব্যবহার করে) অ্যালগরিদমটি সর্বোচ্চ উপরের বাউন্ডযুক্ত শিশুকে বারবার নির্বাচন করে একটি লিফ নোডে নেমে আসে। যখন একটি লিফ নোডে পৌঁছায়, তখন অ্যালগরিদম সমস্ত উত্তরসূরি নোড তৈরি করে এবং মূল্যায়ন ফাংশন ব্যবহার করে তাদের জন্য ব্যবধান বরাদ্দ করে। তারপর ব্যাকআপ অপারেশন ব্যবহার করে সমস্ত নোডের ব্যবধানগুলি ব্যাক আপ করতে হবে। যখন স্থানান্তর সম্ভব হয়, তখন ব্যাক-আপ ক্রিয়াকলাপের জন্য নোডের মানগুলি পরিবর্তন করার প্রয়োজন হতে পারে যা নির্বাচনের পথে ছিল না। এই ক্ষেত্রে, অ্যালগরিদমের জন্য শিশুদের কাছ থেকে সমস্ত পিতামাতার কাছে পয়েন্টার প্রয়োজন যাতে পরিবর্তনগুলি প্রচার করা যায়। মনে রাখবেন যে প্রচার বন্ধ হতে পারে যখন একটি ব্যাকআপ অপারেশন একটি নোডের সাথে সম্পর্কিত ব্যবধান পরিবর্তন করে না। দৃঢ়তা যদি ব্যবধানগুলি ভুল হয় (এই অর্থে যে নোডের খেলা-তাত্ত্বিক মান ব্যবধানের মধ্যে অন্তর্ভুক্ত নয়), তবে বি * সঠিক পথ সনাক্ত করতে সক্ষম নাও হতে পারে। যাইহোক, অ্যালগরিদমটি অনুশীলনে ত্রুটির জন্য মোটামুটি শক্তিশালী। মাভেন (স্ক্র্যাবল) প্রোগ্রামে একটি উদ্ভাবন রয়েছে যা মূল্যায়নের ত্রুটিগুলি সম্ভব হলে বি * এর দৃust়তা উন্নত করে। যদি পৃথকীকরণের কারণে কোনও অনুসন্ধান বন্ধ হয়ে যায় তবে মাভেন সমস্ত মূল্যায়নের ব্যবধানগুলি সামান্য পরিমাণে প্রসারিত করার পরে অনুসন্ধানটি পুনরায় শুরু করে। এই নীতি ধীরে ধীরে গাছটিকে প্রশস্ত করে, অবশেষে সমস্ত ত্রুটি মুছে দেয়। দুই খেলোয়াড়ের খেলায় সম্প্রসারণ বি * অ্যালগরিদম দুই খেলোয়াড়ের নির্ধারিত শূন্য-সমষ্টি গেমের ক্ষেত্রে প্রযোজ্য। প্রকৃতপক্ষে, একমাত্র পরিবর্তন হল সেই নোডে দিকটি চলার ক্ষেত্রে "সেরা" ব্যাখ্যা করা। সুতরাং আপনার পক্ষ যদি নড়াচড়া করে তবে আপনি সর্বোচ্চ এবং প্রতিপক্ষ যদি নড়াচড়া করে তবে সর্বনিম্ন গ্রহণ করবেন। সমতুল্যভাবে, আপনি সরানোর জন্য পাশের দৃষ্টিকোণ থেকে সমস্ত ব্যবধানের প্রতিনিধিত্ব করতে পারেন এবং তারপরে ব্যাক-আপ অপারেশন চলাকালীন মানগুলিকে অস্বীকার করতে পারেন। অ্যান্ড্রু পালে দাবা খেলায় বি * প্রয়োগ করেন। শেষবিন্দু মূল্যায়নগুলি নাল-মুভ অনুসন্ধানগুলি সম্পাদন করে বরাদ্দ করা হয়েছিল। একই হার্ডওয়্যারে চলমান আলফা-বিটা ছাঁটাই সার্চ ইঞ্জিনগুলির তুলনায় এই সিস্টেমটি কতটা ভাল কাজ করেছে তার কোনও রিপোর্ট নেই। মাভেন (স্ক্র্যাবল) প্রোগ্রামটি শেষ গেমগুলিতে বি * অনুসন্ধান প্রয়োগ করে। একটি হিউরিস্টিক প্ল্যানিং সিস্টেম ব্যবহার করে এন্ডপয়েন্ট মূল্যায়ন বরাদ্দ করা হয়েছিল। বি * সার্চ অ্যালগরিদমটি সমন্বিত গেমের একটি সেটের সমষ্টি খেলায় সর্বোত্তম কৌশল গণনা করতে ব্যবহৃত হয়েছে। আরও দেখুন শাখা এবং আবদ্ধ রেফারেন্স গ্রাফ অ্যালগরিদম রাউটিং অ্যালগরিদম সার্চ অ্যালগরিদম কম্বিনেটরিয়াল অপ্টিমাইজেশন গেম কৃত্রিম বুদ্ধিমত্তা