{"id":22430,"date":"2021-02-12T09:11:37","date_gmt":"2021-02-12T00:11:37","guid":{"rendered":"https:\/\/www.waca.associates\/en\/?p=22430"},"modified":"2021-03-22T08:52:52","modified_gmt":"2021-03-21T23:52:52","slug":"kit-popular-uniform-search-algorithm","status":"publish","type":"post","link":"https:\/\/www.waca.or.jp\/en\/growthhacking\/kit-popular-uniform-search-algorithm\/","title":{"rendered":"[KIT] Popular Uniform search Algorithm"},"content":{"rendered":"
Uniform search algorithm is an algorithm that has no additional info about the state beside from problem definition. In this article i will bring you to a brief introduction of some popular uninform search algorithms.<\/p>
instead of expand the successor by level we expand the node base on the cost.<\/li>
we use pririority queue base on g(n) for this that mean the node with the lowest g(n) will expand first<\/li>
goal test will not perform until that node selected for expandsion<\/li><\/ul>
Algorithm<\/h2>
step1: initialize a queue with root node with its pririority and a set \nstep2: while queue is not empty:\n\t- remove node highest pririority from queue,add to set\n\t- if goal return success\n\t- else add all child to queue with pririority\n\n<\/code><\/pre>
It give a lowest path cost solution in weight graph<\/li>
It is optimal<\/li>
It is complete<\/li>
Time complexity<\/li><\/ul>
$$time=O(b^x), x=c+1$$<\/p>
C is a number of depth from root to the goal<\/p>
n maximum number of child of each o<\/p>
3.Depth First search<\/h2><\/figure>
It start from root node and follow each path until the last depth before moving to next path<\/li>
we use LIFO queue (stack)<\/li>
Algorithm is similiar to BFS<\/li>
time complexity<\/li><\/ul>
It use less memory because it store only the node in one depth<\/li>
less time than BFS if take the right path<\/li><\/ul>
The problem with DFS<\/h3>
it will be a loop if the tree is not bounce<\/li>
so it will be not complete<\/li>
Not optimal<\/li><\/ul>
to avoid this loop we have another solution that is Depth limited search<\/p>
4. Depth Limited Search<\/h2><\/figure>
It’s like DFS but what we do is adding limited depth to avoid loop<\/li>
It will be terminated if the depth exit the limit<\/li>
it is not optimal<\/li>
it is not complete if if the solution above the limit<\/li>
Not optimal<\/li><\/ul>
5. Recursive Depth limited search<\/h2>
It is like depth limit search but it set the limit again and again until we found the solution<\/li><\/ul>
6. Iterative Deepening depth first search<\/h2>
As we know it BFS even it is fast but it require a lot of space to store the node because it store all the node in the level to the queue<\/li>
Also DFS even it require less space but it take log time to find the solution<\/li><\/ul><\/figure>
That why IDDFS came in. In IDDFS we get the benefit from BFS(time) and DFS(space)<\/p>
7. Bidirectional Search<\/h2>
it is an algo that search from both direction simontanously<\/li>
start from initial state by forward searching<\/li>
also start from goal node by backward searching<\/li>
so we can perform 2 algorithm one from intial state and one from goal state<\/li>
we can use BFS,DFS,IDDFS in each side<\/li><\/ul>","protected":false},"excerpt":{"rendered":"Uniform search algorithm is an algorithm that has no additional info about the state beside from problem defin […]","protected":false},"author":718,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[169],"tags":[],"class_list":["post-22430","post","type-post","status-publish","format-standard","hentry","category-growthhacking"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/posts\/22430"}],"collection":[{"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/users\/718"}],"replies":[{"embeddable":true,"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/comments?post=22430"}],"version-history":[{"count":1,"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/posts\/22430\/revisions"}],"predecessor-version":[{"id":22437,"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/posts\/22430\/revisions\/22437"}],"wp:attachment":[{"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/media?parent=22430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/categories?post=22430"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.waca.or.jp\/en\/wp-json\/wp\/v2\/tags?post=22430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"https:\/\/www.waca.associates\/en\/wp-content\/uploads\/2021\/02\/Animated_BFS-1-1.gif\")
<\/figure>![\"\"](\"https:\/\/www.waca.associates\/en\/wp-content\/uploads\/2021\/02\/Algorithm-1-1.png\")
![\"\"](\"https:\/\/www.waca.associates\/en\/wp-content\/uploads\/2021\/02\/dfs.gif\")
<\/figure>![\"\"](\"https:\/\/www.waca.associates\/en\/wp-content\/uploads\/2021\/02\/s.png\")
<\/figure>![\"\"](\"https:\/\/www.waca.associates\/en\/wp-content\/uploads\/2021\/02\/w-1024x420.png\")
<\/figure>