Bidirectional search
দ্বিমুখী অনুসন্ধান হল একটি গ্রাফ অনুসন্ধান অ্যালগরিদম যা একটি নির্দেশিত গ্রাফে প্রাথমিক শীর্ষ থেকে লক্ষ্য শীর্ষে যাওয়ার একটি সংক্ষিপ্ততম পথ খুঁজে পায়। এটি একযোগে দুটি অনুসন্ধান চালায়ঃ একটি প্রাথমিক অবস্থা থেকে সামনের দিকে এবং একটি গোল থেকে পিছনের দিকে, যখন দুজনের দেখা হয় তখন থেমে যায়। এই পদ্ধতির কারণ হল অনেক ক্ষেত্রে এটি দ্রুততরঃ উদাহরণস্বরূপ, অনুসন্ধান সমস্যা জটিলতার একটি সরলীকৃত মডেলে যেখানে উভয় অনুসন্ধান শাখা ফ্যাক্টর বি সহ একটি গাছকে প্রসারিত করে এবং শুরু থেকে লক্ষ্য পর্যন্ত দূরত্ব ডি হয়, দুটি অনুসন্ধানের প্রত্যেকটির জটিলতা ও (বিডি/2) (বিগ ও নোটেশনে) রয়েছে এবং এই দুটি অনুসন্ধানের সময়ের যোগফল ও (বিডি) জটিলতার তুলনায় অনেক কম যা শুরু থেকে লক্ষ্য পর্যন্ত একক অনুসন্ধানের ফলস্বরূপ হবে। অ্যান্ড্রু গোল্ডবার্গ এবং অন্যান্যরা ডিজকস্ট্রার অ্যালগরিদমের দ্বিমুখী সংস্করণের জন্য সঠিক সমাপ্তি শর্তগুলি ব্যাখ্যা করেছিলেন। এ * অনুসন্ধানের মতো, দ্বি-দিকনির্দেশক অনুসন্ধানটি গোলের অবশিষ্ট দূরত্বের (সামনের গাছে) বা শুরু থেকে (পিছনের গাছে) অনুসন্ধানমূলক অনুমান দ্বারা পরিচালিত হতে পারে। তিনিই প্রথম দ্বিমুখী হিউরিস্টিক সার্চ অ্যালগরিদমের নকশা ও বাস্তবায়ন করেন। শুরু থেকে উদ্ভূত অনুসন্ধান গাছ এবং গোল নোডগুলি সমাধান স্থানের মাঝখানে মিলিত হতে ব্যর্থ হয়েছে। বি. এইচ. এফ. এফ. এ অ্যালগরিদম এই ত্রুটিটি চ্যামপিয়ক্স (1977) সংশোধন করে। একটি গ্রহণযোগ্য হিউরিস্টিক ব্যবহার করে একক-দিকনির্দেশক এ * অ্যালগরিদম দ্বারা পাওয়া একটি সমাধানের পথের দৈর্ঘ্য সংক্ষিপ্ততম; ডি চ্যাম্পিয়ক্সে (1983) বর্ণিত বি. এইচ. এফ. এফ. এ 2 দ্বিমুখী হিউরিস্টিক সংস্করণের জন্য একই বৈশিষ্ট্য রয়েছে। অন্যদের মধ্যে, বি. এইচ. এফ. এফ. এ-র তুলনায় বি. এইচ. এফ. এফ. এ-2-এর আরও সতর্ক সমাপ্তি শর্ত রয়েছে। একটি দ্বিমুখী অনুসন্ধানমূলক অনুসন্ধান হল কোনও রাজ্য থেকে অন্য রাজ্যে রাষ্ট্রীয় স্থান অনুসন্ধান, যা একই সাথে থেকে এবং থেকে অনুসন্ধান করে। এটি অপারেটরদের একটি বৈধ তালিকা প্রদান করে যা প্রয়োগ করা হলে আমাদের দেবে। যদিও এটি মনে হতে পারে যে অপারেটরদের বিপরীত অনুসন্ধানের জন্য বিপরীতমুখী হতে হবে, তবে কোনও নোডের পরিপ্রেক্ষিতে কেবল এমন প্যারেন্ট নোডের সেট খুঁজে বের করতে সক্ষম হওয়া প্রয়োজন যাতে প্রতিটি প্যারেন্ট নোড থেকে কিছু বৈধ অপারেটর বিদ্যমান থাকে। এটিকে প্রায়শই রুট-ফাইন্ডিং ডোমেনের একমুখী রাস্তার সাথে তুলনা করা হয়ঃ উভয় দিকেই ভ্রমণ করতে সক্ষম হওয়ার প্রয়োজন নেই, তবে রাস্তার শেষে দাঁড়ানোর সময় রাস্তার শুরুটি সম্ভাব্য রুট হিসাবে নির্ধারণ করা প্রয়োজন। একইভাবে, বিপরীত চাপযুক্ত প্রান্তগুলির জন্য (অর্থাৎ। উভয় দিকে যাওয়া চাপ) প্রতিটি দিক সমান ব্যয়ের হওয়া আবশ্যক নয়। বিপরীত অনুসন্ধান সর্বদা বিপরীত খরচ ব্যবহার করবে (অর্থাৎ। সামনের দিকে চাপের খরচ)। আরও আনুষ্ঠানিকভাবে, যদি প্যারেন্ট সহ একটি নোড হয়, তবে, থেকে থেকে পর্যন্ত খরচ হিসাবে সংজ্ঞায়িত করা হয়। (Auer Kaindl 2004) পরিভাষা এবং স্বরলিপি-একটি অনুসন্ধান গাছের শাখা-প্রশাখার উপাদান-নোড থেকে নোডে যাওয়ার সাথে যুক্ত খরচ-মূল থেকে নোডে যাওয়ার খরচ-নোড এবং শুরুর লক্ষ্যের মধ্যে দূরত্বের অনুমানমূলক অনুমান লক্ষ্যের অবস্থা (কখনও কখনও, ফাংশনের সাথে বিভ্রান্ত হবেন না) বর্তমান অনুসন্ধানের দিক নির্দেশ করে। প্রচলিত নিয়ম অনুসারে, সামনের দিকের জন্য 1 এবং পিছনের দিকের জন্য 2 এর সমান (কে. ডব্লিউ. এ 1989) বিপরীত অনুসন্ধানের দিক (অর্থাৎ)। ঘ দিকে অনুসন্ধান গাছ। যদি, মূল হয়, যদি, মূল হল এর পাতা (কখনও কখনও হিসাবে উল্লেখ করা হয়)। এই সেট থেকে সম্প্রসারণের জন্য একটি নোড বেছে নেওয়া হয়। দ্বিমুখী অনুসন্ধানে, এগুলিকে কখনও কখনও অনুসন্ধান 'ফ্রন্টিয়ারস' বা 'ওয়েভফ্রন্টস' বলা হয়, যা কোনও অনুসন্ধানকে গ্রাফিকভাবে উপস্থাপন করার সময় এগুলি কীভাবে প্রদর্শিত হয় তা উল্লেখ করে। এই রূপকটিতে, একটি 'সংঘর্ষ' ঘটে যখন, সম্প্রসারণ পর্যায়ে, একটি তরঙ্গফ্রন্ট থেকে একটি নোডের বিরোধী তরঙ্গফ্রন্টে উত্তরসূরি পাওয়া যায়। এর অ-পাতার নোডগুলি। এই সেটটিতে অনুসন্ধান পদ্ধতির দ্বারা ইতিমধ্যে পরিদর্শন করা নোডগুলি রয়েছে দ্বিমুখী অনুসন্ধানের জন্য দ্বিমুখী অ্যালগরিদমগুলি বিস্তৃতভাবে তিনটি বিভাগে বিভক্ত করা যেতে পারেঃ ফ্রন্ট-টু-ফ্রন্ট, ফ্রন্ট-টু-ব্যাক (বা ফ্রন্ট-টু-এন্ড), এবং পেরিমিটার সার্চ (কাইন্ডল কাইঞ্জ 1997)। হিউরিস্টিক গণনা করতে ব্যবহৃত ফাংশন দ্বারা এগুলি পৃথক হয়। ফ্রন্ট-টু-ব্যাক অ্যালগরিদমগুলি বিপরীত অনুসন্ধান গাছের মূল এবং মূলের মধ্যে অনুসন্ধানমূলক অনুমান ব্যবহার করে একটি নোডের মান গণনা করে, বা। ফ্রন্ট-টু-ব্যাক তিনটি বিভাগের মধ্যে সবচেয়ে সক্রিয়ভাবে গবেষণা করা হয়। বর্তমান সেরা অ্যালগরিদম (অন্ততপক্ষে পনেরোটি ধাঁধা ডোমেনে) হল বায়ম্যাক্স-বিএস * এফ অ্যালগরিদম, যা আউয়ার এবং কাইন্ডল (আউয়ার, কাইন্ডল 2004) দ্বারা তৈরি করা হয়েছে। ফ্রন্ট-টু-ফ্রন্ট অ্যালগরিদমগুলি এবং এর কিছু উপসেটের মধ্যে অনুসন্ধানমূলক অনুমান ব্যবহার করে একটি নোডের মান গণনা করে। ক্যানোনিকাল উদাহরণ হল বি. এইচ. এফ. এফ. এ (দ্বিমুখী হিউরিস্টিক ফ্রন্ট-টু-ফ্রন্ট অ্যালগরিদম), যেখানে ফাংশনটিকে বর্তমান নোড এবং বিপরীত ফ্রন্টের নোডগুলির মধ্যে সমস্ত হিউরিস্টিক অনুমানের সর্বনিম্ন হিসাবে সংজ্ঞায়িত করা হয়। অথবা, আনুষ্ঠানিকভাবেঃ যেখানে গ্রহণযোগ্য রিটার্ন (অর্থাৎ। অতিরিক্ত মূল্যায়ন না করে) নোড এবং এর মধ্যে দূরত্বের অনুমানমূলক অনুমান। ফ্রন্ট-টু-ফ্রন্ট অত্যধিক গণনামূলক চাহিদা থেকে ভুগছে। প্রতিবার যখন কোনও নোডকে খোলা তালিকায় রাখা হয়, তখন তার মান অবশ্যই গণনা করতে হবে। উপরে বর্ণিত হিসাবে, এর সাথে বিপরীত সেটের প্রতিটি নোড থেকে একটি হিউরিস্টিক অনুমান গণনা করা জড়িত। সেটগুলি সমস্ত ডোমেনের জন্য আকারে দ্রুত বৃদ্ধি পায়। রেফারেন্স। । । । গ্রাফ অ্যালগরিদম অনুসন্ধান অ্যালগরিদম