Search techniques
From Wikiversity
Artificial Intelligence: History of AI | Intelligent Agents | Search techniques | Constraint Satisfaction | Knowledge Representation and Reasoning | Logical Inference | Reasoning under Uncertainty | Decision Making | Learning and Neural Networks | Bots
Purpose of searching: Find path to desired Goal State from all future states possible.
Contents |
[edit] Uninformed search
- Only a successor function is available to get the children of a state.
- Uses these states to continue search
[edit] Breadth-first search
- Each level (or depth) of the search tree is explored before expanding its nodes to search their children.
- Uses a FIFO QUEUE
- Advantage: Simple to implement
- Disadvantage: Heavy memory requirements
[edit] Depth-first search
- Drills deep into the hierarchy, exploring one lineage until it reaches the child/leaf node with no successors (or it's goal, of course).
- Advantage: Improves on the memory requirements by deleting entire line once explored.
- Disadvantage: Potential to run into infinitely deep search path (non-complete)
[edit] Depth-limited search
- Depth-first search with a limit on the depth.
- Mitigates infinite depth path of Depth-first search by cutting the tree on the limit depth
- Will fail to reach goal if goal resides deeper than depth limit .
[edit] Iterative deepening depth-first search
- Performs iterations of depth-limited searches with increasing depth limits.
- Advantage: Unlike normal depth-first search and depth-limited search, it is complete. It also does this without greatly increasing the expected runtime.
[edit] Bidirectional search
- Searches from initial state to goal state and also from goal state backward to initial state, stopping when the two searches meet at a node in between.
- Advantage: Time and memory requirements good, comparatively
- Disadvantage: Not always feasible, or possible, to search backward through possible states.
[edit] Informed search
- If information is available about the problem this could guide the search (for example in finding the shortest route in a map: information about distances between places on map).
- Information is put in an evaluation function f(n) to be able to give a value to each state.
- Sometimes a heuristic function h(n) is used to guess the value if the information isn't perfect.
[edit] (Greedy) best-first search
- Define f(n) to be the distance to the goal (Or a good guess to the goal h(n), then f(n)=h(n)).
- Expand child with lowest f(n) value.
- Disadvantage: Does not always find the shortest path to the goal.
[edit] A* (A star) search
- Define f(n) to be the distance to the current state plus the expected distance to the goal: f(n) = g(n) + h(n).
- h(n) must be an admissible heuristic, ie it doesn't overestimate the distance to the goal.
- Expand child with lowest f(n) value.
- Advantage: Always finds most optimal solution.
[edit] Self Guided Projects on Search Techniques
- Uninformed Search Project - Make a program that can help Homer Simpson find his way around Springfield
- Simulated Annealing and Gradient Descent - Use simulated annealing to find the correct placement of baby lizards in a nursery so that they can't eat each other
