Level ancestor problem
গ্রাফ তত্ত্ব এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানে, স্তরের পূর্বপুরুষ সমস্যা হল একটি প্রদত্ত মূলযুক্ত গাছ টি-কে একটি তথ্য কাঠামোতে প্রাকপ্রক্রিয়াকরণের সমস্যা যা গাছের মূল থেকে নির্দিষ্ট দূরত্বে প্রদত্ত নোডের পূর্বপুরুষ নির্ধারণ করতে পারে। আরও সুনির্দিষ্টভাবে বলতে গেলে, টি-কে এন নোড সহ একটি শিকড়যুক্ত গাছ হতে দিন এবং ভি-কে টি-এর একটি নির্বিচারে নোড হতে দিন। স্তরের পূর্বপুরুষের প্রশ্ন এলএ (ভি, ডি) গভীরতায় ডি-তে নোড ভি-এর পূর্বপুরুষকে অনুরোধ করে, যেখানে একটি গাছে নোড ভি-এর গভীরতা হল গাছের মূল থেকে নোড ভি পর্যন্ত সংক্ষিপ্ততম পথের প্রান্তের সংখ্যা। এই সমস্যাটি প্রতি প্রশ্নের জন্য ধ্রুবক সময়ে সমাধান করা সম্ভব, একটি প্রাক প্রক্রিয়াকরণ অ্যালগরিদমের পরে যা ও (এন) নেয় এবং যা একটি ডেটা কাঠামো তৈরি করে যা ও (এন) স্টোরেজ স্পেস ব্যবহার করে। নিষ্ক্রিয় পদ্ধতি একটি নোডের একটি স্তরের পূর্বপুরুষ খুঁজে বের করার সবচেয়ে সহজ উপায় হল গাছের শিকড়ের দিকে গাছে আরোহণ করা। গাছের শিকড়ের পথে, একটি নোডের প্রতিটি পূর্বপুরুষ পরিদর্শন করা যেতে পারে এবং তাই রিপোর্ট করা যেতে পারে। এই ক্ষেত্রে, গাছটিকে পূর্বপ্রক্রিয়া করার প্রয়োজন নেই এবং একটি প্রশ্নের উত্তর দেওয়ার সময় হল ও (এইচ), যেখানে "এইচ" হল গাছের উচ্চতা। এই পদ্ধতিটি এমন পরিস্থিতিতে সম্ভব নয় যেখানে গাছের উচ্চতা বেশি হতে পারে এবং বিপুল সংখ্যক প্রশ্ন প্রক্রিয়াকরণের প্রয়োজন হয়। বিকল্পভাবে, সমস্ত সম্ভাব্য সমাধান আগে থেকে গণনা করা যেতে পারে এবং একটি টেবিলে সংরক্ষণ করা যেতে পারে। এই ক্ষেত্রে, প্রশ্নের উত্তর ও (1)-এ দেওয়া যেতে পারে তবে স্থান এবং প্রাক প্রক্রিয়াকরণের সময় হল ও (এন2)। কোনও প্রাক প্রক্রিয়াকরণ ছাড়াই ধ্রুবক সময়ে উত্তর দেওয়া যেতে পারে এমন সহজতম প্রশ্নগুলি হল এল. এ (ভি, 0) এবং এল. এ (ভি, গভীরতা (ভি))। প্রথম ক্ষেত্রে, উত্তরটি সর্বদা গাছের মূল এবং পরের ক্ষেত্রে, উত্তরটি নোড ভি নিজেই। এই ফলাফলগুলির প্রত্যেকটিতে ও (1) লাগে। একটি তির্যক বাইনারি র্যান্ডম অ্যাক্সেস তালিকায় গাছের মধ্য দিয়ে পথগুলি সংরক্ষণ করলে গাছটিকে একবারে এক ও (1) ধাপে নীচের দিকে প্রসারিত করা যায়, তবে এখন অনুসন্ধানটি ও (লগ (পি))-তে এগিয়ে যাওয়ার অনুমতি দেয়, যেখানে "পি" হল ভি থেকে অনুরোধ করা গভীরতা পর্যন্ত দূরত্ব। এই পদ্ধতিটি সম্ভব হয় যখন গাছটি বিশেষভাবে প্রশস্ত হয় বা অনলাইনে প্রসারিত করা হবে এবং তাই কার্যকরভাবে প্রাক-প্রক্রিয়াজাত করা যায় না, কারণ সঞ্চয় এবং প্রবেশাধিকারের সময় সম্পূর্ণরূপে পথের দৈর্ঘ্য দ্বারা নির্ধারিত হয়। জাম্প পয়েন্টার অ্যালগরিদম জাম্প পয়েন্টার অ্যালগরিদম ও (এন লগ এন) সময়ে একটি ট্রি প্রাক-প্রক্রিয়া করে এবং ও (লগ এন) সময়ে স্তরের পূর্বপুরুষের প্রশ্নের উত্তর দেয়। জাম্প পয়েন্টার অ্যালগরিদম গাছের প্রতিটি শীর্ষে এন পয়েন্টার লগ করার জন্য যুক্ত করে। এই পয়েন্টারগুলিকে জাম্প পয়েন্টার বলা হয় কারণ তারা গাছের শিকড়ের দিকে লাফ দেয়। একটি গাছের প্রদত্ত নোড ভি-এর জন্য, অ্যালগরিদম দৈর্ঘ্যের জাম্পারগুলির একটি অ্যারে সংরক্ষণ করে। এই অ্যারের ith উপাদানটি v এর 2th পূর্বপুরুষকে নির্দেশ করে। এই ধরনের তথ্য কাঠামো ব্যবহার করা আমাদের যে কোনও প্রদত্ত নোড থেকে গাছের অর্ধেক উপরে লাফিয়ে উঠতে সহায়তা করে। যখন অ্যালগরিদমকে একটি প্রশ্ন প্রক্রিয়া করতে বলা হয়, তখন আমরা বারবার এই পয়েন্টারগুলি ব্যবহার করে গাছের উপরে লাফিয়ে উঠি। লাফ দেওয়ার সংখ্যা সর্বাধিক লগ এন হবে এবং তাই প্রশ্নের উত্তর লগ এন সময়ে দেওয়া যেতে পারে। ল্যাডার অ্যালগরিদম ল্যাডার অ্যালগরিদম একটি গাছকে পথের সংগ্রহে সরল করার ধারণার উপর ভিত্তি করে তৈরি। এর কারণ হ 'ল পূর্বপুরুষদের প্রশ্নের ক্ষেত্রে পথগুলি জিজ্ঞাসা করা সহজ। একটি নোড r-এ শিকড়যুক্ত n নোডের সমন্বয়ে গঠিত একটি পথ P বিবেচনা করুন। আমরা পথটিকে ল্যাডার নামক আকারের n-এর একটি অ্যারেতে সংরক্ষণ করতে পারি এবং গভীরতা (v) ≤ d হলে ল্যাডার [d] ফেরত দিয়ে আমরা দ্রুত এল. এ (v, d)-এর একটি স্তরের পূর্বপুরুষ প্রশ্নের উত্তর দিতে পারি। এটি ও (1) নেবে। তবে, এটি তখনই কাজ করবে যখন প্রদত্ত গাছটি একটি পথ হবে। অন্যথায়, আমাদের এটিকে পথে বিভক্ত করতে হবে। এটি দুটি পর্যায়ে করা হয়ঃ দীর্ঘ পথের পচন এবং দীর্ঘ পথগুলিকে সিঁড়িতে প্রসারিত করা। পর্যায় 1: দীর্ঘ-পথ পচন এটি একটি পুনরাবৃত্তিমূলক পদ্ধতি যা একটি প্রদত্ত গাছকে পথে বিভক্ত করে। এই পর্যায়গুলি গাছের মূল থেকে পাতার দীর্ঘতম পথ খুঁজে বের করার মাধ্যমে শুরু হয়। এরপরে এটি গাছ থেকে তার বন্ধন ভেঙে এই পথটি সরিয়ে দেয় যা অবশিষ্ট গাছটিকে উপ-গাছে ভেঙে দেবে এবং তারপরে এটি প্রতিটি উপ-গাছকে পুনরাবৃত্তিমূলকভাবে প্রক্রিয়া করবে। প্রতিবার যখন কোনও পথ বিচ্ছিন্ন হয়, তখন মূল থেকে পাতা পর্যন্ত পথের উপাদানগুলি ধারণ করে এমন পথের সাথে একটি অ্যারে তৈরি করা হয়। এই পুনরাবৃত্তির মূল বিষয়টি হল যখন গাছটি একটি পথ হয় যেখানে তার অপসারণ একটি খালি গ্রাফ ছেড়ে যায়। প্রতিটি শীর্ষ ভি-এর একটি অনন্য মই থাকে যা এটি ধারণকারী মই এবং আমরা এটিকে "ভি-এর মই" বলি। তবে, এই প্রাক-প্রক্রিয়াকরণ পর্যায়ের পরে, প্রশ্নের দ্রুত উত্তর দেওয়া যায় না। প্রকৃতপক্ষে একটি স্তরের পূর্বপুরুষের প্রশ্নের উত্তর দেওয়ার জন্য, অ্যালগরিদমটিকে একটি পথ থেকে অন্য পথে ঝাঁপিয়ে পড়তে হবে যতক্ষণ না এটি মূলে পৌঁছায় এবং একটি পাতা-থেকে-মূল পথে এই ধরনের পথের ≤ () থাকতে পারে। এটি আমাদের এমন একটি অ্যালগরিদমের দিকে নিয়ে যায় যা গাছটিকে ও (এন) সময়ে প্রাক-প্রক্রিয়া করতে পারে এবং ও ()-এ প্রশ্নের উত্তর দিতে পারে। সর্বোত্তম অনুসন্ধানের সময়ে পৌঁছানোর জন্য, আমাদের নীচে বর্ণিত দ্বিতীয় পর্যায়ে ফলাফলগুলি প্রক্রিয়া করতে হবে। পর্যায় 2: দীর্ঘ পথগুলিকে সিঁড়িতে প্রসারিত করা অ্যালগরিদমের প্রথম পর্যায়টি গাছটিকে বেশ কয়েকটি বিচ্ছিন্ন পথে বিভক্ত করে। অ্যালগরিদমের দ্বিতীয় পর্যায়ে, প্রতিটি পথ প্রসারিত করা হয় এবং তাই ফলস্বরূপ পথগুলি পারস্পরিক একচেটিয়া হবে না। অ্যালগরিদমের প্রথম পর্যায়ে, প্রতিটি পথ এইচ 'আকারের একটি অ্যারের সাথে যুক্ত। আমরা একই অ্যারেতে পথের শীর্ষে এইচ 'তাৎক্ষণিক পূর্বপুরুষদের যুক্ত করে এই পথটি প্রসারিত করি। এটি প্রতিটি অ্যারেকে তার মূল আকারের দ্বিগুণ প্রসারিত করবে যার ফলে সমস্ত সিঁড়িতে মোট 2n সংখ্যক নোড থাকবে। লক্ষ্য করুন যে সিঁড়ির সংখ্যা পরিবর্তিত হয় না এবং প্রতিটি নোডের মই একই থাকে। যদিও একটি নোড ভি এখন একাধিক পথে তালিকাভুক্ত করা যেতে পারে তবে এর মইটি অ্যালগরিদমের প্রথম পর্যায়ে ভি-এর সাথে যুক্ত ছিল। এই দুটি পর্যায় ও (এন)-এ প্রক্রিয়া হতে পারে তবে অনুসন্ধানের সময় এখনও স্থির নয়। এইচ উচ্চতার একটি নোডের উপর একটি স্তরের পূর্বপুরুষের প্রশ্ন বিবেচনা করুন। ইউ এর মইয়ের শীর্ষে ভ্রমণ করার মাধ্যমে, কমপক্ষে 2 ঘন্টা উচ্চতার একটি শীর্ষে পৌঁছানো হবে। লক্ষ্য করুন যে সমস্ত নোডের উচ্চতা কমপক্ষে 1 এবং তাই এই i বার করার পরে, আমরা কমপক্ষে 2i উচ্চতার একটি নোডে পৌঁছাই এবং তাই আমাদের সর্বাধিক লগ n বার এটি করতে হবে। এটি আমাদের ও (লগ এন)-এর একটি অনুসন্ধানের সময় দেয়। পর্যায় 3: দুটি পদ্ধতির সংমিশ্রণ দেখা যাচ্ছে যে মইয়ের অ্যালগরিদম নিজেই কৌশলটি করে না। প্রকৃতপক্ষে জাম্প পয়েন্টার অ্যালগরিদম এবং ল্যাডার অ্যালগরিদম একে অপরের পরিপূরক। দুটি অ্যালগরিদম বিপরীত দিকে কাজ করেঃ জাম্প পয়েন্টার অ্যালগরিদম হপগুলিকে দ্রুত হ্রাস করে এবং ল্যাডার অ্যালগরিদম হপগুলিকে দ্রুত বৃদ্ধি করে। দুটি অ্যালগরিদমের সংমিশ্রণ ও (1) সময়ে প্রশ্নের উত্তর দিতে পারে। একটি একক লাফ পয়েন্টার যে কোনও প্রশ্ন কমপক্ষে গাছের অর্ধেক উপরে নিয়ে যায় যার পরে কেবল একটি সিঁড়ি আরোহণ প্রশ্নের উত্তর দেবে। এর ফলে ও (এন লগ এন) প্রাক-প্রক্রিয়াকরণ সময় এবং ও (1) অনুসন্ধানের সময় হয়। চার রাশিয়ান পদ্ধতির প্রয়োগের মাধ্যমে প্রাক-প্রক্রিয়াকরণকে আরও ও (এন) সময়ে হ্রাস করা যেতে পারে, যেখানে গাছটিকে রৈখিক প্রাক প্রক্রিয়াকরণ সহ একটি ছোট গাছে পরিণত করা হয় এবং খুব ছোট গাছের সংগ্রহ, যা এতটাই ছোট যে সমস্ত গাছের একটি সম্পূর্ণ গণনা এবং সেই গাছগুলির প্রাক প্রক্রিয়াকরণ এখনও ও (এন) সময়। আকারের গাছ (লগ এন)/4 যথেষ্ট। বার্কম্যান এবং ভিশকিনের সমাধান একটি ভিন্ন সমাধান বার্কম্যান এবং ভিশকিনের কারণে। এই সমাধানটি গাছ প্রক্রিয়াকরণের জন্য অয়লার ট্যুর কৌশলের উপর ভিত্তি করে তৈরি। প্রধান পর্যবেক্ষণটি হল যে এলএ (ভি, ডি) হল গভীরতা ডি-এর প্রথম নোড যা ভি-এর শেষ উপস্থিতির পরে অয়লার সফরে প্রদর্শিত হয়। সুতরাং, অয়লার সফর এবং গভীরতার উপর সম্পর্কিত তথ্য তৈরি করে, সমস্যাটি অ্যারেতে একটি অনুসন্ধানে হ্রাস করা হয়, যার নাম ফাইন্ড স্মলার (এফএস)। একটি অ্যারের জন্য, এবং একটি বৈধ সূচক i, FS (i, x) প্রথম সূচক j> i এমনভাবে প্রদান করে যে A [i] <x (এখানে, আমরা x = d + 1 ব্যবহার করি)। এফএস সমস্যার একটি কার্যকর সমাধান সাধারণভাবে কঠিন, তবে ইউলার ট্যুর থেকে উদ্ভূত বিশেষ ক্ষেত্রে সহজ; এই ক্ষেত্রে, সংলগ্ন উপাদানগুলি ±1 দ্বারা পৃথক হয়। এই ধারণাটি ও (এন লগ এন) জটিলতার একটি প্রাক প্রক্রিয়াকরণ অ্যালগরিদম সহ ও (1) অনুসন্ধানের সময় দেয়। ফোর রাশিয়ান পদ্ধতির প্রয়োগের মাধ্যমে প্রাক প্রক্রিয়াকরণের সময়কে ও (এন)-এ উন্নীত করা হয়। আরও দেখুন রেঞ্জ কোয়েরি (কম্পিউটার বিজ্ঞান) সর্বনিম্ন সাধারণ পূর্বপুরুষ রেফারেন্স তাত্ত্বিক কম্পিউটার বিজ্ঞান গাছ (গ্রাফ তত্ত্ব)