AI search is about finding a path from a start state to a goal state through a space of possibilities. The space is described by states, actions, a goal test and a step cost. Search strategies differ in which node they expand next, and four properties judge them: completeness (does it always find a solution when one exists?), optimality (does it find the best solution?), time complexity and space complexity.
Uninformed search uses no knowledge about the goal. Breadth-first search (BFS) expands level by level using a queue: it is complete and optimal for uniform step costs, but its memory use, O(b^d) for branching factor b and depth d, is its weakness. Depth-first search (DFS) dives down one path using a stack: it uses only O(bm) memory for maximum depth m, but it is neither complete (it can wander down infinite paths) nor optimal. Iterative deepening combines both: it repeats depth-limited DFS with growing limits, gaining BFS's completeness and optimality with DFS's memory use, at the cost of re-expanding upper levels.
Informed search uses a heuristic, an estimate of the cost to the goal. Greedy best-first search expands the node with the smallest heuristic value h(n) only: fast, but neither complete nor optimal in general. A search expands by f(n) = g(n) + h(n), where g(n) is the cost so far and h(n) the estimated cost to go. A is optimal when the heuristic is admissible (it never overestimates the true cost) and, for graph search, consistent (it obeys the triangle inequality). Admissibility is the single most examined property of A*.
Worked example — A on a tiny map. Start S connects to A with cost 2 and to B with cost 5. A connects to the goal G with cost 2; B connects to G with cost 1. Heuristic values: h(S) = 3, h(A) = 2, h(B) = 1, h(G) = 0. A expands S first (f = 0 + 3 = 3). Its successors have f(A) = 2 + 2 = 4 and f(B) = 5 + 1 = 6, so A expands next, reaching G with total cost 4. B's path would cost 6, so A* correctly finds the optimal route S–A–G with cost 4, even though B is closer to the goal in heuristic terms alone.