Search techniques

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

Uninformed search

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

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

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

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

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

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

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

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

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

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