Search Algorithms

Properties of Search Algorithms

Completeness

Completeness is whether or not the algorithm is guaranteed to find a goal (provided at least one goal exists).

Optimality

Optimality is whether or not the algorithm is guaranteed to find the shallowest goal (i.e. the goal with the lowest cost).

Time Complexity

Time Complexity refers to the degree of time consumed by the algorithm.

Space Complexity

Space Complexity refers to the degree of memory space consumed by the algorithm.

Search Tree Terminology

Node: a state in the search problem

Edge: an action or a transition between states in the search problem

Branching Factor, $b$$\large b$: the maximum number of child nodes extending from a parent node

Shallowest Goal Depth, $d$$\large d$: the number of edges to the shallowest goal node

Maximum Depth, $m$$\large m$: the number of edges to the further node

Heuristics

Heuristics are solution strategies by trial and error used to produce acceptable (optimal or sub-optimal) solutions to complex problems in a reasonably practical time. Heuristics aim to efficiently generate good solutions, but does not guarantee optimality. Heuristics:

• have short running times
• are easy to implement
• are flexible
• are simple

A heuristic function $h(n)$$\large h(n)$ is one that uses domain knowledge and estimates the goodness of node $n$$\large n$. It is the estimated cost of the minimal cost path from node $n$$\large n$ to a goal node.

Admissible Heuristic

An admissible heuristic function is one that never overestimates the cost of reaching a goal:

where $h^{\ast }(n)$$\large h^*(n)$ is the true cost of the minimal cost path from node $n$$\large n$ to a goal node.

Breadth-First Search

Breadth-First Search involves searching the tree by expanding nodes into a queue data structure.

Search Path: $A\to B\to C\to D\to E\to F$$\large A \rarr B \rarr C \rarr D \rarr E \rarr F$

Depth-First Search

Depth-First Search involves searching the tree by expanding nodes into a stack data structure.

Search Path: $A\to B\to D\to E\to C\to F$$\large A \rarr B \rarr D \rarr E \rarr C \rarr F$

Uniform-Cost Search

Uniform Cost Search involves searching the tree by expanding nodes into a priority queue data structure based on the cost of the path to each node.

Search Path: $A\to C\to F\to B\to D\to E$$\large A \rarr C \rarr F \rarr B \rarr D \rarr E$

$C^{\ast }$$\large C^*$ and $ϵ$$\large \epsilon$ are costs of the goal path and the minimum cost of all the other edges respectively in the worst case scenario.

Depth-Limited Search

Depth-Limited Search involves searching the tree using Depth-First Search, but limiting the maximum expanded depth to an upper bound $l$$\large l$.

Search Path $(l=2)$$(\large l = 2)$: $A\to B\to C$$\large A \rarr B \rarr C$

Iterative-Deepening Search

Iterative-Deepening Search involves searching the tree using Depth-Limited Search using incremental values of $l$$l$.

Search Path $(l=1)$$(l = 1)$: $A$$\large A$

Search Path $(l=2)$$(l = 2)$: $A\to B\to C$$\large A \rarr B \rarr C$

Search Path $(l=3)$$(l = 3)$: $A\to B\to D\to E\to C\to F$$\large A \rarr B \rarr D \rarr E \rarr C \rarr F$

Greedy Search

Greedy Search involves running Best-First Search with an evaluation function $f(n)=h(n)$$\large f(n) = h(n)$, where $h(n)$$\large h(n)$ is the heuristic function.

Beam Search

Beam Search involves storing and expanding the $\beta$$\large \beta$ best nodes at each depth to a queue data structure. $\beta$$\large \beta$ is the beam width.

A* Search

A* Search involves running Best-First Search with an evaluation function $f(n)=g(n)+h(n)$$\large f(n) = g(n) + h(n)$, where $g(n)$$\large g(n)$ is the cost function.

Hill-Climbing Search

Hill-Climbing involves always traversing the node that decreases $h(n)$$\large h(n)$.

Max-Min Strategy

Max-Min Strategy (or the minimax algorithm) is a recursive backtracking algorithm that chooses the maximum or minimum value of the child nodes at any node.