What is the difference between informed and uninformed searches?

An uninformed search is a brute-force or "blind" search. It uses no knowledge about problem, hence possibly less efficient than an informed search.

Examples of uninformed search algorithms are breadth-first search, depth-first search, depth-limited search, uniform-cost search, depth-first iterative deepening search and bidirectional search.

An informed search (also called "heuristic search") uses prior knowledge about problem ("domain knowledge"), hence possibly more efficient than uninformed search.

Examples of informed search algorithms are best-first search and A*.

Blind or Uniformed Search

It is a search without "information" about the goal node.

An example an is breadth-first search (BFS). In BFS, the search proceeds one layer after the other. In other words, nodes in the same layer are first visited before nodes in successive layers. This is performed until a node that is "expanded" is the goal node. In this case, no information about the goal node is used to visit, expand or generate nodes.

We can think of a blind or uniformed search as a brute-force search.

Heuristic or Informed Search

It is a search with "information" about the goal.

An example of such type of algorithm is A*. In this algorithm, nodes are visited and expanded using also information about the goal node. The information about the goal node is given by an heuristic function (which is a function that associates information about the goal node to each of the nodes of the state space). In the case of A*, the heuristic information associated with each node n is an estimate of the distance from n to the goal node.

We can think of a informed search as a approximately "guided" search.