গ্রাফ সার্চ – এ* সার্চ

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

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

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

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

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

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

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

Graph1

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

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

Graph2

আমাদের শুরু করবার নোড হবে 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 . এখন আমাদের অবস্থা নিচের মতো:
(sav)Graph

খেয়াল করলে দেখবেন, এখানে 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

(sav)Graph3যেহেতু 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 এ পাঠিয়ৈ দিবো।

(sav)Graph4

এখন আমাদের 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 হয়ে গেছে।

(sav)Graph5

এখন খেয়াল করলে দেখবেন আমাদের 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 ই আমাদের খুঁজতে থাকা পথ।তার মানে হচ্ছে আপনার এ* সার্চ এ যদি এক্সপান্ড করতে যে নোডটি সিলেক্ট হবে সেটিই যদি গোল নোড হয়, আপনি আপনার পথ পেয়ে গেছেন।

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

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

Advertisements

Windows Phone For Newbies: Episode 1 – Introduction

আপনি যদি আগে কখনোই উইন্ডোজ ফোনে কাজ না করে থাকেন তাহলে এই ভিডিও সিরিজ টি আপনার জন্যে। এটি উইন্ডোজ ফোন ৮.১ এর একটি বাংলা টিউটোরিয়াল সিরিজ যা আপনাকে একদম শুরু থেকে উইন্ডোজ ফোনে কাজ করার জন্য সম্যক সকল কিছু জানিয়ে দেবে।

এটি সিরিজটির প্রথম পর্ব

ইউটিউব প্লেলিস্টটি পাচ্ছেন এইখানে

প্রোজেক্ট সোর্স কোড পাচ্ছেন এইখানে

বাংলায় উইন্ডোজ ফোন – DelegateCommand, The Reusable ICommand

অনেকদিন পর ফেরত আসলাম। আজকের টিউটোরিয়াল ICommand এর একটি সহজ ও Reusable Implementation যার নাম DelegateCommand, তার উপরে। DelegateCommand implement হয় ICommand interface দিয়েই এবং এটি ICommand এর ব্যবহারকে অনেকটাই সহজ করে দেয়। আশা করি সবার ভালো লাগবে।

পুনশ্চ: যদি আপনি Introduction to ICommand দেখে না থাকেন তাহলে অনুগ্রহ করে দেখে আসুন।

 

প্রজেক্ট সোর্স পাওয়া যাবে এই লিংকে – http://sdrv.ms/1dYX3pT

বাংলায় উইন্ডোজ ফোন – Introduction to ICommand

ফিরে আসলাম আবার। আজকের টিউটোরিয়াল ICommand এর উপরে। নিঃসন্দেহে  অত্যন্ত গুরুত্বপূর্ন একটি interface যেটা MVVM approach এ বড় ভূমিকা পালন করে। আশা করি সবার ভালো লাগবে। 🙂

স্যাম্পল প্রজেক্ট ডাউনলোড করে নিন নিচের লিঙ্ক থেকে :
http://sdrv.ms/1eouqSL