Course contentsShow
← Computer Science
Lesson 2733 of 2,87261. AI and Search AlgorithmsFree lesson

Frontier and Explored Sets

Managing the collection of states to explore next and tracking visited states to avoid redundant work.

Frontier and Explored Sets

What you'll learn: How AI search algorithms manage which states to visit next and remember which states they've already seen.

The Core Idea

When an AI agent explores a state space (like finding a route on a map or solving a puzzle), it needs two crucial data structures:

  1. The Frontier (or "Open Set"): States you've discovered but haven't explored yet—these are candidates for your next move
  2. The Explored Set (or "Closed Set"): States you've already visited and processed

Think of it like exploring a maze: the frontier is your mental list of "hallways I spotted but haven't walked down yet," while the explored set is "places I've already been—no need to backtrack there."

Why Both Matter

Without tracking explored states, you'd waste time revisiting the same state repeatedly (imagine checking the same intersection over and over). Without a frontier, you'd have no systematic way to continue your search.

The frontier determines what you explore next. Its organization (queue, stack, priority queue) defines your search strategy—breadth-first, depth-first, or best-first.

The explored set prevents redundant work. Before adding a successor state to the frontier, you check: "Have I seen this before?" If yes, skip it.

Typical Workflow

  1. Start with the initial state in the frontier
  2. Remove a state from the frontier to explore
  3. Add it to the explored set
  4. Generate successor states
  5. For each successor: if not in explored set and not already in frontier, add to frontier
  6. Repeat until you find the goal or exhaust possibilities

Key Takeaway: The frontier queues states awaiting exploration while the explored set prevents revisiting known states, together ensuring efficient, systematic search through a state space.