গ্রাফ সার্চ নিয়ে কচকচানো শুরু করার কারণ আমি বেশ কয়েকদিন আগে একটি অ্যাপ এর কাজে এটি ব্যবহার করেছিলাম। ভাবলাম লিখে ফেলা উচিত, তাই শুরু করলাম। লেখাটা পড়ার আগে আপনার যা যা জানা থাকলে ভালো তা হচ্ছে।

1. বেসিক গ্রাফ (http://en.wikipedia.org/wiki/Graph_%28mathematics%29)
2. গ্রাফ ট্রাভের্সাল (http://en.wikipedia.org/wiki/Graph_traversal)

গ্রাফ সার্চের অসংখ্য মেথডের মধ্যে এ* সার্চ বেশ পরিচিত হবার কারণ এটি অনেক জায়গায় বিশাল কানেক্টেড একটি গ্রাফ এর এক প্রান্ত থেকে অন্য প্রান্তে যাবার রাস্তা খুঁজে বের করার জন্যে ব্যবহৃত হয়। যেসব জায়গায় এটি সবচেয়ে বেশি ব্যবহৃত হয় তা হচ্ছে:

1. রুবিক কিউব সলভ করার জন্যে
2. ম্যাপ এ রাউট সার্চ করার জন্যে
3. রোবট নেভিগেশন রাউট বের করার জন্যে
4. কোন গেইম এ পাথ, রাউট সার্চ করার জন্যে

অন্য সব অ্যালগরিদম থেকে এটির ব্যবহার এতো বেশি হবার কারণ এটি শুরু এবং শেষের নোড খোঁজার জন্যে শুরু এবং শেষের নোড এর আশেপাশের নোড গুলো থেকে শুরু করে। অন্য একটি কারণ হচ্ছে এ* সার্চ শুধুমাত্র একটি নোড হতে অন্য নোডের দূরত্ব (cost) ছাড়াও একটি অনুমেয় দূরত্ব(Heuristic cost) ব্যবহার করে।

যদি এখনো পর্যন্ত যা বলছি তা কঠিন লাগে তাহলে আসুন একটি বাস্তব উদাহরণ এ চলে যাই।

আমরা প্রথমে শুরু করছি একটি গ্রাফ দিয়ে। ধরে নেই আমাদের গ্রাফটি দেখতে এরকম:

সহজ বাংলায় এখানে একটি ছোট গ্রাফ আছে যার নোডসংখ্যা ৫ টি এবং কোন নোড থেকে অন্যান্য নোড এ যাবার cost নোড গুলোর edge এ লেখা। যেমন S থেকে A  যাবার জন্যে Cost 1. A থেকে G তে যাবার Cost হচ্ছে ১২. অন্যান্য সকল গ্রাফ সার্চিং অ্যালগরিদম এর মতো শুধুমাত্র path cost এর উপর এটি নির্ভর করেনা। আপনার ঠিক এর পর যেটি দরকার হবে সেটি হচ্ছে একটি Heuristic Cost . এখন প্রশ্ন আসতেই পারে কিভাবে Heuristic Cost আমরা ঠিক করবো। এই ক্ষেত্রে আমরা আমাদের এক নোড থেকে অন্য নোডের Expected Cost বসিয়ে নিয়েছি। তবে আপনি চাইলে এই Heuristic Cost ও নির্ণয় করার পদ্ধতিগুলো পরীক্ষা করতে পারেন। আমরা সেগুলো পরবর্তী কোন টিউটোরিয়াল এ দেখবো।

আসুন ধরে নেই আমাদের Heuristic Cost Table এরকম:

আমাদের শুরু করবার নোড হবে S এবং শেষ করবার নোড হবে G। আসুন দেখি এ* সার্চ কিভাবে সঠিক পথ টি খুঁজে বের করে। আমরা একটি priority queue ব্যবহার করবো এ ক্ষেত্রে। আপনি যদি Priority Queue কি না জেনে থাকেন, অনুগ্রহ করে জেনে নিন এখান থেকে।

মনে করি লিস্টটির নাম Closed List, এটির ব্যবহার ব্যাখ্যা করার থেকে দেখে নেয়াটাই বুদ্ধিমানের কাজ হবে। অাপাতত জেনে রাখুন এটি একটি লিস্ট। আমাদের শুরু করার নোড হচ্ছে S , আমরা যেতে চাই G তে। আসুন দেখি, আমরা কিভাবে সেটি করতে পারি। প্রথমে নেই S কে। S এর সাথে Attached Node হচ্ছে A এবং B। তাহলে S থেকে G তে যেতে হলে আগে আমাকে A অথবা B তে যেতে হবে। তার মানে হচ্ছে যে নোড টি থেকে আপনি শুরু করবেন তার সাথে সংযুক্ত সকল নোড কে আপনার আগে বিবেচনায় আনতে হবে অথবা node টি expand করতে হবে।

সবার শুরুতে S এর Total Cost হিসেব করি:

c(s) = g(s) + h(s)

এখানে g(s) হচ্ছে S এ আসার Cost. S এ আসতে আমার তেমন কোন খরচ হয়নি বিধায় আমি এটিকে ধরে নিচ্ছি শূন্য। এবং h(s) হচ্ছে S এর heuristic cost যেটা আমরা table থেকে দেখে পাচ্ছি 7. এখন আমাদের কাজ হচ্ছে S এর সাথে সংযুক্ত সকল নোড বিবেচনায় আনা, মানে S expand করা। S কে expand করলে আমরা পাই A এবং B ।

c(s) = 0 + 7

মনে করি শুরুতে আমরা A তে যাবো।

এখন S হতে A তে যাবার Cost নির্ণয় করার উপায় হচ্ছে S থেকে A তে যাবার Cost এবং A এর Heuristic Cost যোগ করা। মনে করি:

c(S-A) = ( g(s)+g(a) ) + h(a)

এখানে c(S-A) হচ্ছে S হতে A তে যাবার Total Cost. g(s) হচ্ছে s এ আসার Cost. এখানে যেটি শুন্য। কারণ, s থেকে আমরা শুরু করছি। A তে যাবার Cost হচ্ছে 1. A এর Heuristic Cost হচ্ছে 6. তাহলে সম্পূর্ণ Cost দাঁড়ায়:

c(S-A) = ( 0+ 1 ) + 6 =7

অনুরূপ ভাবে S হতে B যাবার পর Cost দাঁড়ায়

c(S-B) = ( 0+ 4 ) + 4 =8

কারণ, s এ আসতে 0 এবং B আসতে 4 এবং B এর heuristic cost হলো 4 . এখন আমাদের অবস্থা নিচের মতো:

খেয়াল করলে দেখবেন, এখানে closed_list নামে একটি queue আছে। আমরা যখনি কোন নোড পুরোপুরি expand করে ফেলবো তখনি সেটিকে এখানে নিয়ে নেবো, যাতে পরে এটিকে Expand না করা লাগে। তাই আমরা এখানে S এর সব attached node (A, B) ভিসিট করে ফেলেছি বলে S কে closed_list এ রেখে দিয়েছি। আর ডান পাশে যে Tree টি তৈরী হচ্ছে তাকে বলবো আমরা Search Tree.

এখন যেহেতু A এবং B ভিসিট করা শেষ, আমাদের পরবর্তী টার্গেট A অথবা B expand করা। A এবং B এর মধ্যে কোনটি আগে করবো? যার Total cost কম তারটি আগে। এখানে A এর Total Cost 7 যেখানে B তে আসার Total Cost হচ্ছে 8, তাই এটি আগে expand করবো। A হতে শুধু B,C,G তে যাওয়া যায়। তাই ৩ টি পথের ই Total Cost বের করতে হবে। তাই Total Cost হবে:

c(S-A-B) = ( g(s)+g(b)+g(c) ) + h(c)

c(S-A-B) = ( 0+1+2) +4 = 7

অনুরূপভাবে,

c(S-A-C) = (0+1+5) + 2 = 8

c(S-A-G) = (0+1+12) + 0 = 13

যেহেতু A নোডটি আমাদের expand করা শেষ সেহেতু আমি A কে closed_list এ পাঠিয়ৈ দিবো। এখন সার্চ ট্রি এর দিকে লক্ষ্য করুন। প্রশ্ন হচ্ছে কোনটি আপনি expand করবেন? ট্রি এর সকল Leaf Node গুলো খেয়াল করুন (যেগুলো এখনো expand হয়নি)। নোডগুলো হচ্ছে:

1. s-a-b
2. s-a-c
3. s-a-g
4. s-b

এখন এর মধ্যে সবচেয়ে কম Total Cost হচ্ছে s-a-b এর। এটি এখন expand করতে হবে।

s-a-b এর শেষ নোড b, তাহলে b expand করি। b থেকে শুধু c তে যাওয়া যায় ।

c(s-a-b-c) = (g(s) + g(a) + g(b) + g(c)) + h(c)

c(s-a-b-c) = (0+1+2+2) + 2 = 7

যেহেতু B নোডটি আমাদের expand করা শেষ সেহেতু আমি B কে closed_list এ পাঠিয়ৈ দিবো।

এখন আমাদের Leaf Node (ট্রি এর তলার নোড গুলো যেগুলো এক্সপান্ড করা হয়নি) সেগুলো হচ্ছে

1. s-a-b-c
2. s-a-g
3. s-a-c
4. s-b

যেহেতু s-a-b-c এর Total Cost কম সেহেতু আমরা এটিই expand করবো, মানে এটির শেষ নোড c expand করবো। c থেকে শুধু g তে যাওয়া যায়। তাহলে s-a-b-c-g এর total cost হচ্ছে

c(s-a-b-c-g) = (g(s) + g(a) + g(b) + g(c) + g(g) ) + h(g)

c(s-a-b-c-g) = (0+1+2+2+3) + 0 = 8

আমরা C কেও closed_list এ ঢুকিয়ে দেবো কারণ, এটি expanded হয়ে গেছে।

এখন খেয়াল করলে দেখবেন আমাদের expand করার মতো path এবং তাদের Total Cost হচ্ছে:

1. s-a-b-c-g = 8
2. s-a-c = 8
3. s-a-g = 13
4. s-b = 8

এখানে s-a-b-c-g এবং s-a-c এবং s-b এর Total cost এক ই। এখন কোনটি expand করবো?

এখন আমাদের সমস্যা সমাধান করার জন্যে খেয়াল করে দেখুন alphabetically dictionary sort এ s-a-b-c-g আগে আসে, এরপর আসে s-a-c এবং তার পরে s-b

তাহলে s-a-b-c-g expand করা উচিত। কিন্তু এটি g তে চলে এসেছে এবং এখানেই আমরা আসতে চেয়েছিলাম। তাই, এই s-a-b-c-g ই আমাদের খুঁজতে থাকা পথ।তার মানে হচ্ছে আপনার এ* সার্চ এ যদি এক্সপান্ড করতে যে নোডটি সিলেক্ট হবে সেটিই যদি গোল নোড হয়, আপনি আপনার পথ পেয়ে গেছেন।

এটি ই সবচেয়ে ভালো পথ কিনা সেটি নিয়ে কথা বলবো পরের টিউটোরিয়াল এ। সাথে থাকবে একটি স্যাম্পল উইন্ডোজ ফোন অ্যাপ।

হ্যাপী কোডিং!