//Search
//Informed Search
//Uninformed Search
//Overview of Breadth First Search and Depth First Search
//Overview of A* and Best First Search
/*
Video link : https://youtu.be/AHO7BFfvRc8
*/
1)Search :
a)A search algorithm is an algorithm for finding an item with the specified properties among a collection of items.
b)The items may be stored as records in a database or as elements in a search space defined by a mathematical formula or a combination of both.
c)The required item or the item with the specified properties can be called the goal state.
d)The search is complete once we reach the goal state or there are no more elements to search.
e)There are two types of search algorithms :
i)Uninformed search.
ii)Informed search.
2)Uninformed Search:
a)As the name suggests these kind of searches have no extra information.
b)The only available information is which nodes can it move to from the current nodes, which nodes have been visited.
c)Uninformed search do not contain any information regarding how far we are from the goal state or how long will it take to reach the goal state.
d)It is a brute force kind of search.
e)In this type of search we keep searching till we get the goal node or we exhaust the search space regardless of whether we are going in the correct direction.
f)Examples:
i)Breadth First Search:
Uses queues
Traverses the tree level by level
In BFS it is guaranteed that a solution will be found if a solution exists.
Time complexity: O(b^d) where b is the branching factor and d is the depth of the tree.
Space complexity : O(b^d) where b is the branching factor and d is the depth of the tree.
ii) Depth First Search:
Uses stacks.
Traverses one path completely to find solution, if solution is not found it goes to the next path.
In DFS it is not guaranteed that a solution will be found.
Time complexity: O(b^d) where b is the branching factor and d is the depth of the tree.
Space complexity : O(bd) where b is the branching factor and d is the depth of the tree.
g)Other examples are
Depth-Limited Search
Depth-First Iterative Deepening
Uniform Cost Search
Backwards Chaining
Bidirectional Search
3)Informed Search:
a)As the name suggests these kind of searches have extra information.
b)The are also called Heuristic Search.
c)Informed search contain a heuristic function which returns how far the current node is from the goal node.
d)In this type of search we use the data provided by the Heuristic function and take th correct decision and move towards the goal state.
e)This is not a brute force method and at each iteration we go closer and closer to the goal node.
f)Examples:
i)Best First Search:
Uses only heuristic function
It uses two lists
Open List
Closed List
i)Initially we put the root node into the open list.
ii)The nodes that can be reached from the current node are added to the open list.
iii)Then the node which has the lowest heuristic that can be reached from the current node is chosen
iv)Once a node is traversed its put it into the closed list and removed from the open list.
v)We stop when we find the goal node or the open list is empty
ii)A*:
Uses f(n) where f(n)=g(n)+h(n)
here,
g(n) is actual distance from previous node current node,
h(n) is heuristic function of current node.
Using f(n) each node is evaluated.
Two lists are used
Open List
Closed List
We use a priority Queue in A* algorithm.
The node with the lowest value of f(n) in the open list is expanded will we get a solution or until there are no more nodes to search.
g)Other examples are
Recursive Best First Search
AO*
Beam Search
Iterative Deepening A*
4)Difference between Informed and Uninformed Search:
a)Informed Searches are much more efficient.
b)Informed Searches are not brute force and expand in a direction towards the goal node.
c)Informed Searches have smaller/better time complexity compared to the Uninformed Searches.
//Informed Search
//Uninformed Search
//Overview of Breadth First Search and Depth First Search
//Overview of A* and Best First Search
/*
Video link : https://youtu.be/AHO7BFfvRc8
*/
1)Search :
a)A search algorithm is an algorithm for finding an item with the specified properties among a collection of items.
b)The items may be stored as records in a database or as elements in a search space defined by a mathematical formula or a combination of both.
c)The required item or the item with the specified properties can be called the goal state.
d)The search is complete once we reach the goal state or there are no more elements to search.
e)There are two types of search algorithms :
i)Uninformed search.
ii)Informed search.
2)Uninformed Search:
a)As the name suggests these kind of searches have no extra information.
b)The only available information is which nodes can it move to from the current nodes, which nodes have been visited.
c)Uninformed search do not contain any information regarding how far we are from the goal state or how long will it take to reach the goal state.
d)It is a brute force kind of search.
e)In this type of search we keep searching till we get the goal node or we exhaust the search space regardless of whether we are going in the correct direction.
f)Examples:
i)Breadth First Search:
Uses queues
Traverses the tree level by level
In BFS it is guaranteed that a solution will be found if a solution exists.
Time complexity: O(b^d) where b is the branching factor and d is the depth of the tree.
Space complexity : O(b^d) where b is the branching factor and d is the depth of the tree.
ii) Depth First Search:
Uses stacks.
Traverses one path completely to find solution, if solution is not found it goes to the next path.
In DFS it is not guaranteed that a solution will be found.
Time complexity: O(b^d) where b is the branching factor and d is the depth of the tree.
Space complexity : O(bd) where b is the branching factor and d is the depth of the tree.
g)Other examples are
Depth-Limited Search
Depth-First Iterative Deepening
Uniform Cost Search
Backwards Chaining
Bidirectional Search
3)Informed Search:
a)As the name suggests these kind of searches have extra information.
b)The are also called Heuristic Search.
c)Informed search contain a heuristic function which returns how far the current node is from the goal node.
d)In this type of search we use the data provided by the Heuristic function and take th correct decision and move towards the goal state.
e)This is not a brute force method and at each iteration we go closer and closer to the goal node.
f)Examples:
i)Best First Search:
Uses only heuristic function
It uses two lists
Open List
Closed List
i)Initially we put the root node into the open list.
ii)The nodes that can be reached from the current node are added to the open list.
iii)Then the node which has the lowest heuristic that can be reached from the current node is chosen
iv)Once a node is traversed its put it into the closed list and removed from the open list.
v)We stop when we find the goal node or the open list is empty
ii)A*:
Uses f(n) where f(n)=g(n)+h(n)
here,
g(n) is actual distance from previous node current node,
h(n) is heuristic function of current node.
Using f(n) each node is evaluated.
Two lists are used
Open List
Closed List
We use a priority Queue in A* algorithm.
The node with the lowest value of f(n) in the open list is expanded will we get a solution or until there are no more nodes to search.
g)Other examples are
Recursive Best First Search
AO*
Beam Search
Iterative Deepening A*
4)Difference between Informed and Uninformed Search:
a)Informed Searches are much more efficient.
b)Informed Searches are not brute force and expand in a direction towards the goal node.
c)Informed Searches have smaller/better time complexity compared to the Uninformed Searches.
No comments:
Post a Comment