All search strategies are distinguished by the order in which nodes are expanded
1. Uniformed search method (Blind search) have access only the problem definition.
- Breadth-first search
- Uniform-cost search
- Depth-first search
- Iterative deepening search
- Bidirectional search
2. Informed search methods may have access to a heuristic function h(n) that estimate the cost of a solution from n.
- Greedy best-first search
- A* search
- Recursive best-first search (RBFS) search
Uninformed Search
Sometimes we may not get much relevant information to solve a problem.
Suppose we lost our car key and we are not able to recall where we left, we have to search for the key with some information such as in which places we used to place it. It may be our pant pocket or may be the table drawer. It it is not there then we have to search the whole house to get it.The best solution would be to search in the places from the table to the wardrobe.Here we need to search blindly with less clue.
This type of search is called uninformed search or blind search.
Uninformed Search and Exploration
Blind search - BFS, DFS, uniform cost
- no notion concept of the "right direction"
- can only recognize goal once it's achieved
Informed Search
We can solve the problem in an efficient manner if we have relevant information, clues or hints. The clues that help solve the problem constitute heuristic information.
Informed search is also heuristic search.
Instead of searching one path or many paths just like that informed search uses the given heuristic information to decide whether or not to explore the current state further.
Add domain-specific information to select the best path along which to continue searching
Define a heuristic function, h(n), that estimates the "goodness" of a node n.
Specifically, h(n) = estimated cost (or instance) of minimal cost path from n to a goal state.
The heuristic function is an estimate, based on domain-specific information that is computable from the current state description, of how close we are to a goal.
1. Uniformed search method (Blind search) have access only the problem definition.
- Breadth-first search
- Uniform-cost search
- Depth-first search
- Iterative deepening search
- Bidirectional search
2. Informed search methods may have access to a heuristic function h(n) that estimate the cost of a solution from n.
- Greedy best-first search
- A* search
- Recursive best-first search (RBFS) search
Uninformed Search
Sometimes we may not get much relevant information to solve a problem.
Suppose we lost our car key and we are not able to recall where we left, we have to search for the key with some information such as in which places we used to place it. It may be our pant pocket or may be the table drawer. It it is not there then we have to search the whole house to get it.The best solution would be to search in the places from the table to the wardrobe.Here we need to search blindly with less clue.
This type of search is called uninformed search or blind search.
Uninformed Search and Exploration
Blind search - BFS, DFS, uniform cost
- no notion concept of the "right direction"
- can only recognize goal once it's achieved
Informed Search
We can solve the problem in an efficient manner if we have relevant information, clues or hints. The clues that help solve the problem constitute heuristic information.
Informed search is also heuristic search.
Instead of searching one path or many paths just like that informed search uses the given heuristic information to decide whether or not to explore the current state further.
Add domain-specific information to select the best path along which to continue searching
Define a heuristic function, h(n), that estimates the "goodness" of a node n.
Specifically, h(n) = estimated cost (or instance) of minimal cost path from n to a goal state.
The heuristic function is an estimate, based on domain-specific information that is computable from the current state description, of how close we are to a goal.
.png)
No comments:
Post a Comment