N Puzzle Problem – part 2

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

আগের পর্বে আমরা পাযল এর solvable state নিয়ে কথা বলেছি। এখন আমরা দেখবো কিভাবে আগালে আমরা সহজে পাযল প্রব্লেম সল্ভ করতে পারি।

ছবিটি হল একটি ৮-পাযল এর স্টেট কিভাবে জেনারেট হবে তার একটি স্যাম্পল।

ডি এফ এস ( Depth First Search )

আমরা এটি সল্ভ এর জন্য প্রথমেই ভাবতে পারি ডি এফ এস (Depth_First_Search) এর কথা। এরজন্য আমরা একেকটি স্টেট থেকে সবচেয়ে ডীপ এ যাওয়ার চেষ্টা করবো। যদি আর কোন স্টেট এ না যেতে পারি, তাহলে আবার রিকার্সিভলি ব্যাক করে ফিরে আসবো। কিন্তু এর একটি বড় সমস্যা হল, আমাদের এই নোড জেনারেট এর ব্যাপারটি আমাদের ফাইনাল স্টেট থেকে অনেক অনেক দূরে নিয়ে যেতে পারে, যার কারনে আমরা এক্সপেক্টেড সলুশন পাবোতো নাই, উলটো আমাদের প্রোগ্রাম মেমরি ধারন করতে না পারার কারনে ক্র্যাশ করার সল্ভাবনা অনেক বেশি। কাজেই ডি এফ এস নরমালি করতে গেলে আমাদের জন্য তা সুবিধার হবেনা।

বি এফ এস ( Breadth First Search )

আমরা বি এফ এস এর মাধ্যমেও কাজ করতে গেলে সেইম আগের মতন প্রবলেম এ পরবো। অর্থাৎ BFS & DFS সেইম টাইপ নোড জেনারেট করবে। আমাদের তাই কিছু ট্রিক কাজে লাগাতে হবে যাতে অপটিমাল সলুশন পাওয়া যায়।
যাদের বি এফ এস, ডি এফ এস সম্পর্কে জানা নেই, তারা শাফায়েত ভাই এর ব্লগ থেকে দেখে নিতে পারো।

বি এফ এস
ডি এফ এস

একটি ছোট উদাহরন দেই। ধরি আমি পিযা ডেলিভারি দিবো একটি ১০ তলা বিল্ডিং এ। বিল্ডিং এর প্রতি তলায় আবার ১০ টি করে রুম আছে। একদিন কোন এক কারনে এলাকার মেয়র ঘোষনা দিল যে আজকে এই বিল্ডিং এর সবাইকে পিযা খাওয়ানো হবে । পুরো বিল্ডিং এ পিযা সার্ভের দায়িত্ব পরলো আমার ঘাড়ে -_- । এখন আমার কাছে ২ টি অপশন আছে। আমি প্রথেম ১ তলার সব রুম এ পিযা ডেলিভারি দিলাম, এরপরে ২ তলার সব রুম, এরপরে ৩ তলা... এভাবে ১০ তলা পর্যন্ত ডেলিভারি শেষ করলাম। আরেক কাজ করতে পারি যে, আমি প্রথমে ১ তলার একটি রুম এ পিযা দিয়ে ২ তলায় চলে গেলাম, সেখানের হাতের সবচেয়ে কাছের রুম এ পিযা দিয়ে আবার ৩ তলায়... এভাবে ১০ তলায় দেয়ার পরে আবার ১ তলায় নেমে পরর রুম থেকে একই ভাবে ডেলিভারি শুরু করলাম। এই ২ কাজের মধ্যে প্রথমটি হচ্ছে বি এফ এস, এবং পরেরটি হল ডি এফ এস। আশা করি কোনরকম আইডিয়া তোমরা পেয়েছো।
এখন আমরা কাজের কথায় আসি। আমরা ৮-পাযল সল্ভের ক্ষেত্রে আমাদের জন্য reachable state হল 9! / 2 = 1,81,440। এই ব্যাপারটি কিভাবে আসলো তা এখানে আলোচনা করছিনা। ১৫-পাযল এর জন্য এই মান 16! / 2 = 10,461,394,944,000 । বুঝতেই পারছো, ৮-পাযল শুধুমাত্র ব্রুটফোর্স দিয়ে করা গেলেও, ১৫ এর ক্ষেত্রে এটি সম্ভব না। এজন্য আমাদের লাগবে A* ( এ স্টার ) সার্চ বা ইটারেটিভ ডিপেনিং সার্চ ( Iterative Deepening A* Search or IDA* search )।
আমরা এখানে ডি এফ এস, বি এফ এস স্টাইল এর কাজ করবো, কিন্তু একটু আলাদাভাবে। আমরা একটি ফাংশন নিবো

f  ( n ) = g ( n ) + h ( n ), যেখানে,
f  ( n ) = n তম স্টেট এর ভ্যালু ( cost ) ।
g ( n ) = ইনিশিয়াল স্টেট থেকে  n তম স্টেট পর্যন্ত দূরত্ব।
h ( n ) = হিউরিস্টিক জেনারেশন এর জন্য একটি ফাংশন।

হিউরিস্টিক হল এমন একটি টেকনিক, যা আমাদের অপটিমাল সলুশন খুঁজে বের করতে সাহায্য করে। আমাদের পাযল সল্ভিং এর ক্ষেত্রে A* সার্চে আমরা এই হিউরিস্টিক ব্যবহার করবো। সহজ কথায়, এটি সিম্পল একটি ভ্যালু যা প্রতিটি স্টেট এর জন্য বের করে আমরা আমাদের সুবিধামত সামনে এগিয়ে যাবো।
ছবিটিতে আমরা দেখতে পাচ্ছি যে, ইনিশিয়াল স্টেট থেকে ৪ টি নতুন স্টেট জেনারেট হয়েছে। আমরা A* সার্রচের জন্য এই প্রতিটি চাইল্ড স্টেট এর হিউরিস্টিক ভ্যালু বের করবো। এরমধ্যে যেই ভ্যালু সবার চেয়ে কম, আমরা সেই চাইল্ড কে পরবর্তী স্টেট এর জন্য এক্সপান্ড ( Expand or Branching; creating next child for further calculation ) করবো।

হিউরিস্টিক ব্যবহারের সুবিধা ঃ

অপটিমাল সলুশন সহজে স্বল্প সময়ের মধ্যে বের করে নিয়ে আসা যায়,  এবং অপ্রয়োজনীয় নোড মেরে ফেলে ( removal of unnecessary nodes )।

Coding:

এখন আমরা আলোচনা করবো কোডিং নিয়ে। প্রথমেই আমরা ইনিশিয়াল স্টেট থেকে নোড এক্সপান্ড করবো। এখন যেকোন একটি হিউরিস্টিক ফাংশন আমরা ব্যবহার করবো। ইনিশিয়াল স্টেট এ g ( n ) = 0। এই স্টেট এর জন্য আমরা h ( n ) , f ( n ) বের করবো। আমরা এই প্যারেন্ট কে এক্সপান্ড করে কতগুলি চাইল্ড নোড পাবো। এবার কাজ হচ্ছে প্রতিটি চাইল্ড নোড এর জন্য আমরা f ( n ) বের করবো। এবং এর মধ্যে সবচেয়ে কম যার মান, আমরা সেটি নিয়ে সামনে এগিয়ে যাবো। এই সামনে এগিয়ে যাওয়ার মানে হচ্ছে একটি কিউ তে আমরা স্টেট গুলি জমা রাখবো। এখন আমরা এভাবে একটি স্ট্রাকচার ডিক্লার করতে পারি-->

struct node
{
int grid [ N ] [ N ] ;            // 2D grid to save the state
int h_val;                            // heuristic value of the state
char parent ;                     // parent =  { 'U', 'D', 'L', 'R' }
};

এখানে grid ২ডি অ্যাারেতে আমরা আমাদের পাযল এর স্টেট এর ভ্যালুগুলি রাখবো। h_val এর মাঝে থাকবে এই গ্রিড এর জন্য জেনারেট করা হিউরিস্টিক ভ্যালু। parent ভ্যারিয়েবল এর মাঝে আমরা প্যারেন্ট স্টেট থেকে কোন মুভ এ এই স্টেট এ এসেছি সেটি সেভ রাখবো। (এ ব্যাপারটি আমাদের জানা থাকলে ব্যাকট্র্যাক এর ক্ষেত্রে সুবিধা হবে)
এখন আমাদের একটি কিউ লাগবে যেখানে এই নোডগুলি রাখবো আমরা। শুরুতে আমরা কিউ তে আমাদের ইনিশিয়াল স্টেট এর যে পাযল দেয়া আছে তা রাখবো। এরপরে আমরা কিউ থেকে এই নোড পপ করে এর চাইল্ড জেনারেট করবো। এখন চাইল্ড জেনারেট এর সাথে সাথে আমরা প্রত্যেক চাইল্ডের হিউরিস্টিক ও জেনারেট করবো। এরপরে আমরা এই হিউরিস্টিক এর মধ্যে যার মান কম, সেই চাইল্ডকে কিউ তে পুশ করবো। এখন নরমাল বি এফ এস এ আমরা কিন্তু সব চাইল্ড ই পুশ করতাম। এখানেও তা করা যাবে, কিন্তু ১৫-পাযল এর ক্ষেত্রে খুব কষ্টকর হবে ব্যাপারগুলি ঠিকমত হিসাব নিকাশ করা। কারন, মেমরি, টাইম কমপ্লেক্সিটি এর ব্যাপারগুলি আমাদের মাথায় রাখা লাগবে। আর যেহেতু আমরা A* সার্চ ব্যবহার করছি, আমাদের অপ্রয়োজনীয় চাইল্ড নোড জেনারেট না করাই উত্তম। যখন দরকার হবে আমরা তখন জেনারেট করবো। নিচের ছবিটি খেয়াল করি ঃ

ইনিশিয়াল স্টেট টি থেকে আমরা ৩ টি চাইল্ড নোড পেলাম। এদের f ( n ) বের করলাম। এবং এরমধ্যে সবচেয়ে কম যার মান, তাকে আমরা পরবর্তীতে কিউ তে পুশ করবো। এখন যেহেতু আমরা কিউ তে বাকি ২ টি নোড পুশ করছিনা, কাজেই আমাদের মেমরি স্পেস এক্ষেত্রে অনেক বেঁচে যাবে। কিউ তে চাইল্ড নোডটি পুশ এর সময় আমরা parent ভ্যারিয়েবল এর মধ্যে 'L' ক্যারেক্টারটি রাখবো, কারন 4 কে Left এ নেয়ার মাধ্যমে আমরা এই চাইল্ড নোডটি পেয়েছি। আমরা বলেছিলাম যে আমাদের এই ভ্যারিয়েবল এর মান ব্যাকট্র্যাকিং এর কাজে লাগবে। আমরা সেটি এখন আলোচনা করবো। আশা করি, এ পর্যন্ত সবকিছু বুঝে গেছো। এখন ধরি আমাদের প্যারেন্ট নোডের f এর মান এর চেয়ে প্রতিটি চাইল্ড নোডের f এর মান বেশি আসলো। এখন আমরা যেই চাইল্ড ই নেই না কেনো, ব্যাপারটি কিন্তু আসলে খারাপ হবে, কারন কম f এর মান থেকে আমরা আবার বেশি মানের দিকে আগাচ্ছি। আমাদের মেইন টার্গেট হচ্ছে যত কম মুভ এ পাযল সল্ভ করা যাএ, অর্থাৎ আমাদের f এর মান কমাতে হবে। এখন যদি এরকম অবস্থা হয়, তখন আমাদের সেই চাইল্ড নোড থেকে আবার প্যারেন্ট এ ব্যাক করতে হবে।

এখন আমাদের কাছে তো বর্তমান নোড ছাড়া আর কোন নোড নেই, তাহলে কিভাবে প্যারেন্ট এ ব্যাক করবো? এরজন্য আমাদের তখন দেখতে হবে parent ভ্যারিয়েবল এর মধ্যে কি আছে।যা থাকবে তার বিপরীত স্টেট দিয়ে ব্যাক মুভ করলে আমরা আমাদের প্যারেন্টকে আবার পাবো। মানে যদি ভ্যারিয়েবল এ থাকে 'L', তাহলে আমাদের 'Right' মুভ করতে হবে আগের স্টেট পাওয়ার জন্য। এখন আগের স্টেট পাবার পরে আবার আমরা সব চাইল্ড জেনারেট করবো। এখন যেই চাইল্ড আগে নিয়েছিলাম, সেটি না নিয়ে, তার ঠিক পরের হিউরিস্টিক মান অনুযায়ী আমরা চাইল্ড নিবো।

ধরি আমাদের ইনিশিয়াল স্টেট এ f = 45। এর ৩ টি চাইল্ড জেনারেট করি।

৩ টি চাইল্ডের মধ্যে f = 42 আমরা সিলেক্ট করবো এবং একে কিউ তে পুশ করে এক্সপান্ড করবো।

এখন খেয়াল করে দেখি যে, আমরা নতুন যে ৩ টি চাইল্ড পেলাম, তাদের প্রত্যেকের  f এর মান প্যারেন্ট এর f এর মান থেকে বেশি। কাজেই আমাদের এই নোড এক্সপান্ড করা আসলে ঠিক হয়নি। তাই আমাদের ব্যাকট্র্যাক করতে হবে।

ব্যাকট্র্যাক করে আগের অবস্থায় ফিরে আসলাম। এখন আমরা নিবো f = 43  কারন, আগের f এর মানের ঠিক পরবর্তী মান এটি।

এবার আমরা এই নোডকে এক্সপান্ড করে নতুন চাইল্ড পেলাম, যার মধ্যে একটির f এর মান 41, যা আগের তুলনায় ভালো মান আমাদের প্রব্লেম সল্ভিং এর জন্য। তাই আমরা এখন এটি নিয়ে কাজ করবো।
এই ছিল আসলে ব্যাসিক কোডিং এর হিন্টস। একেকজনের কোডিং স্টাইল অনুযায়ী কোডের আইডিয়া চেঞ্জ হবে, আরো বেটার আইডিয়া আসবে। পরবর্তী পর্বে আমরা দেখবো এই সার্চিং এর মধ্যে কিছু অপটিমাইজেশন আনা যায় কিনা।

পরবর্তী পর্ব : part - 3