Search techniques

Part of the School of Computer Science

Topic:Artificial intelligence
Artificial intelligence

History of artificial intelligence
Intelligent Agents
Search techniques
Constraint satisfaction
Knowledge Representation and Reasoning
Logical inference
Reasoning under Uncertainty
Decision Making
Learning and neural networks

Bots

* v
* t
* e

Purpose of searching: Find path to desired Goal State from all future states possible.

## Uninformed search

[edit | edit source]

Uninformed search, also called blind search or unguided search, is a class of general purpose search algorithms that operate in a brute-force way. The term 'uninformed'means that they have no additional information about states beyond that provides in the problem definition.These algorithms can be applied to a variety of search problems, since they don't take into account the target problem.

### Breadth-first search

[edit | edit source]

* Each level (or depth) of the search tree is explored before expanding its nodes to search their children. Breadth- first search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors and so on..
* Uses a FIFO QUEUE
* Advantage: Simple to implement
* Disadvantage: Heavy memory requirements

Breadth- first sear

### Depth-first search

[edit | edit source]

* 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)

### Depth-limited search

[edit | edit source]

* Depth-first search with a limit on the depth.
* Depth- first search always expands the deepest node in the current fringe of the search tree.
* 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 .

### Iterative deepening depth-first search

[edit | edit source]

* 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.

### Bidirectional search

[edit | edit source]

* Searches from initial state to last state and also from the last state to initial state, stopping when the two searches meet at a node in between (or when found the goal state).
* Advantage: 1.Time and memory requirements good, comparatively

2.Less time complexity.

* Disadvantage: Not always feasible, or possible, to search backward through possible states.

## Informed search

[edit | edit source]

* 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.

### (Greed) best-first search

[edit | edit source]

* 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.
* advantage:
* Disadvantage: Does not always find the shortest path to the goal.

### A* (A star) search

[edit | edit source]

* 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.

### Self Guided Projects on Search Techniques

[edit | edit source]

1. Uninformed Search Project \- Make a program that can help Homer Simpson find his way around Springfield
2. 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

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template