Reverse-search algorithm
বিপরীত-অনুসন্ধান অ্যালগরিদম হল নির্দিষ্ট শ্রেণীর সমন্বিত বস্তু থেকে প্রদত্ত আকারের সমস্ত বস্তু তৈরির জন্য অ্যালগরিদমের একটি শ্রেণী। অনেক ক্ষেত্রে, এই পদ্ধতিগুলি প্রতি বস্তুতে বহুপদী সময়ে বস্তু তৈরি করার অনুমতি দেয়, শুধুমাত্র ধ্রুবক সংখ্যক বস্তু (বহুপদী স্থান) সংরক্ষণ করার জন্য পর্যাপ্ত মেমরি ব্যবহার করে। (সাধারণত, তবে, এগুলিকে পলিনোমিয়াল-টাইম অ্যালগরিদম হিসাবে শ্রেণীবদ্ধ করা হয় না, কারণ এগুলি উৎপন্ন বস্তুর সংখ্যা সূচকীয়।) তারা তাদের রাজ্য স্থানের একটি বিস্তৃত গাছে উৎপন্ন হওয়া বস্তুগুলিকে সংগঠিত করে কাজ করে এবং তারপরে এই গাছের গভীর-প্রথম অনুসন্ধান করে। 1991 সালে ডেভিড অ্যাভিস এবং কোমেই ফুকুদা উত্তল পলিটোপগুলির শীর্ষস্থান এবং হাইপারপ্লেনের বিন্যাসের কোষ তৈরির সমস্যাগুলির জন্য বিপরীত-অনুসন্ধান অ্যালগরিদম চালু করেছিলেন। 1996 সালে অ্যাভিস এবং ফুকুদা দ্বারা এগুলি আরও বিস্তৃতভাবে আনুষ্ঠানিক করা হয়েছিল। নীতিগুলি একটি বিপরীত-অনুসন্ধান অ্যালগরিদম একটি স্টেট স্পেসে সমন্বিত বস্তু তৈরি করে, একটি অন্তর্নিহিত গ্রাফ যার শীর্ষগুলি তালিকাভুক্ত করা বস্তু এবং যার প্রান্তগুলি বস্তুর জোড়াগুলিকে সংযুক্ত করার জন্য নির্দিষ্ট "স্থানীয় পদক্ষেপ" উপস্থাপন করে, সাধারণত তাদের কাঠামোতে ছোট পরিবর্তন করে। এটি এই স্টেট স্পেসের একটি শিকড়যুক্ত বিস্তৃত গাছের গভীর-প্রথম অনুসন্ধান ব্যবহার করে প্রতিটি বস্তুকে খুঁজে পায়, যা নিম্নলিখিত তথ্য দ্বারা বর্ণনা করা হয়েছেঃ বিস্তৃত গাছের মূল, বস্তুর মধ্যে একটি গাছের প্রতিটি বস্তুর প্যারেন্ট তৈরি করার জন্য একটি সাবরুটিন, এই বৈশিষ্ট্য সহ যে যদি যথেষ্ট বার পুনরাবৃত্তি করা হয় তবে এটি অবশেষে মূল এ-তে পৌঁছাবে রাষ্ট্রীয় স্থানের সমস্ত প্রতিবেশীদের তালিকাভুক্ত করার জন্য একটি সাবরুটিনে (যার মধ্যে সবাই গাছের প্রতিবেশী নাও হতে পারে) এই তথ্য থেকে গাছের কোনও প্রদত্ত নোডের সন্তানদের খুঁজে পাওয়া সম্ভব, প্যারেন্ট সাবরুটিনের দেওয়া লিঙ্কগুলি বিপরীত করেঃ তারা কেবল সেই প্রতিবেশী যাদের প্যারেন্ট প্রদত্ত নোডঃ চাইল্ড নোডের এই বিপরীত লিঙ্কগুলিই অ্যালগরিদম অনুসন্ধান করে। এই বিস্তৃত গাছের একটি ধ্রুপদী গভীরতা-প্রথম অনুসন্ধান গাছটিকে পুনরাবৃত্তভাবে অতিক্রম করবে, মূল থেকে শুরু করে, প্রতিটি নোডে সমস্ত শিশুদের তালিকাভুক্ত করবে এবং প্রত্যেকটির জন্য একটি পুনরাবৃত্তিমূলক কল করবে। চক্র সহ একটি গ্রাফের গভীর-প্রথম অনুসন্ধানের বিপরীতে, বারবার পরিদর্শন এড়াতে ইতিমধ্যে পরিদর্শন করা নোডগুলির সেট বজায় রাখার প্রয়োজন নেই; একটি গাছে এই ধরনের পুনরাবৃত্তি সম্ভব নয়। যাইহোক, এই পুনরাবৃত্তিমূলক অ্যালগরিদমটির কল স্ট্যাকের জন্য এখনও প্রচুর পরিমাণে মেমরির প্রয়োজন হতে পারে, যখন গাছটি খুব গভীর থাকে। পরিবর্তে, বিপরীত অনুসন্ধান শুধুমাত্র দুটি বস্তু সংরক্ষণ করার সময় একই ক্রমে বিস্তৃত গাছটিকে অতিক্রম করেঃ ট্র্যাভার্সালের বর্তমান বস্তু এবং পূর্বে অতিক্রম করা বস্তু। প্রাথমিকভাবে, বর্তমান বস্তুটি গাছের মূলে সেট করা থাকে এবং এর আগে কোনও বস্তু থাকে না। এই তথ্য থেকে, নিম্নলিখিত কেস বিশ্লেষণের মাধ্যমে ট্র্যাভার্সালের পরবর্তী ধাপ নির্ধারণ করা সম্ভবঃ যদি কোনও পূর্ববর্তী বস্তু না থাকে, বা পূর্ববর্তী বস্তুটি বর্তমান বস্তুর অভিভাবক হয়, তবে এই প্রথম ট্র্যাভার্সাল বর্তমান বস্তুর কাছে পৌঁছেছে, তাই এটি অনুসন্ধান থেকে আউটপুট। পরবর্তী উদ্দেশ্য হল তার প্রথম সন্তান বা, যদি তার কোনও সন্তান না থাকে, তার পিতামাতা। অন্যান্য সমস্ত ক্ষেত্রে, পূর্ববর্তী বস্তুটি অবশ্যই বর্তমান বস্তুর একটি শিশু হতে হবে। অ্যালগরিদমটি এই পূর্ববর্তী সন্তানের কাছে না পৌঁছানো পর্যন্ত শিশুদের (অর্থাৎ, বর্তমান বস্তুর রাষ্ট্র-স্থান প্রতিবেশী যাদের বর্তমান বস্তুটি তাদের পিতামাতা হিসাবে রয়েছে) একবারে তালিকাভুক্ত করে এবং তারপরে শিশুদের এই তালিকায় আরও একটি পদক্ষেপ নেয়। যদি অন্য একটি শিশুকে এইভাবে পাওয়া যায়, তবে এটি পরবর্তী বস্তু। যদি কোনও পরবর্তী চাইল্ড না থাকে এবং বর্তমান বস্তুটি মূল না হয়, তবে পরবর্তী বস্তুটি বর্তমান বস্তুর প্যারেন্ট। অবশিষ্ট ক্ষেত্রে, যখন কোনও পরবর্তী চাইল্ড থাকে না এবং বর্তমান বস্তুটি মূল হয়, তখন বিপরীত অনুসন্ধানটি শেষ হয়। এই অ্যালগরিদম অনুসন্ধানের প্রতিটি ধাপের জন্য একটি বস্তুর প্রতিবেশীদের একবার তালিকাভুক্ত করে। যাইহোক, যদি তালিকাভুক্ত করার মতো কোনও বস্তু থাকে, তবে অনুসন্ধানটি পদক্ষেপগুলি সম্পাদন করে, তাই এটি বস্তুর প্রতিবেশীদের কতবার তৈরি করে তা পুনরাবৃত্তিমূলক গভীরতা-প্রথম অনুসন্ধান একই কাজটি কতবার করবে তার দুই গুণকের মধ্যে থাকে। প্রয়োগগুলি বিপরীত অনুসন্ধান প্রয়োগ করা হয়েছে এমন সমস্যাগুলির উদাহরণগুলির মধ্যে নিম্নলিখিত সংমিশ্রণগত প্রজন্মের সমস্যাগুলি অন্তর্ভুক্ত রয়েছেঃ সাধারণ উত্তল পলিটোপগুলির উল্লম্বতা যদি একটি-মাত্রিক উত্তল পলিটোপকে অর্ধ-স্থানগুলির ছেদ হিসাবে সংজ্ঞায়িত করা হয়, তবে এর শীর্ষগুলিকে অর্ধ-স্থানগুলির মধ্যে আবদ্ধ হাইপারপ্লেনের ছেদ বিন্দু বা আরও বেশি হিসাবে বর্ণনা করা যেতে পারে; এটি একটি সাধারণ পলিটোপ যদি কোনও শীর্ষ এই হাইপারপ্লেনের চেয়ে বেশি ছেদ না হয়। ভার্টেক্স গণনা সমস্যা হল এই সমস্ত শীর্ষগুলি তালিকাভুক্ত করার সমস্যা। পলিটোপের প্রান্তগুলি শীর্ষস্থানের জোড়াগুলিকে সংযুক্ত করে যার মধ্যে সাধারণভাবে হাইপারপ্লেন রয়েছে, তাই শীর্ষস্থান এবং প্রান্তগুলি একটি রাষ্ট্রীয় স্থান গঠন করে যেখানে প্রতিটি শীর্ষস্থানের প্রতিবেশী থাকে। লিনিয়ার প্রোগ্রামিং তত্ত্ব থেকে সিম্প্লেক্স অ্যালগরিদম একটি শীর্ষ খুঁজে পায় যা স্থানাঙ্কের একটি প্রদত্ত রৈখিক ফাংশনকে সর্বাধিক করে তোলে, শীর্ষ থেকে শীর্ষে হাঁটার মাধ্যমে, প্রতিটি ধাপে ফাংশনের বৃহত্তর মান সহ একটি শীর্ষ বেছে নেয়; "পিভট রুল"-এর বেশ কয়েকটি মানক পছন্দ রয়েছে যা আরও সুনির্দিষ্টভাবে নির্দিষ্ট করে যে কোন শীর্ষটি বেছে নিতে হবে। এই ধরনের যে কোনও পিভট নিয়মকে পলিটোপের একটি বিস্তৃত গাছের মূল ফাংশনকে সংজ্ঞায়িত করা হিসাবে ব্যাখ্যা করা যেতে পারে, যার মূলটি সর্বোত্তম শীর্ষ। এই তথ্যে বিপরীত অনুসন্ধান প্রয়োগ করলে পলিটোপের সমস্ত শীর্ষ তৈরি হয়। একটি অনুরূপ অ্যালগরিদম একটি রৈখিক প্রোগ্রামের সমস্ত ভিত্তি গণনা করতে পারে, এটি একটি সরল পলিটোপকে সংজ্ঞায়িত করার প্রয়োজন ছাড়াই। হাইপারপ্লেন বিন্যাসের কোষ একটি হাইপারপ্লেন বিন্যাস ইউক্লিডীয় স্থানকে কোষে বিভক্ত করে, প্রতিটি একটি "সাইন ভেক্টর" দ্বারা বর্ণনা করা হয় যা বর্ণনা করে যে এর বিন্দুগুলি হাইপারপ্লেনগুলির মধ্যে একটির (চিহ্ন 0) অন্তর্গত, হাইপারপ্লেনটির একপাশে (চিহ্ন + 1), বা অন্য দিকে (চিহ্ন-1) রয়েছে কিনা। কোষগুলি স্থানীয় পদক্ষেপের অধীনে একটি সংযুক্ত অবস্থা স্থান গঠন করে যা একটি একক দ্বারা একটি চিহ্ন পরিবর্তন করে এবং একটি রৈখিক প্রোগ্রামিং সম্ভাব্যতা সমস্যা সমাধান করে এই ক্রিয়াটি একটি বৈধ কোষ তৈরি করে কিনা তা পরীক্ষা করা সম্ভব। মূল কোষের যে কোনও পছন্দের জন্য একটি স্প্যানিং ট্রি তৈরি করা যেতে পারে একটি মূল অপারেটরকে সংজ্ঞায়িত করে যা প্রথম সম্ভাব্য পরিবর্তন করে যা সাইন ভেক্টরকে মূলের কাছাকাছি নিয়ে আসে। এই স্টেট স্পেস এবং প্যারেন্ট অপারেটরের জন্য বিপরীত অনুসন্ধান ব্যবহার করে প্রতি কোষে বহুপদী সময়ে সমস্ত কোষ তালিকাভুক্ত করার জন্য একটি অ্যালগরিদম তৈরি করে। বিন্দু-সেট ত্রিভুজ একটি সমতলীয় বিন্দু সেটের ত্রিভুজগুলি "উল্টানো" পদক্ষেপ দ্বারা সংযুক্ত থাকে যা একটি ত্রিভুজ থেকে একটি তির্যককে সরিয়ে অন্যটি দ্বারা প্রতিস্থাপন করে। যদি ডেলাউনে ত্রিভুজকে মূল হিসাবে বেছে নেওয়া হয়, তবে প্রতিটি ত্রিভুজকে ডেলাউনে ত্রিভুজে এমন ধাপ দ্বারা উল্টানো যেতে পারে যেখানে চারটি বিন্দুর কিছু উপসেটের ত্রিভুজকে তার ডেলাউনে ত্রিভুজ দ্বারা প্রতিস্থাপিত করা হয়। প্রতিটি ত্রিভুজের মূল হিসাবে প্রথম ডেলাউনে পাল্টাকে বেছে নেওয়া এবং স্থানীয় অনুসন্ধান প্রয়োগ করা, প্রতি ত্রিভুজের বহুপদী সময়ে সমস্ত ত্রিভুজকে তালিকাভুক্ত করার জন্য একটি অ্যালগরিদম তৈরি করে। সংযুক্ত সাবগ্রাফ একটি প্রদত্ত সংযুক্ত গ্রাফের সংযুক্ত সাবগ্রাফ এবং সংযুক্ত প্ররোচিত সাবগ্রাফগুলি একটি স্টেট স্পেস গঠন করে যার স্থানীয় পদক্ষেপগুলি যথাক্রমে গ্রাফের একক প্রান্ত বা শীর্ষের সংযোজন বা অপসারণ। এই স্টেট স্পেসের একটি স্প্যানিং ট্রি প্রথম প্রান্ত বা শীর্ষ (প্রান্ত বা শীর্ষগুলির কিছু ক্রমে) যোগ করে পাওয়া যেতে পারে যার সংযোজন আরেকটি সংযুক্ত সাবগ্রাফ তৈরি করে; এর মূল হল পুরো গ্রাফ। এই স্টেট স্পেস এবং প্যারেন্ট অপারেটরে স্থানীয় অনুসন্ধান প্রয়োগ করে সমস্ত সংযুক্ত সাবগ্রাফকে প্রতি সাবগ্রাফ বহুপদী সময়ে তালিকাভুক্ত করার জন্য একটি অ্যালগরিদম তৈরি করে। অন্যান্য প্রয়োগের মধ্যে নিম্নলিখিত কাঠামো তৈরির জন্য অ্যালগরিদম অন্তর্ভুক্ত রয়েছেঃ পলিওমিনোস, পলিঅ্যামন্ড প্রোটাইল এবং পলিহেক্স (গণিত) হাইড্রোকার্বন অণু। নির্দেশিত অ্যাসাইক্লিক গ্রাফের টপোলজিকাল অর্ডারিং, একটি স্টেট স্পেস ব্যবহার করে যার স্থানীয় পদক্ষেপগুলি দুটি উপাদানের ক্রমকে বিপরীত করে। গ্রাফের বিস্তৃত গাছ, প্ল্যানার পয়েন্ট সেটের বিস্তৃত গাছ এবং আরও সাধারণভাবে ম্যাট্রয়েডের ঘাঁটি, একটি রাষ্ট্রীয় স্থান ব্যবহার করে যা এক প্রান্তকে অন্য প্রান্তের সাথে অদলবদল করে। অয়লার গ্রাফগুলিতে ভ্রমণ করেন। বিরল গ্রাফের সর্বাধিক স্বাধীন সেট। সর্বাধিক সমতলীয় গ্রাফ এবং পলিহেড্রাল গ্রাফ। একটি নির্দিষ্ট পয়েন্ট সেটের উপর নন-ক্রসিং ন্যূনতম অনমনীয় গ্রাফ। পার্শ্ববর্তী বহুভুজ, বহুভুজ যার কিছু নির্দিষ্ট বিন্দুর সমষ্টি শীর্ষবিন্দু হিসাবে থাকে এবং বাকিগুলিকে ঘিরে রাখে, এমন একটি স্থিতি স্থান ব্যবহার করে যা বহুভুজের একটি শীর্ষ যোগ করে বা সরিয়ে দেয়। মিঙ্কোভস্কির উল্লম্ব বা দিকগুলি উত্তল পলিটোপগুলির যোগফল। মনোমিয়াল আদর্শের কোণগুলি (মাল্টিডিগ্রি)। তথ্যসূত্র অনুসন্ধান অ্যালগরিদম সমন্বিত অ্যালগরিদম