The Particle Swarm Optimization by Nafis Islam on Scribd
Sunday, December 17, 2017
Wednesday, November 22, 2017
Into to Meta-Heuristics
Meta-heuristic হল একটি primary field of stochastic optimization.
Stochastic optimization হল the general class of algorithm and techniques যা randomness use করে optimal বা optimal এর কাছাকাছি solution বের করে আনে।
•যে সকল problem এ আমরা আগে থেকে বুঝতে পারি না যে, optimal solution কেমন হতে পারে।
•যে সকল problem এ আমরা জানি না, principal way তে কিভাবে solution এর দিকে আগাব।
•যে সকল problem এ, brute-force search impossible কারন search space অনেক বড়।
কিন্তু আমাদের কাছে ঐ problem এর কোন candidate solution দিলে test করে দেখতে পাড়ব solution তা কত ভাল।সে সকল problem এ meta-heuristic use করা হয়।
“Meta-heuristics are applied to I know it when I see it problem”
এরকম কোন problem এর সামনে পরলে সবচেয়ে simplest thing যা করতে পারি তা হল random search, আমরা random solution বের করব যতক্ষণ আমাদের কাছে time আছে, সবচেয়ে best solution return করব।
কিন্তু random search এর আগে একটা alternative পথ দেখতে পারি।
আমরা প্রথমে random solution নেই। এই solution একটা ছোট এবং random modification করি। এখন নতুন solution test করি।
যদি দেখি current solution better হয় then old solution ফেলে দিব। যদি না হয় তাহলে current solution ফেলে দিব।
এখন বর্তমান হাতে যে solution আসে তার উপর ছোট ও random modification করব। এভাবে যতক্ষণ পারা যায় repeat করতে থাকব।
এই পধতি কে বলে hill-climbing.এটি হল একটি simple meta-heuristic algorithm.
"It exploits a heuristic belief about your space of candidate solutions which is usually true for many problems: that similar solutions tend to behave similarly (and tend to have similar quality), so small modifications will generally result in small, well-behaved changes in quality, allowing us to “climb the hill” of quality up to good solutions. This heuristic belief is one of the central defining features of meta-heuristics: indeed, nearly all meta-heuristics are essentially elaborate combinations of hill-climbing and random search."
Meta-heuristic দারা যে সকল problem tackle করা যায় সে সকল problem হল sub-class of inverse problem।
Inverse problem কে আমারা এভাবে কল্পনা করতে পাড়ি, মনে করি আমাদের কাছে একটি test function আছে f() যেটা parameter হিসেবে একটি candidate solution কে নিবে এবং ওই solutionটির একটি assessment বা fitness return করবে।
কিন্তু এটা মোটামোট impossible উপরের functionটির inverse function f-1() তৈরি করা যা assessment বা fitness parameter হিসেবে নেয় এবং এমন একটি candidate solution return করবে যার ঐ assessment or fitness থাকবে।
Optimization methods(Meta-heuristic) design করা হয়েছে inverse problem কে overcome করতে।
Stochastic optimization হল the general class of algorithm and techniques যা randomness use করে optimal বা optimal এর কাছাকাছি solution বের করে আনে।
•যে সকল problem এ আমরা আগে থেকে বুঝতে পারি না যে, optimal solution কেমন হতে পারে।
•যে সকল problem এ আমরা জানি না, principal way তে কিভাবে solution এর দিকে আগাব।
•যে সকল problem এ, brute-force search impossible কারন search space অনেক বড়।
কিন্তু আমাদের কাছে ঐ problem এর কোন candidate solution দিলে test করে দেখতে পাড়ব solution তা কত ভাল।সে সকল problem এ meta-heuristic use করা হয়।
“Meta-heuristics are applied to I know it when I see it problem”
এরকম কোন problem এর সামনে পরলে সবচেয়ে simplest thing যা করতে পারি তা হল random search, আমরা random solution বের করব যতক্ষণ আমাদের কাছে time আছে, সবচেয়ে best solution return করব।
কিন্তু random search এর আগে একটা alternative পথ দেখতে পারি।
আমরা প্রথমে random solution নেই। এই solution একটা ছোট এবং random modification করি। এখন নতুন solution test করি।
যদি দেখি current solution better হয় then old solution ফেলে দিব। যদি না হয় তাহলে current solution ফেলে দিব।
এখন বর্তমান হাতে যে solution আসে তার উপর ছোট ও random modification করব। এভাবে যতক্ষণ পারা যায় repeat করতে থাকব।
এই পধতি কে বলে hill-climbing.এটি হল একটি simple meta-heuristic algorithm.
"It exploits a heuristic belief about your space of candidate solutions which is usually true for many problems: that similar solutions tend to behave similarly (and tend to have similar quality), so small modifications will generally result in small, well-behaved changes in quality, allowing us to “climb the hill” of quality up to good solutions. This heuristic belief is one of the central defining features of meta-heuristics: indeed, nearly all meta-heuristics are essentially elaborate combinations of hill-climbing and random search."
Meta-heuristic দারা যে সকল problem tackle করা যায় সে সকল problem হল sub-class of inverse problem।
Inverse problem কে আমারা এভাবে কল্পনা করতে পাড়ি, মনে করি আমাদের কাছে একটি test function আছে f() যেটা parameter হিসেবে একটি candidate solution কে নিবে এবং ওই solutionটির একটি assessment বা fitness return করবে।
কিন্তু এটা মোটামোট impossible উপরের functionটির inverse function f-1() তৈরি করা যা assessment বা fitness parameter হিসেবে নেয় এবং এমন একটি candidate solution return করবে যার ঐ assessment or fitness থাকবে।
Optimization methods(Meta-heuristic) design করা হয়েছে inverse problem কে overcome করতে।
Wednesday, August 30, 2017
Bishops
Problem Statement:
Solution:
এ প্রব্লেম আমি বহুদিন আগে দেখেছি LOJ এ। কিন্তু অত দিন কোন solution মাথায় আসে নাই।
আজকে same প্রবলেম পাইলাম সিএস আচাডেমীতে।
লাস্ট দাবা খেলেছি প্রায় ৬ মাস আগে। কিন্তু আজকে প্রব্লেমটা পরতেগিয়ে মাথায় একটা কথা আসল।
কোন বিশপ যদি কাল ঘরে থাকে তাহলে সে কখন সাদায় জেতে পারে না আবার বিশপ যদি সাদা ঘরে থাকে তাহলে সে কখন কাল জেতে পারে না।
এটা যখই মাথায় আসল তখনি বুঝে গেলাম destination এ পোষাইতে পাড়বে কি না তার solution পেয়ে গেসি।
আমি destination এ পোষাইতে পাড়ব যদি same color হয় current position ও destination position।
এখন এটা check কিভাবে করব?
একটা ২ *৩ board আঁকলাম।
এখনে লক্ষ করলে দেখা যায় যে কোন cell এর r%2==c%2 হলে cellটি white cell হবে। তা না হলে black cell হবে।
আমরা পোষাইতে পাড়বে কি না তা পেয়ে গেসি। কিন্তু minimum move আমাদের লাগবে।
তখন আমি একটা ছবি আঁকলাম।
জিনিশটা লক্ষ করার মত হল আমরা যে রঙ এর ঘরে আছি বোর্ডে সেই রঙ এর অন্য কোন ঘর যেতে মাক্সিমাম ২টা move লাগবে। আর ঘরটি current cell er diagonal যদি হয় তাহলে আমরা ১ move এ যেতে পারি।
current cell (3,2) , destination cell (1,4) এ ২ cell diagonal তা হাতে একে দেখলেই বুঝা যায়। যেহেতু diagonal cell তাই ১ টা move চলে যেতে পারব।
current cell (3,2) , destination cell (3,4) এ ২ cell diagonal না। আমরা একটা move দিয়ে (2,3) cell এ চলে যেতে পারব , আর আরেকটা মভে দিয়ে destination cell (3,4) এ চলে যেতে পারব। সব non-diagonal same color cell এ আমরা একই ভাবে ২টা move এ পোষাইতে পারব।
current cell (3,2) , destination cell (1,4) এ ২ cell diagonal তা হাতে একে দেখলেই বুঝা যায়। যেহেতু diagonal cell তাই ১ টা move চলে যেতে পারব।
current cell (3,2) , destination cell (3,4) এ ২ cell diagonal না। আমরা একটা move দিয়ে (2,3) cell এ চলে যেতে পারব , আর আরেকটা মভে দিয়ে destination cell (3,4) এ চলে যেতে পারব। সব non-diagonal same color cell এ আমরা একই ভাবে ২টা move এ পোষাইতে পারব।
এটাই আমাদের solution :v :v :v ।
এ question পরেছিলাম ১-১.৫ বছর আগে। এ ৩ লাইন এর observation আস্তে লাগে গেছে ১- ১.৫ বছর। জীবন বরই সুন্দর :D ।
Sunday, August 27, 2017
DP & Recursion Lower Bound
DON'T KNOW:
Longest Run on a Snowboard
Wedding shopping [DONE]
Cutting Sticks [FAILED]
Unidirectional TSP
Getting in Line [FAILED]
Distinct Subsequences
Longest Palindrome [DONE]
Collecting Beepers
Optimal Array Multiplication Sequence
Maximum Sum
The Twin Towers
23 out of 5
Take the Land
Stacking Boxes
History Grading
Strategic Defense Initiative
Largest Submatrix
Non Classical (The Easier Ones):
Homer Simpson
How do you add? [DONE]
0-1 Knapsack (Subset Sum):
10819 - Trouble of 13-Dots [DONE]
990 - Diving for Gold
10261 - Ferry Loading
11003 - Boxes
Coin Change (CC):
166 - Making Change
11517 - Exact Change
10313 - Pay the Price
10306 - e-Coins
Longest Increasing Sub-sequence (LIS):
111 - History Grading
10131 - Is Bigger Smarter?
Testing the CATCHER
481 - What Goes Up
497 - Strategic Defense Initiative
10534 - Wavio Sequence
437 - The Tower of Babylon
Longest Common Sub-sequence (LCS):
Longest Common Sub-sequence
Compromise
Vacation
Bitmask DP:
(LOJ) Marriage Ceremonies (bitmask dp)
Free Candies (bitmask dp)
Forming Quiz Teams
Basic recursion:
524 - Prime Ring Problem [DONE]
750 - 8 Queens Chess Problem
729 - The Hamming Distance Problem
167 - The Sultan's Successors
574 - Sum It Up [DONE]
10098 - Generating Fast
10063 - Knuth's Permutation
193 - Graph Coloring
Longest Run on a Snowboard
Wedding shopping [DONE]
Cutting Sticks [FAILED]
Unidirectional TSP
Getting in Line [FAILED]
Distinct Subsequences
Longest Palindrome [DONE]
Collecting Beepers
Optimal Array Multiplication Sequence
Maximum Sum
The Twin Towers
23 out of 5
Take the Land
Stacking Boxes
History Grading
Strategic Defense Initiative
Largest Submatrix
Non Classical (The Easier Ones):
Homer Simpson
How do you add? [DONE]
0-1 Knapsack (Subset Sum):
10819 - Trouble of 13-Dots [DONE]
990 - Diving for Gold
10261 - Ferry Loading
11003 - Boxes
Coin Change (CC):
166 - Making Change
11517 - Exact Change
10313 - Pay the Price
10306 - e-Coins
Longest Increasing Sub-sequence (LIS):
111 - History Grading
10131 - Is Bigger Smarter?
Testing the CATCHER
481 - What Goes Up
497 - Strategic Defense Initiative
10534 - Wavio Sequence
437 - The Tower of Babylon
Longest Common Sub-sequence (LCS):
Longest Common Sub-sequence
Compromise
Vacation
Bitmask DP:
(LOJ) Marriage Ceremonies (bitmask dp)
Free Candies (bitmask dp)
Forming Quiz Teams
Basic recursion:
524 - Prime Ring Problem [DONE]
750 - 8 Queens Chess Problem
729 - The Hamming Distance Problem
167 - The Sultan's Successors
574 - Sum It Up [DONE]
10098 - Generating Fast
10063 - Knuth's Permutation
193 - Graph Coloring
Friday, August 11, 2017
Saturday, June 24, 2017
Count all numbers up to A that have sum of digits equal to S
1 <= A < 10^15
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।
000
001
.
.
188
189
.
.
244
245
.
.
257
258
আমাদের কে প্রথমে জানতে হবে ডিজিট সংখ্যা কয়টি। এখানে আমরা ৩ ডিজিট এর সংখ্যা ধরেছি A।
আমরা ৩ ডিজিট এর সকল সংখ্যা generate করতে পারব। কিন্তু A এর উপরের সংখ্যা generate করে আমাদের কোন লাভ হবে না। তাই A পর্যন্ত limit দিয়ে ৩ ডিজিট এর সংখ্যা generate করব।
আমরা আগেই n ডিজিট এর সকল সংখ্যা কিভাবে generate করা যায় তা দেখেছি এখানে।
এখন আমরা দেখবো A পর্যন্ত limit কিভাবে সেট করা যায়।
আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে 3ta current_digit_no ,sum_left , limit ।
আমরা এভাবে চিন্তা করতে পারি A = 2(0 তম ডিজিট ) 5 (1 তম ডিজিট) 6 (2 তম ডিজিট) 8 (3 তম ডিজিট)।
function er limit parameter আমাদের বলবে আমরা যে ডিজিট এ আসছি তার limit পর্যন্ত নিতে পারব না সব সংখ্যা নিতে পারব।
০ তম ডিজিট এর জন্য আমরা highest ২ পর্যন্ত generate করতে পারব, আমরা যদি ০ তম ডিজিট এ ২ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ৫ পর্যন্ত genetare করতে পারব, আবার আমরা যদি ০ তম ডিজিট এ ০/১ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ০-৯ পর্যন্ত সব গুল ডিজিট নিয়ে আগাইতে পারব। পরের ডিজিট এর জন্য same কাজ হবে।
আমরা limit এর ২টা value ঠিক করব।
যখন limit == 0 তখন প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব আর limit 0 পাথাব।
আর যখন limit == 1 তখন ঐ ডিজিট এর highest_limit বের করব। প্রতিবার ০ ঠেকে highest_limit এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব। সংখ্যাটা highest_limit এর চে ছোট হলে limit = 0 পাঠাব আর highest_limit এর সমান হলে limit = 1 পাঠাব।
BaseCase:
যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।
যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।
dynamic programming:
function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি।
Friday, June 23, 2017
Given n & sum find all the n digit numbers with sum of digit as sum with no leading zero
1 <= n <=20
1<= sum <= 500000
n টা ডিজিট এর প্রতিটায় ০ - ৯ ১ বার বসিয়ে আমরা মোট n^10 টা সংখ্যা generate করতে পারি। কিন্তু আমাদের বলা হয়েছে যে generate করা সংখ্যাটার প্রথম ডিজিট ০ হতে পারবে না। তাহলে আমরা প্রথম ডিজিটটাকে আলাদা ভাবে handle করব।
1<= sum <= 500000
n টা ডিজিট এর প্রতিটায় ০ - ৯ ১ বার বসিয়ে আমরা মোট n^10 টা সংখ্যা generate করতে পারি। কিন্তু আমাদের বলা হয়েছে যে generate করা সংখ্যাটার প্রথম ডিজিট ০ হতে পারবে না। তাহলে আমরা প্রথম ডিজিটটাকে আলাদা ভাবে handle করব।
আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে n এর কত গুল ডিজিট বাকি আর আমার sum কত টুকু বাকি।
আমরা প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব।
BaseCase:
যদি num_of_digit_left যদি ০ হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।
যদি num_of_digit_left যদি ০ হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।
প্রথম ডিজিটটাকে আলাদা ভাবে handle:
যেহেতু প্রথম ডিজিট ০ হতে পারবে না তাই আমরা প্রথম ডিজিটটাতে ০ ছাড়া বাকি ৯ টা সংখ্যার সবগুলো সংখ্যা নিয়ে একবার আগাবো।
dynamic programming:
আমরা যদি n = ৫ আর sum যে কোন সংখ্যা দিয়ে function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি। (20*500000 = < 10^8 যা ম্যাক্সিমাম কোন array এর সাইজ)
ToDo List June 2K17
(UVA) Corporative Network (dsu)
(UVA) Fibonacci Sum (don't know)
(UVA)10539 - Almost Prime Numbers (number theory) [DONE]
(UVA) 13153 - Number of Connected Components (number theory + bfs/dfs/dsu) [DONE Finally]
DP:
(UVA) 10943 - How do you add? (Non Classical DP (The Easier Ones) [DONE]
(UVA) Matches (Mediam dp) [DONE]
(UVA) Zeros and Ones (Mediam dp) [DONE]
Bitmask DP:
(LOJ) Marriage Ceremonies (bitmask dp)
(UVA) Free Candies (bitmask dp)
Permutation:
(UVA) 10063 - Knuth's Permutation (permutation)
(UVA) 10098 - Generating Fast (permutation)
DIGIT DP:
(SPOJ) LUCIFER - LUCIFER Number (Digit dp) [DONE]
(SPOJ) RAONE - Ra-One Numbers (Digit dp)
(SPOJ) GONE - G-One Numbers (Digit dp)
(SPOJ) NUMTSN - 369 Numbers (Digit dp)
(SPOJ) LOTGAME - New Lottery Game (Digit dp)
(LOJ) Fast Bit Calculations (Digit dp) [DONE]
(LOJ) Investigation (Digit dp) [DONE]
(LOJ) How Many Zeroes (Digit dp) [DONE]
(LOJ) Palindromic Numbers (Digit dp)
(UVA) Fibonacci Sum (don't know)
(UVA)10539 - Almost Prime Numbers (number theory) [DONE]
(UVA) 13153 - Number of Connected Components (number theory + bfs/dfs/dsu) [DONE Finally]
DP:
(UVA) 10943 - How do you add? (Non Classical DP (The Easier Ones) [DONE]
(UVA) Matches (Mediam dp) [DONE]
(UVA) Zeros and Ones (Mediam dp) [DONE]
Bitmask DP:
(LOJ) Marriage Ceremonies (bitmask dp)
(UVA) Free Candies (bitmask dp)
Permutation:
(UVA) 10063 - Knuth's Permutation (permutation)
(UVA) 10098 - Generating Fast (permutation)
DIGIT DP:
(SPOJ) LUCIFER - LUCIFER Number (Digit dp) [DONE]
(SPOJ) RAONE - Ra-One Numbers (Digit dp)
(SPOJ) GONE - G-One Numbers (Digit dp)
(SPOJ) NUMTSN - 369 Numbers (Digit dp)
(SPOJ) LOTGAME - New Lottery Game (Digit dp)
(LOJ) Fast Bit Calculations (Digit dp) [DONE]
(LOJ) Investigation (Digit dp) [DONE]
(LOJ) How Many Zeroes (Digit dp) [DONE]
(LOJ) Palindromic Numbers (Digit dp)
Monday, May 1, 2017
Basic Dp On Tree
Problem:
Given a tree with n nodes we have to find the number of nodes under each sub-tree
The root is 1.
Solution:
we can solve this with dynamic programming
- Determine the bottom nodes of the tree (with no children)
- Assign "weight" 1 to each of the bottom nodes
- Build your way up the tree calculating the "weight" of each node (for example a node with 2 children has "weight" 3)
- That's your answer....
Related Problem:
Degree Of Node
The degree of a vertex V in a graph is defined as the number of graph edges that touches the vertex V.
In a graph,
the total sum of all degree of
vertex = 2 * E [E = number of edge]
For a Tree,
the total sum of all degree of
vertex = 2 * E
= 2 * (n-1)
So if the sum of all degree of
vertex = 2*(n-1) then it must be a tree
Related Problem:
Wednesday, January 18, 2017
Counting Triangles Problem
1307 - Counting Triangles
এ প্রবলেম এ আমাদের কাছে কিছু লাঠির length দিয়ে দিয়েছে। এ length দিয়ে আমারা কত ভাবে একটি valid triangle বানাতে পারি তা বের করতে হবে। একটি valid triangle মানে তার ক্ষেত্রফল ০ এর সমান বা কম হতে পারে না।
আমরা জানি triangle একটি তখনি valid হয় যখন তার ক্ষুদ্রতম দুই বাহুর সমষ্টি বিহতম বাহুরচে বড় হয়।
একটি triangle এর তিন বাহুর যদি a,b,c হয় ও c > a এবং c > v হয়।
তার মানে triangle valid হবে যদি a + b > c হয়। এর জন্য আমারা বাহু গুল কে length অনুজাই sort করে compare করতে পারি।
এ প্রবলেম এ আমাদের কাছে কিছু লাঠির length দিয়ে দিয়েছে। এ length দিয়ে আমারা কত ভাবে একটি valid triangle বানাতে পারি তা বের করতে হবে। একটি valid triangle মানে তার ক্ষেত্রফল ০ এর সমান বা কম হতে পারে না।
আমরা জানি triangle একটি তখনি valid হয় যখন তার ক্ষুদ্রতম দুই বাহুর সমষ্টি বিহতম বাহুরচে বড় হয়।
একটি triangle এর তিন বাহুর যদি a,b,c হয় ও c > a এবং c > v হয়।
তার মানে triangle valid হবে যদি a + b > c হয়। এর জন্য আমারা বাহু গুল কে length অনুজাই sort করে compare করতে পারি।
oshomapto
Subscribe to:
Posts (Atom)
-
This Project has been designed and developed for fulfillment of my 2nd year,1st semester Project Work. Video:
-
Problem Type : BFS , math , greedy , shortest path Problem link: Two Buttons this was a very interesting for me. This problem asks u...
