N Puzzle Problem – part 3

আগের পর্ব এখানে ঃ part - 1 , part - 2

মেমরি স্পেস ( Memory Space )

আমরা আমাদের মেমরি স্পেস কমানোর জন্য স্ট্রাকচারকে একটু মডিফাই করতে পারি। আমরা একটি স্ট্রিং এর মধ্যে আমাদের প্রতি স্টেট এর প্রয়োজনীয় সব জিনিস সেইভ রাখতে পারি।

যেমন চিত্রের পাযলটির জন্য আমরা ২ডি অ্যাারে তে ভ্যালুগুলি না রেখে একটি স্ট্রিং এ এভাবে রাখতে পারি ঃ string a = "123046758" । এর মাধ্যমে আমরা পরে এটিকে ইচ্ছা করলে ২ডি গ্রিড এ কনভার্ট করে আমাদের কাজ করতে পারি। এখন আমরা আমাদের প্যারেন্ট ও এভাবে স্ট্রিং এর শেষে অ্যাড করে দিতে পারি। যেমন ঃ a = "123046758L" , এর মানে হচ্ছে এই স্টেট টি Left মুভ দেয়ার পরে আমরা পেয়েছি। আর আমাদের বাকি হিউরিস্টিক ভ্যালু সেইভ। এটাও আমরা একই ভাবে করতে পারি। ব্যাপারটা তোমাদের উপর ছেড়ে দিলাম। এখন আমরা একটি ম্যাপ রাখবো এরকম ঃ map < string, bool > visited;
এই ম্যাপ এর কাজ হচ্ছে আমাদের স্টেট গুলি চেক এ রাখা। মানে একই স্টেট এ যেনো আমরা আবার ফিরে না আশি। এর একটি সুবিধা হল আমাদের অপ্রয়োজনীয় বারতি স্টেট সেইভ রাখা লাগবেনা। আমরা একবার ভিজিটেড কোন স্টেট আবার পেয়েছি কিনা, এটা ম্যাপ এর মাধ্যমে এভাবে চেক করতে পারবো। আরো একটি কাজ আমরা করবো যে, যদি unsolvable state কখনো চলে আসে, তাহলে আমরা তাকে মার্ক করে রাখবো যে এটি বাজে স্টেট, এখানে আসলে সামনে আর একে এক্সপান্ড এর কোন প্রয়োজন নেই। আর আমরা কিউ তে একের বেশি স্টেট কখনো রাখছি না, কাজেই আমাদের মেমরি বেড়ে গিয়ে রান টাইম এরর খাওয়ার সম্ভাবনা কম।

টাইম কমপ্লেক্সিটি ( Time Complexity )

বি এফ এস, ডি এফ এস এর জন্য আমাদের টাইম কমপ্লেক্সিটি হবে O ( b^d ) । এখানে,
b = branching factor ( একটি নোড থেকে সর্বোচ্চ যে কয়টি চাইল্ড নোড জেনারেট হতে পারে, আমাদের পাযল এর ক্ষেত্রে সর্বোচ্চ ৪ টি হতে পারে {উপরে, নিচে, ডানে, বামে} )।
d = depth ( আমাদের নোড জেনারেটের সর্বোচ্চ লেভেল, )

ইটারেটিভ ডিপেনিং সার্চ এর জন্য হবে O ( bd ), O ( b^d ) এর পরিবর্তে। অর্থাৎ আমরা ডি এফ এস মত এগিয়ে যাবো এবং যখন দরকার হবে তখন আমরা নতুন চাইল্ড তৈরী করবো।

A* সার্চ সম্পর্কে জানার জন্য এখানে দেখতে পারো ঃ A* search