Lab 01
Basic Definitions & Uninformed Search
State space — basic concepts
State space
- State: a representation (formulation) of the task in the process of its solution.
- Initial State — presented with S
- Intermediate State — presented with any capital letter except S and G, any state in between
- Goal State — presented with G, if there are more: G1, G2 etc.
- Successor Function (Operator): obtaining one state from another
- Path Cost: additive; e.g., sum of distances, number of actions executed, etc.
- ❗State Space: the totality of all possible states that can be obtained from a given initial state.
A solution is a sequence of actions leading from the initial state to a goal state.
Representation of the State Space
The representation of the state space is a graph or a tree, where each state is represented as a node and the successor function is represented as an edge. When the state space is represented as a tree, it is called a Search Tree.
- The initial state is the root of the tree
- The terminal states and the goal state are represented with leaves
Search strategies evaluation
Strategies are evaluated along the following dimensions:
- Completeness: does it always find a solution if one exists?
- Optimality: does it always find a least-cost solution?
- Time complexity: number of nodes generated/expanded. We are interested in the worst-case scenario.
- Space Complexity: maximum number of nodes in memory.
Time and space complexity are measured in terms of:
- b – maximum branching factor of the search tree
- d – depth of the least-cost solution
- m – maximum depth of the state space (may be ∞)
Explore the search tree
This is the example tree used throughout the lab. S is the initial state; the dashed nodes G1 and G2 are goal states. Click any node to inspect it, or turn on the b / d / m overlay.
Global search vs. local search
Global Search vs Local Search
- Global Search: search strategies that look all over the state space. If necessary, all states will be traversed.
- Local Search: they only look at the local area, so they can only look at states in this area. If the solution is outside of it, they will not be able to find it.
Generally, Local Search is not used for finding a path from state A to state B.
Local Search
- Local Search in Artificial Intelligence is an optimizing algorithm to find the optimal solution more quickly.
- Local search algorithms are used when we care only about a solution but not the path to a solution.
- Local search is a heuristic method for solving computationally hard optimization problems.
- Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions.
- Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.
Uninformed (Blind) Search
Uninformed Search Strategies
Uninformed strategies use only the information available in the problem definition. They have no information where the goal state might be (if one exists).
- Uninformed Search Strategies:
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
- Uniform-Cost Search (UCS)
- Depth-Limited Search (DLS)
- Iterative Deepening Search (IDS)
DFS — Depth-First Search
Go Deep First: DFS explores as far as possible down one branch of a tree or graph before it backtracks. It's like exploring a maze by always choosing the first available path until you hit a dead end.
Example of an infinite space: find a sequence of actions to transform an initial positive integer N into a target integer T, using only:
- Operation A: "Subtract 1" (x → x−1)
- Operation B: "Multiply by 2" (x → 2x)
- Start node (N): 5 — Target node (T): 10
- Why O(bm) space? The storage for the current path, at most m: O(m).
- Whenever we visit a node we generate its neighbours, which are at most b. So for each of the at most m nodes on the path, we've generated at most b nodes — so we keep at most b·m nodes in memory.
Stack (next pop from the right)
Search log
BFS — Breadth-First Search
b0 + b1 + ... + bd + b(bd − 1) = O(bd+1) If the goal state is the last one at level d, we would visit all nodes up to level d and would generate at most b children of each node of level d, except for the goal state.
Queue (next pop from the left)
Search log
UCS — Uniform-Cost Search
Description: Uniform cost search (UCS) is a strategy for exploration that always selects the lowest-cost frontier node from the start node for expansion.
Frontier Representation: the choice is usually a heap-based priority queue, where the priority for a given enqueued node v is the path cost from the start node to v. A priority queue built this way simply reshuffles itself to maintain the desired ordering by path cost as we remove the current minimum-cost path and replace it with its children.
Let us define the optimal path cost as C*, and the minimal cost between two nodes in the state space graph as ε.
Since we explore nodes in order of increasing path cost, we're guaranteed to find the lowest-cost path to a goal state. The strategy behind UCS is identical to Dijkstra's algorithm — the main difference is that UCS terminates as soon as it finds a solution state, instead of finding the shortest path to all states.
Priority queue (next pop = lowest cost)
Search log
DLS — Depth-Limited Search
= depth-first search with a depth limit l — nodes at depth level l have no successors. It's DFS with a fence: once a branch reaches depth l, DLS stops digging there and backtracks, whether or not that's actually the bottom of the real tree.
With l = 2, C/D/E/F (depth 2) are treated as if they were leaves — G through N (depth 3) are never generated, even though they exist in the real tree.
IDS — Iterative Deepening Search
Iterate over the limit l in Depth-Limited Search: run DLS with l = 0, then l = 1, then l = 2, ... — restarting from the root each time — until a goal is found. Each restart throws away the previous iteration's work, but it's the price paid for DFS's small memory footprint with BFS's level-by-level completeness.
Optimality's key: since each iteration explores level-by-level up to its limit, the first iteration to find a goal finds it at the shallowest possible depth — just like BFS, but without keeping every level in memory at once.
Stack (this iteration only)
Search log
Complexity simulator
- b = branching factor (breadth)
- d = depth of the shallowest solution
- m = maximum depth of the state space
Drag the sliders and watch how many nodes each strategy has to generate — and how much memory it needs.
Nodes generated (time complexity)
Peak nodes in memory (space complexity)
UCS is drawn using d as a stand‑in for ⌈C*/ε⌉ (the number of "cost steps" to the optimal goal) — with unit step costs the two coincide. If m < d, DFS can't reach the solution at all.
IDS vs BFS
Let b = 10 and d = 5, solution at the far-right leaf.
BFS time complexity is calculated the following way: b0 + b1 + ... + bd + b(bd − 1)
IDS time complexity is calculated the following way: (d+1)b0 + db1 + ... + bd
Let's compare IDS and BFS numerically:
Nodes generated to find the goal — IDS does the same job with about 9× fewer node expansions.
- IDS does better because other nodes at depth d are not expanded.
- BFS can be modified to apply the goal test when a node is generated (not when it's expanded) to close some of this gap.
Summary of algorithms
| Algorithm | Complete | Optimal | Time | Space | Data structure |
|---|---|---|---|---|---|
| Depth‑First Search (DFS) | No | No | O(b^m) | O(bm) | Stack |
| Breadth‑First Search (BFS) | Yes* (b ≤ ∞) | Yes* (unit cost) | O(b^(d+1)) | O(b^(d+1)) | Queue |
| Uniform‑Cost Search (UCS) | Yes | Yes | O(b^⌈C*/ε⌉) | O(b^⌈C*/ε⌉) | Priority queue |
| Depth‑Limited Search (DLS) | Yes* (l ≥ d) | No | O(b^l) | O(bl) | Stack |
| Iterative Deepening (IDS) | Yes | Yes* (unit cost) | O(b^d) | O(bd) | Stack |
14 auto-graded tasks, 100 points: b / d / m, complexity, tracing BFS, DFS, DLS, IDS and UCS, and choosing an algorithm.