প্রথমেই জানতে হবে BFS এলগরিদম।কিন্তু আমি ধরেই নিচ্ছি,যারা এই লেখা পড়তে এসেছে,তারা BFS জানে।জানা না থাকলেও কোন সমস্যা নাই।
http://en.wikipedia.org/wiki/Breadth-first_search উইকির লিঙ্ক এটা
আর কারো ইংরেজী পড়তে সমস্যা হলে,বাংলাতেও একটা ভাল টিউটোরিয়াল আছে https://sites.google.com/site/smilitude/shortestpath
এখন আসলে জানা দরকার স্টেট ভ্যারিয়েবল কাকে বলে।স্টেট ভায়রিয়েবলের আইডিয়া ডিপিতেও কাজে লাগবে।
BFS দিয়ে কোন কিছু সার্চ করা যায়।তাই BFS এর জন্য state variable মানে হল,সার্চ স্পেসের যে কোন জায়গাকে uniquely রিপ্রেজেন্ট করতে যে কয়টা ভ্যারিয়েবল লাগে। তাহলে সার্চ স্পেস কি জিনিস?সার্চ স্পেস হল,আমি যে কয় জায়গায় একটা জিনিস সার্চ করব সে জায়গাগুলো নিয়েই আমার সার্চ স্পেস।যেমন একটা ৮x৮ দাবার বোর্ডের জন্য সার্চ স্পেস হল দাবার বোর্ডের ৬৪টা ঘর।কারণ এর বাইরে আসলে কোন দাবার গুটি থাকতে পারে না।তাই এর বাইরে আমার সার্চ করারও কোন প্রয়োজন নেই।
State variable এর উদাহরণঃ একটা দাবার বোর্ডে কুইন কোথায় আছে আমি জানতে চাই।তাহলে শুধু রো নাম্বার কি স্টেট ভ্যারিয়েবল হতে পারে?না,পারে না। কারণ ধরি কুইনটা ৫ নাম্বার রোতে আছে।কিন্তু শুধু রো নাম্বার দিয়ে দাবার বোর্ডের কোন পজিশাঙ্কে uniquely রিপ্রেজেন্ট করা যায় না।৫ নাম্বার রোতে তো আরো অনেকেই থাকতে পারে!!!
কিন্তু যদি বলি কুইন্টা ৫ নাম্বার রো এর ৬ নাম্বার কলামে আছে,তবে সেটা uniquely define করা হল,কারণ ৫ নাম্বার রো এর ৬ নাম্বার কলামে আর কেউ নাই।
যদি অন্যভাবে চিন্তা করি,তাহলে কুইন্টা কোন রোতে আছে সেটা জানার পরে আমি অবশ্যই জানতে চাব কুইন্টা কোন কলামে আছে(যদি আমার প্রব্লেমে দরকার হয়)।তাহলে, যে সব ভ্যারিয়েবলের মান জানার পরে আর কোন কিছু জানার দরকার হয় না,সেগুলাই স্টেট ভ্যারিয়েবল।
স্টেট ভ্যারিয়েবল ২ ভাবে বুঝালাম,যে যেভাবে বুঝতে পারে,একভাবে বুঝলেই হবে।
এখন আমরা কিছু প্রব্লেম নিয়ে আলোচনা করি।যাতে কন্সেপ্ট একদম ক্লিয়ার হয়ে যায়।
http://uva.onlinejudge.org/external/4/439.html এটা uva 439 Knight Moves
এখানে বলা হয়েছে, দাবার বোর্ডে একটা ঘোড়ার স্টার্টিং পজিশান এবং লাস্ট পজিশান দেয়া আছে।মিনিমাম কয়টা মুভে ঘোড়াটা স্টার্টিং পজিশান হতে লাস্ট পজিশানে যেতে পারবে, তা বের করতে হবে।
এই প্রব্লেমটা ডিপি দিয়েও করা যায়,কিন্তু BFS দিয়ে করার উদ্দেশ্য্য হল,একাধিক স্টেট ভ্যারিয়েবল থাকলে কিভাবে BFS দিয়ে কিভাবে সার্চ করা যায় সেটা দেখা।
এখন আগে আমার সাধারণ BFS এর কোডটা দেখি, মানে যেখানে স্টেস্ট ভ্যারিয়েবল এক্টা integer[আমি শুধু আমার BFS এর কোড সেগমেন্টটা দিলাম।এরের ডিক্লারেশান,ম্যাক্রো…এসব আশা করি এম্নিতেই বোঝা যাবে]:
int BFS(int s,int d){//to find shortest path from s to d
memset(color,White,sizeof color);
memset(dist,-1,sizeof dist);
memset(parent,-1,sizeof parent);
dist[s]=0;
color[s]=Gray;
queue<int>q;
q.push(s);
int u;
while(!q.empty()){
u=q.front();
q.pop();
//printf("Layer number is: %d",dist[u]);
if(u==d)return dist[u];
tr(adjList[u],it){//u node এর adjacent সবাইকে traverse করছি,একটা ম্যাক্রো লিখে আমি এটা করেছি
//এটা যে যার মত ইম্পলিমেন্ট করতে পারে।
if(color[*it]==White){
color[*it]=Gray;
dist[*it]=dist[u]+1;
parent[*it]=u;
if(*it==d)return dist[*it];
q.push(*it);
}
}
color[u]=Black;
}
return -1;
}
উপরের কোডের কিছু কিছু জায়গায় চেঞ্জ আনতে হবে।উপরের কোডে state variable ছিল একটা integer.তাই এখানে রো আর কলাম কে
একটা ভ্যারিয়েবলে কনভার্ট করতে হবে,সেটা করা যায় class বা strucrure এর মাধ্যমে।তার মানে একটা structure বানাতে হবে
যার element সংখ্যা state variable এর সমান।
struct state{
int row,col,dist;
};
কিন্তু এখানে dist কেও নিয়ে এসেছি,যাতে distance রাখার জন্য আলাদা একটা এরে না রাখতে হয়।আলাদা একটা এরে রাখলেও কোন
সমস্যা নাই।তবে একসাথে রাখলে প্রায়ই কোড করতে সুবিধা হয়।
আগে queue টা ছিল integer type এর,কিন্তু এখানে queue টা হবে structure type এর মানে queueq,এরকম কিছু ছোটখাট চেঞ্জ
করতে হবে।
আর == operator টা overload করতে হবে।কারণ,আগের কোডে লিখছিলাম,if(u==d),কিন্তু এখানে u,d ২টাই state type এর।
bool operator ==(const state& a,const state& b){
if((a.col==b.col)&&(a.row==b.row))return true;
return false;
}
আর বাকি যা কিছু চেঞ্জ,তা দেখলেই বোঝা যাবে ইনশা আল্লাহ
#include <cstdio> // In case needed
#include <queue> // queue and priority_queue
#include<string.h>
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define Nodes 100
#define White -1//memset works properly with -1
#define Gray 1
#define Black 2
using namespace std;
int color[9][9];
struct state{
int row,col,dist;
};
bool operator ==(const state& a,const state& b){
if((a.col==b.col)&&(a.row==b.row))return true;
return false;
}
int moverow[]={2,2,-2,-2,1,1,-1,-1};
int movecol[]={1,-1,1,-1,2,-2,2,-2};
int BFS(state s,state d){//to find shortest path from s to d
memset(color,White,sizeof color);
s.dist=0;
color[s.col][s.row]=Gray;
queue<state>q;
q.push(s);
state u;
while(!q.empty()){
u=q.front();
q.pop();
if(u==d)return u.dist;
int temprow,tempcol;
REP(i,0,7){
tempcol=u.col+movecol[i];
temprow=u.row+moverow[i];
if(tempcol>=0 && tempcol<=7 && temprow>=0 && temprow<=7){
if(color[tempcol][temprow]==White){
color[tempcol][temprow]=Gray;
state temp_s;
temp_s.col=tempcol,temp_s.row=temprow,temp_s.dist=u.dist+1;
if(temp_s==d)return temp_s.dist;
q.push(temp_s);
}
}
}
color[u.col][u.row]=Black;
}
return -1;
}
int main(){
char s1[4],s2[4];
state s,d;
while(scanf("%s %s",s1,s2)!=EOF){
s.col=s1[0]-'a';
s.row=s1[1]-'1';
d.col=s2[0]-'a';
d.row=s2[1]-'1';
int ans=BFS(s,d);
printf("To get from %s to %s takes %d knight moves.\n",s1,s2,ans);
}
return 0;
}
এবারে আরো কিছু উদাহরণ দেখা যাকঃhttp://uva.onlinejudge.org/external/100/10047.html এটা uva 10047 The Monocycle
এখানে বলা হয়েছে,শুরুতে সাইকেল্টা উত্তর দিকে মুখ কারানো থাকবে।যে দিকে মুখ কারানো আছে,সে দিকে যেতে পারবে,অথবা ডানে বা বামে ঘুরতে পারবে।প্রতিটা মুভের(সামনে আগানো বা ডানে-বামে ঘোরা)কস্ট ১,তাই BFS করাই যাবে।Destination এ পৌছানোর পরে কোন দিকে মুখ করে আছি সেটা ব্যাপার না।আমার পৌছাতে পারলেই হল,যাতে করে সাইলেকের চাকার নিচে সবুজ রং থাকে।
এখানে স্টেট গুলো কি?রো-কলাম তো অবশ্যই লাগবে,তার সাথে আর কি লাগবে?হুম,চাকার নিচের রঙ কি সেটাও তো লাগবে।কারণ বলাই আছে, Destination এ সাইলেকের চাকার নিচে সবুজ রং থাকতে হবে।
আচ্ছা,কোন দিকে মুখ করে আছি সেটা কি একটা state variable হতে পারে?প্রব্লেমে বল আছে,Destination এ পৌছানোর পরে কোন দিকে মুখ করে আছি সেটা ব্যাপার না।তাই direction মনে হয় state variable না…
আচ্ছা,কোন দিকে মুখ করে আছে সেটা যদি না জানি,তবে কি আমি বলতে পারব এর পরের স্টেপে সাইকেল্টা সামনে আগালে কোন দিকে যাবে?না,পারি না।
আবার,direction যদি state variable না হয়,তবে কি আমি যে কোন সাইকেলকে uniquely define করতে পারব?না,পারব না।কারণ একটা সাইকেল উত্তর দিকে মুখ করে ৪ নাম্বার রো এর ৬ নাম্বার কলামে আছে আর চাকার রঙ সবুজ।আরেকটা সাইকেল দক্ষিণ দিকে মুখ করে ৪ নাম্বার রো এর ৬ নাম্বার কলামে আছে আর চাকার রঙ সবুজ।২টা সাইকেল কিন্তু এক না,কারণ ১মটা সামনে গেলে উত্তরে যাবে,২য়টা সামনে গেলে দক্ষিণে যাবে।কিন্তু direction কে state variable না বললে আমার কাছে মনে হবে ২টা সাইকেল একই।
তার মানে কোন সাইকেল কে uniqueley define করতে ৪টা জিনিস লাগবে।রো,কলাম,এখন নিচে কোন কালার, আর কোন দিকে মুখ করে আছে।
আশা করি এটার কোড আগেরটার মতই করে ফেলা যাবে।
