N Puzzle Problem – part 2

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

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

image6.jpg

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

ডি এফ এস ( 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* সার্চ ব্যবহার করছি, আমাদের অপ্রয়োজনীয় চাইল্ড নোড জেনারেট না করাই উত্তম। যখন দরকার হবে আমরা তখন জেনারেট করবো। নিচের ছবিটি খেয়াল করি ঃ 

8-puzzle-manhattan.jpg

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

1

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

2

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

3

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

2

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

4

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

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

N Puzzle Problem – part 1

posa

ছবিটি একটি ৮-পাযল ( 8 – Puzzle ) এর ছবি। এখানে ১ থেকে ৮ পর্যন্ত ইউনিক ৮ টি নম্বর আছে। এবং একটি ফাঁকা ঘর আছে। আমাদের কাজ হচ্ছে পাযলটি কে ফাইনাল স্টেট এ নিয়ে আসা। এক্ষেত্রে আমরা ফাঁকা ঘরটির উপর ভিত্তি করে উপরে, নিচে, ডানে এবং বামে মুভ দিতে পারবো। আমাদের কাজ হচ্ছে নিচের ছবির মতন স্টেট এ আসা। 

8 puzzle

আমরা হিসাবের সুবিধার্থে ফাঁকা ঘরটিতে 0 (শুন্য) বসিয়ে হিসাব করবো। একটি ডেমোন্সট্রেশন দেখা যাক –>

Capture.JPG

আমরা প্রথমে বামে( 4 কে 0 এর ঘরে নিয়েছি, কাজেই আমাদের বামদিকে মুভ হয়েছে ), এরপরে উপরে এবং আবার বামে গিয়ে স্টেট মিলাতে পেরেছি। আমাদের ইনিশিয়াল থেকে মোট ৩ টি মুভ দেয়া লাগার কারনে আমাদের টোটাল মুভ লেগেছে ৩ টি। আমাদের কাজ হচ্ছে, এরকম পাযল দেয়া থাকলে ইনিশিয়াল থেকে ফাইনাল স্টেট এ সবচেয়ে কম কত মুভ এ যাওয়া যায় এবং মুভগুলি কিকি তা হিসাব করা।
এটা একটি ৮-পাযল প্রব্লেম। এখানে n এর মান ৩। কাজেই একটি n*n ২ডি গ্রিড এর মধ্যে 0 থেকে n²-1 পর্যন্ত সংখ্যা থাকবে। n এর মান ৪ হলে আমরা তাকে ১৫-পাযল বলবো।

Unsolvable State for N Puzzle Problem

আমরা এখানে ৮-পাযল নিয়ে আলোচনা করবো। সব ৮-পাযল স্টেট কিন্তু সল্ভ করা নাও যেতে পারে। unsolvable এরকম স্টেট আসতে পারে আমাদের কোন এক মুভ এ। আমরা হাতে কলমে কিছুদূর আগালে হয়তোবা বুঝতে পারবো যে এটা সল্ভ করা সম্ভব না। কিন্তু কম্পিউটার কে এটা কিভাবে বুঝাবো? এরজন্য আমাদের কিছু প্যাটার্ন অ্যাানালাইসিস করা লাগবে যে কিকি কারনে একটি পাযল unsolvabel state আছে তা আমরা সহজে বুঝতে পারি।
আমাদের একটি n*n গ্রিড দেয়া আছে। কিছু নিয়ম খেয়াল করলে আমরা বলতে পারবো যে n*n-1 পাযলটি সল্ভ করা যাবে কিনা। নিয়মগুলি খেয়াল করি — >
১। যদি n এর মান বেজোড় হয়, তাহলে পাযলের স্টেটটি সল্ভ করা যাবে শুধুমাত্র তখনি যখন ঐ স্টেট এর ইনভার্শন (inversion) সংখ্যা জোড় হবে।
২। যদি n এর মান জোড় হয় (১৫-পাযল এর ক্ষেত্রে n এর মান ৪, যা জোড়) তাহলে পাযলের স্টেটটি সল্ভ করা যাবে যদি–>

  • যদি গ্রিড এর নিচ থেকে শুরু করে জোড় পজিশন (second_last, fourth_last,… ) এ ফাঁকা ঘরটি থাকে এবং ইনভার্শন সংখ্যা বেজোড় হয় অথবা,
  • যদি গ্রিড এর নিচ থেকে শুরু করে বেজোড় পজিশন (last, third_last,fifth_last,… ) এ ফাঁকা ঘরটি থাকে এবং ইনভার্শন সংখ্যা জোড় হয়।

** এখানে পজিশন হল, নিচের সারি ( একদম শেষ সারিকে ১ ধরে ) থেকে শুরু করে উপরে উঠতে থাকলে যেই সারি তে আমরা ফাঁকা ঘরটি পাবো সেই সারি নম্বর।

৩। বাকি সকল ক্ষেত্রে পাযলটি সল্ভ করা সম্ভব হবেনা।

Inversion Count for a N Puzzle State

final

আমরা গ্রিডটি কে ২ডি থেকে ১ডি তে কনভার্ট করি। তাহলে উপরের উদাহরন অনুসারে আমরা এভাবে মানগুলিকে সাজাই –> 1  2  3  0  4  6  7  5  8
এখানে পজিশন হল ২, কারন নিচ থেকে শুরু করে ২ নং সারিতে আমাদের ফাঁকা ঘরটি আছে।
এখন এটি একটি ১ডি অ্যাারের মতন হয়ে গেল। এখন আমরা এখানে সকল পেয়ার (pair) সংখ্যা এর জন্য দেখবো যে ,
একটি সংখ্যা তার পরের সংখ্যা থেকে বড় কিনা। যদি বড় হয়, তাহলে আমরা ইনভার্শন এর মান বাড়াবো। তাহলে এই অ্যাারে থেকে খেয়াল করলে আমরা সকল পেয়ার এর মধ্যে হিসাব করলে দেখবো যে ২ টি সংখ্যা এর মধ্য নিচের পেয়ারগুলি আমাদের ইনভার্শন হবার শর্ত পূরণ করে–>

  • ( 6, 5 ) as 6 > 5
  • ( 7, 5 ) as 7 > 5

তাহলে আমাদের ইনভার্শন সংখ্যা হচ্ছে ২ যা জোড়। এবং এই পাযল এর জন্য n এর মান ৩, যা বেজোড়। এবং এটি আমাদের unsolvable puzzle state এর ১ নং শর্তটি পূরণ করেছে। কাজেই, পাযলের এই স্টেটটি সল্ভেবল একটি স্টেট। আরেকটি পাযল দেখা যাক–>
for.JPG
এখানে  2  1  3  4  5  6  7  8  9  10  11  12  13  14  15  0
সুতরাং আমাদের ইনভার্শন সংখ্যা হবে ১। ( যেহেতু পেয়ার < 2, 1 > ই কেবলমাত্র শর্ত মানে )।
আর যেহেতু ইনভার্শন সংখ্যা বেজোড় এবং n  এর মান এখানে জোড় ( 4 ) কাজেই এটি unsolvable puzzle state এর ২নং শর্ত অনুযায়ী , 0 নিচ থেকে শুরু করে বেজোড় পজিশন এ আছে। এবং ইনভার্শন সংখ্যা এর মান ও বেজোড়। কাজেই এটি একটি unsolvable state । এই স্টেট থেকে কখনো আমরা ফাইনাল স্টেট এ যেতে পারবোনা।
** আমরা কিন্তু ইনভার্শন কাউন্ট এর সময় 0 কে কখনো ধরবো না। হিসাবের সুবিধার্থে আমরা 0 নিয়েছি, যাতে প্রোগ্রাম লিখার ক্ষেত্রে আমাদের সুবিধা হয়। এখানে 0  আসলে ফাঁকা ঘর, যা আমরা আগেই বলে এসেছি।
আরো কিছু উদাহরন দেখা যাক—>


15puz115puz215Puzz315Puzz4

 

এখানে একটি n-puzzle এর সল্ভ চেকিং এর কোড দেয়া হল। ইচ্ছামতন গ্রিড সাইজ দিয়ে কোড রান করলে আমরা বলতে পারবো স্টেট টি সল্ভ করা সম্ভব কিনা।
Code : solvable_state_checking

Sources:
https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

পরবর্তী পর্ব পাওয়া যাবে এখানে ঃ part – 2 

Inspiring Quotes About Chess

Capture

Over the last few centuries, there have been hundreds of incredible quotes about chess. Here is given some of the best quotes that sum up the game nicely.

  • “Tactics flow from a superior position.” — Bobby Fischer
  • “Chess is a fairy tale of 1,001 blunders.” — Savielly Tartakower
  • “The winner of the game is the player who makes the next-to-last mistake.” — Savielly Tartakower
  • “When you see a good move, look for a better one.” — Emanuel Lasker
  • “Even the laziest king flees wildly in the face of a double check!” — Aron Nimzowitsch
  • “The pawns are the soul of chess.” — Francois Andre Danican Philidor
  • “The hardest game to win is – A Won Game.” — Emanuel Lasker
  • “Many has become the chess masters, none has become the master at chess.” — Siegbert Tarrasch
  • “A sacrifice is best refuted by accepting it.” — Wilhelm Steinitz
  • “Strategy requires thought, tactics require observation.”– Max Euwe
  • “Chess is played with the mind and not with the hands!” — Renaud and Kahn
  • “Openings teach you openings. Endgames teach you chess!” — Stephan Gerzadowicz
  • “The essence of Chess is thinking about what Chess is.” — David Bronstein
  • “Every Chess master was once a beginner.” — Chernev
  • “One doesn’t have to play well, it’s enough to play better tha your opponent.” — Siegbert Tarrasch
  • “It’s always better to sacrifice your opponent’s men.” — Savielly Tartakover
  • “In a gambit you give up a Pawn for the sake of getting a lost game.” — Samuel Standige Boden
  • “Some sacrifices are sound; the rest are mine.” — Mikhail Tal
  • “A bad plan is better than none at all.” — Frank Marshall
  • “First-class players lose to second-class players because second-class players sometimes play a first-class game.” — Siegbert Tarrasch

(Collected)

Set

সেট (Set)

সেট বলতে আমরা ইউনিক জিনিস বুঝে থাকি। যেমন আমার কাছে অনেকগুলি চকলেট আছে, ২ টি মার্স, ১০ টি স্নিকার্স, ৭ টি কিটক্যাট, ১৮ টি সাফারী। এখন আমি যদি আমার চকলেট এর সেট করতে চাই, তাহলে
s = { Mars, Snikers, Kitkat, Safari };
এখানে কিন্তু কোন চকলেট কতবার আছে তা জানার কোন দরকার নেই। আমার খালি দরকার আমার কাছে ইউনিক কি আছে। সেট এই কাজটা করে। STL এর সেট ভ্যালুগুলিকে ইউনিক আকার এবং একই সাথে সর্টেড আকারেও রাখে।
#include <set>
int main(){
set < int > s;
s.insert ( 10 );
s.insert ( 10 );
s.insert ( 1 );
s.insert ( 10 );
s.insert ( 10 );
s.insert ( 2 );
s.insert ( 2 );
set < int > :: iterator it; // সেট এর ভ্যালু পয়েন্ট করার জন্য ইটারেটর ডিক্লার
for ( it = s.begin(); it != s.end(); it++ )
cout << *it << endl;  // সেট এর ভ্যালুগুলি প্রিন্ট করলাম
cout << s.size() << endl; //সেট এর সাইজ প্রিন্ট করলাম
}
ধরি আমাকে অনেকগুলি নম্বর দেয়া হল। আমাকে বলতে হবে এর মধ্যে ইউনিক কতটি নম্বর আছে। এর জন্য আমরা খালি সেট এর মধ্যে ইনসার্ট করতে থাকবো এবং সেট এর সাইজটি প্রিন্ট করে দিবো।

Upper_Bound & Lower_Bound

আপার_বাউন্ড এবং লোয়ার_বাউন্ড(upper_bound & lower_bound)

আপার_বাউন্ড এবং লোয়ার_বাউন্ড খুব গুরুত্বপুর্ণ  একটি টপিক। এখন একটি কাহিনী দেখা যাকঃ
আসিফ এবং আসফি ২ যমজ ভাই। তাদের বয়স ধরি ২১। অর্থাৎ তাদের বিয়ের বয়স হয়েছে। তারা আবার খুব হ্যান্ডসাম এবং একই সাথে ব্রিলিয়ান্ট এবং তাদের আগে কোন ফুল-গার্লফ্রেন্ড, হাফ-গার্লফ্রেন্ড কিছুই ছিলনা। কাজেই তাদের বিয়ে করার কথা শুনে মেয়েরা পাগলপ্রায়। এখন আসিফ এর পছন্দ তার থেকে কম বা তার সমান বয়স্ক মেয়েদের (বউ হিসেবে)। অন্যদিকে আসফি এর পছন্দ তার থেকে বেশি বয়স্ক মেয়েদের। এখন ধরি প্রায় ১০০ জন মেয়ে তাদেরকে বিয়ে করার জন্য আগ্রহী। আমাদের কাজ হবে আসিফ এবং আসফি এর জন্য সঠিক বয়সের পাত্রী খুঁজে বের করা। কিভাবে করবো কাজটা? প্রথমেই আমরা পাত্রীদের কে তাদের বয়সের ক্রমানুসারে কম থেকে বেশি আকারে সাজাই। এই সংখ্যাগুলি ধরে একটি ভেক্টর এর মধ্যে রাখি। ধরি আমাদের ভেক্টরটি দেখতে এরকমঃ
int v [ ] = { 10, 12, 14, 21, 21, 21, 21, 30, 32 };
এখন আমরা এই v ভেক্টর এর উপর লোয়ার_বাউন্ড চালালে পাবো ২১, যা ৩ তম ইনডেক্স। আর আপার_বাউন্ড চালালে পাবো ৩০, যা ২১ থেকে ঠিক বড়।CaptureOutput :
lower_bound at position 3
upper_bound at position 6
upper_bound & lower_bound ফাংশন এর জন্য সি++ এর <algorithm> হেডার ফাইল ব্যবহার করা হয়।
ভেক্টর এর ইনিশিয়াল এবং এনডিং অ্যাড্রেস এবং কোন ভ্যালুর সাপেক্ষে আমরা বাউন্ড বের করতে চাই এগুলি প্যারামিটার হিসেবে দিতে হবে।

Iterator

ইটারেটর(Iterator)

ইটারেটর আসলে সি এর পয়েন্টার এর মত কাজ করে। পয়েন্টার একটি অ্যাড্রেসকে পয়েন্ট করে থাকে যা থেকে আমরা পরবর্তীতে সেই অ্যাড্রেস এর ডাটা নিয়ে কাজ করতে পারি। সি++ এর ইটারেটর এর কাজ ও ঠিক ওরকম। STL ফাংশনগুলি অনেক ক্ষেত্রে অ্যাড্রেস পাঠায় আমরা যে ডাটাকে খুঁজছি, তা কোথায় আছে তার। ইটারেটর ডিক্লার করে এভাবে–>
vector< int > :: iterator it ;
আমরা ভেক্টর এর একটি ইটারেটর it ডিক্লার করলাম।
এখন ভেক্টর এর সব এলেমেন্ট দেখতে চাইলে আমরা এটা করবো–>
for ( it = v.begin(); it != v.end(); it++ )   // v নামের একটি ইন্টিজার এর ভেক্টর নিলাম।
       cout << *it << endl;  // *it দিয়ে আমরা it অ্যাড্রেস যাকে পয়েন্ট করে আছে, তার ভ্যালু প্রিন্ট করলাম।

Searching Algo

লিনিয়ার সার্চ(Linear Search)

লিনিয়ার সার্চ সবচেয়ে ব্যাসিক সার্চ টেকনিক। ধরি আমাদের n টি নম্বর এর একটি অ্যাারে দেয়া আছে। এখন আরেকটি নম্বর a দিয়ে আমাকে জিজ্ঞাসা করা হল, এই a , আগের n টি নম্বর এর মাঝে আছে কিনা। স্বাভাবিকভাবে আমরা 0 থেকে n (অ্যাারে এর ঘর বিবেচনা করলে) পর্যন্ত একটি লুপ চালায়ে নম্বরটিকে বের করার চেষ্টা করবো।

int arr [ ] = { 1, 2, 4, 12, 14, 78, 21, -90, 111, 1467};
int a = 111;
for ( int i = 0; i < 10; i++ ){
if ( arr [ i ] == a ){
cout << ” Found the number 😀 ” << endl;
                break;
}
}
সার্চিং এর ক্ষেত্রে লিনিয়ার সার্চ ছোট রেঞ্জ এর মধ্যে কাজ করবে কিন্তু রেঞ্জ বড় হয়ে গেলে TLE দিবে। আমরা লিনিয়ারি একটি পজিশন থেকে আরেকটি পজিশন এ যাচ্ছি ( n তম এলেমেন্ট পাওয়ার জন্য আমাদের শুরু থেকে n পর্যন্ত যেতে হবে), কাজেই লিনিয়ার সার্চের কমপ্লেক্সিটি O ( n )  [ Order of n ] যেখানে n হল কতটি এলেমেন্ট এর মাঝে সার্চিংটি চলছে।

বাইনারি সার্চ(Binary Search)

বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ টেকনিক এবং এর ব্যবহার ও খুব মজার। বাইনারি সার্চের জন্য প্রথমেই আমাদের নম্বরগুলিকে কোন একটি অর্ডার এ সাজাতে হবে ( Ascending or Descending )। এরপরে আমরা ২টি পজিশন সেট করবো low এবং high নামে। low  হবে আমাদের অ্যাারে এর 0th ইনডেক্স এবং high হবে (n-1)th ইনডেক্স। এখন আমরা এই high এবং low এর মাঝে থেকে middle ইনডেক্স বের করার চেষ্টা করবো এবং চেক করবো ঐ middle ইনডেক্স এর ভ্যালুটা আমাদের কাঙ্ক্ষিত ভ্যালুর সাথে মিলে গেছে কিনা। যদি মিলে যায়, তাহলে আমরা আমাদের ভ্যালু পেয়ে গেছি। যদি না মিলে, তবে ২টি কন্ডিশন হতে পারে।
১ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে বড়।
২ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে ছোট।
ধরি আমাদের অ্যাারেটি ছোট থেকে বড় আকারে সাজানো আছে। এখন ১ এর জন্য মিড ভ্যালুটি বড়, কাজেই আমাদের কাঙ্ক্ষিত ভ্যালুটি মিড ইনডেক্স এর অবশ্যই আগে আছে। কাজেই তখন আমাদের high হয়ে যাবে middle – 1 এবং low এর কোন চেঞ্জ হবেনা। ২ঃ এর খেত্রেও একই ব্যাপার। তখন low হবে middle + 1 এবং high এর কোন চেঞ্জ হবেনা। একটি উদাহরন দেখিঃ আমাদের ২০ কে খুঁজে বের করতে হবে। binary-search
টাইম কমপ্লেক্সিটি ঃ আমরা প্রতিবার সার্চিং এর জন্য একটি অংশ নিচ্ছি এবং অন্যটি বাদ দিয়ে দিচ্ছি। কাজেই worst case এর জন্য আমাদের কমপ্লেক্সিটি হবে O ( N * logN )।
স্যাম্পল কোড ঃ Capture
আমরা ভ্যালু পেয়ে গেলে ভ্যালুটির ইনডেক্স রিটার্ন করবো, আর না পেলে -1 রিটার্ন করবো। লক্ষ্য করলে দেখবে যে বাইনারি সার্চ এর টারমিনেট কন্ডিশন যখন high এর চেয়ে low এর ইনডেক্স বড় হয়ে যাবে। এই ব্যাপারগুলি ভালোভাবে খেয়াল না রাখলে ইনফিনিট লুপ এ পরবে প্রোগ্রাম। কোড করার সময় তাই আমাদের মাথায় রাখতে হবে আসলে কখন কোথায় কি হচ্ছে এবং কখন কোন কন্ডিশন দিলে ঠিকমতন প্রোগ্রাম রান করবে।