Web Analytics Certified Course for Your Skill Upgrade and Career

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.

1. Breadth-first Search
2. Depth-first Search
3. Depth-limited Search
4. Iterative deepening depth-first search
5. Uniform cost search
6. Bidirectional Search

1. Breath first Search

• breath first search is a tree and graph search algo it start from root node then expands all successor before going to next level
• All the node in the same level are expand before go to next level
• this algo use FIFO queue as frontier

• BFS is completeness: that mean it will give us the solution if solution exist
• BFS is optimal it will give us a less step solution to get to the goal

Problem with BFS

There is no algorithm that the best each algo has it own advantage and disavantage so base on our problem we need to choose one.

Also in BFS the problem are

• require a lot of memory because all the node in tree was stored
• required more time to complete

Because these problems we have another algo that can reduce the memmory and space complexity for us

2. Uniform cost search

• instead of expand the successor by level we expand the node base on the cost.
• we use pririority queue base on g(n) for this that mean the node with the lowest g(n) will expand first
• goal test will not perform until that node selected for expandsion

Algorithm

step1: initialize a queue with root node with its pririority and a set 
step2: while queue is not empty:
	- remove node highest pririority from queue,add to set
	- if goal return success
	- else add all child to queue with pririority

• It give a lowest path cost solution in weight graph
• It is optimal
• It is complete
• Time complexity

$$time=O(b^x), x=c+1$$

C is a number of depth from root to the goal

n maximum number of child of each o

3.Depth First search

• It start from root node and follow each path until the last depth before moving to next path
• we use LIFO queue (stack)
• Algorithm is similiar to BFS
• time complexity

• It use less memory because it store only the node in one depth
• less time than BFS if take the right path

The problem with DFS

• it will be a loop if the tree is not bounce
• so it will be not complete
• Not optimal

to avoid this loop we have another solution that is Depth limited search

4. Depth Limited Search

• It’s like DFS but what we do is adding limited depth to avoid loop
• It will be terminated if the depth exit the limit
• it is not optimal
• it is not complete if if the solution above the limit
• Not optimal

5. Recursive Depth limited search

• It is like depth limit search but it set the limit again and again until we found the solution

6. Iterative Deepening depth first search

• 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
• Also DFS even it require less space but it take log time to find the solution

That why IDDFS came in. In IDDFS we get the benefit from BFS(time) and DFS(space)

7. Bidirectional Search

• it is an algo that search from both direction simontanously
• start from initial state by forward searching
• also start from goal node by backward searching
• so we can perform 2 algorithm one from intial state and one from goal state
• we can use BFS,DFS,IDDFS in each side