Friday, May 27, 2016

0/1 BFS

shortest path বের করার গ্রাফ এর আল্গরিথম গুলোকে দুই ভাবে ভাগ করা যায় ।

   ১। এক নোড থেকে অন্য নোডে যাবার cost ১ ।
   ২। এক নোড থেকে অন্য নোডে যাবার cost যে কোন কিছু হইতে পারে।

যদি এক নোড থেকে অন্য নোডে যাবার cost ১ হয় তাহলে  এই প্রবলেম গুলা bfs বা dfs দিয়ে সল্ভ করা হয় যদি cost যে কোন কিছু হয় তাহলে floyd-warshal , Dijkstra বা Bellmanford ব্যাবহার করা হয় , যদি নেগেটিভ হয় cost তাহলে Bellmanford ব্যাবহার করা ।

bfs এর একটা ভ্যারিয়েশন হচ্ছে 0/1 bfs .  এইখানে এক নোড থেকে অন্য নোডে যাবার cost 0 বা ১ হতে পারে ।সচরাচর আমরা bfs এর প্রবলেম  এ queue ব্যাবহার করি , এইখানে আমরা করব deque .  যদি current node থেকে আমরা next node এ ০ cost এর কোন edge দ্বারা যুক্ত থাকি যা মানে হচ্ছে current node এ থাকা আর next node এ থাকা একই ব্যাপার তাহলে next_node কে deque এর front এ পুশ করব । যদি দেখা যায় current node থেকে next node এ যাবার cost ১ তাহলে আমরা deque এর back এ next_node কে পুশ করব । আর একটা ব্যাপার রয়েছে , bfs এ আমরা একটা নোড একবার আসা মানেই এতে minimum cost এ এসে গেছি এইখানে কিন্তু তা হয় , তাই নোড cost update এর কাজটা আমরা dijkstra এর মত করব , dijkstra তে প্রতি পুশ এর জন্য priority_queue বা sorting_order কাজ করতে হয় এতে push এর জন্য টাইম লাগে প্রায় logN এর মত , o/1 bfs তা o(1) এ হবে । বাকি সব কিছু আগের মতই হবে ।

practice problem : 1