10.19 Modeling State-Space Problems as Shortest Paths

One of the most powerful ideas in algorithm design is that many problems that do not look like graph problems can be transformed into shortest-path problems.

A maze is obviously a graph.

A puzzle is less obvious.

A scheduling problem is even less obvious.

A string transformation problem may not appear graph-related at all.

Yet many of these problems become straightforward once we identify:

• States
• Transitions
• Costs

The resulting structure is called a state-space graph.

This recipe shows how to model complex problems as shortest-path searches by treating states as vertices and valid actions as edges.

Problem

Given a problem involving transformations, moves, decisions, or configurations, model it as a shortest-path problem and find an optimal solution.

Consider:

Start: 1

Operations:
×2
+1

Target: 11

We want the minimum number of operations required to reach:

11

from:

1

The problem does not initially resemble a graph.

Solution

Treat each reachable value as a vertex.

Valid operations become edges.

1 -> 2
1 -> 2
2 -> 3
2 -> 4
3 -> 4
3 -> 6
...

Once the graph exists, ordinary BFS finds the minimum number of operations.

package main

import "fmt"

func minOperations(start int, target int) int {
	limit := target * 2

	dist := make([]int, limit+1)

	for i := range dist {
		dist[i] = -1
	}

	queue := []int{start}
	dist[start] = 0

	head := 0

	for head < len(queue) {
		current := queue[head]
		head++

		if current == target {
			return dist[current]
		}

		nextStates := []int{
			current + 1,
			current * 2,
		}

		for _, next := range nextStates {
			if next < 0 || next > limit {
				continue
			}

			if dist[next] != -1 {
				continue
			}

			dist[next] = dist[current] + 1
			queue = append(queue, next)
		}
	}

	return -1
}

func main() {
	fmt.Println(
		minOperations(1, 11),
	)
}

Output:

5

The shortest sequence is:

1
2
4
5
10
11

The original optimization problem has become a shortest-path problem.

Understanding State Graphs

A state graph contains:

Vertices = states
Edges = valid transitions

For example:

State: current number

produces:

1
2
3
4
...

as vertices.

Transitions:

+1
×2

produce edges.

1 -> 2
2 -> 3
2 -> 4
3 -> 4
3 -> 6
...

BFS naturally finds the shortest sequence of operations.

The key observation is that the graph need not exist explicitly.

We generate neighbors dynamically.

The State Modeling Process

Most state-space problems can be modeled using four questions.

What Is a State?

A state must contain enough information to describe the current situation.

Examples:

Current position
Current configuration
Current inventory
Current score
Current resources

What Are the Valid Moves?

Moves transform one state into another.

Examples:

Move left
Move right
Pick up key
Open door
Change configuration

What Is the Cost?

Costs determine the shortest-path algorithm.

Uniform cost -> BFS
0/1 cost -> 0-1 BFS
Nonnegative cost -> Dijkstra
Negative cost -> Bellman-Ford

What Is the Goal?

The goal defines termination.

Reach destination
Solve puzzle
Transform string
Complete schedule

Once these elements exist, graph search becomes possible.

Example: Word Transformation

Suppose:

hit

must become:

cog

Changing one character at a time.

Valid words:

hit
hot
dot
dog
lot
log
cog

State:

Current word

Transition:

Change one character

Graph:

hit -> hot
hot -> dot
hot -> lot
dot -> dog
lot -> log
dog -> cog
log -> cog

BFS finds:

hit
hot
dot
dog
cog

The shortest transformation sequence.

The graph is implicit.

Neighbors are generated when needed.

Example: Sliding Puzzle

Consider:

1 2 3
4 5 6
7 _ 8

Goal:

1 2 3
4 5 6
7 8 _

State:

Entire board configuration

Transition:

Move blank tile

Graph:

Configuration A
  ->
Configuration B
  ->
Configuration C

BFS finds the minimum number of moves.

The graph may contain thousands or millions of states, but only a small fraction are explored.

Example: Robot Navigation with Keys

Maze:

S . a
# # .
A . G

Where:

• a is a key
• A is a locked door

A position alone is insufficient.

These states differ:

(1,2,no key)

(1,2,have key)

The state becomes:

(row, col, keyMask)

A three-dimensional state space.

The graph search remains unchanged.

Only the state representation becomes richer.

Why State Definition Matters

Incorrect state modeling causes incorrect solutions.

Suppose we ignore keys.

(row, col)

The algorithm may conclude:

Door already passable.

which is false.

The search loses essential information.

A useful rule is:

Two situations belong to the same state only if every future decision is identical.

If future possibilities differ, the states must remain distinct.

Implicit Versus Explicit Graphs

Most state-space graphs are enormous.

Consider a chess position.

The number of possible states is astronomical.

Building the full graph is impossible.

Instead:

func neighbors(state State) []State

generates adjacent states on demand.

Search algorithms only explore reachable portions.

This approach is essential for large state spaces.

Weighted State Spaces

Some transitions cost more than others.

Example:

Walk = 1
Run = 2
Jump = 3

Now BFS is no longer correct.

The graph becomes weighted.

Dijkstra is appropriate.

The modeling process remains identical.

Only the search algorithm changes.

This flexibility is one reason shortest-path techniques are so widely applicable.

State Compression

State spaces often contain redundant information.

Consider:

10 keys

A naive representation:

[]bool

requires more memory.

A bitmask representation:

uint16

stores all keys efficiently.

0000000000
0000000001
0000000011
...

Bitmasks appear frequently in:

• Puzzle solvers
• Route planning
• Dynamic programming
• State-space search

Compact states improve both memory usage and performance.

Discussion

State-space modeling is often more difficult than the search algorithm itself.

The algorithm is usually familiar:

BFS
Dijkstra
A*

The challenge is deciding:

What is a state?

Strong problem solvers spend most of their effort on modeling rather than on implementation.

Once the correct graph exists, the search often becomes straightforward.

This pattern appears repeatedly in algorithm design.

Complexity

Suppose:

N = number of reachable states
M = number of transitions

Then:

Algorithm	Complexity
BFS	O(N + M)
0-1 BFS	O(N + M)
Dijkstra	O((N + M) log N)
A*	Depends on heuristic
Bellman-Ford	O(NM)

Notice that complexity depends on state count rather than the original problem description.

Reducing state space is often the most important optimization.

Common Mistakes

Do not define states too narrowly. Missing information usually produces incorrect solutions.

Do not define states too broadly. Unnecessary information causes state explosion.

Do not build the entire graph when neighbor generation is possible.

Do not ignore costs when transitions have different weights.

Do not forget visited-state tracking. Cycles frequently appear in state-space graphs.

Practical Applications

State-space shortest paths appear in:

• Puzzle solving
• Robotics
• AI planning
• Compiler optimization
• Game search
• Route planning
• Resource scheduling
• Configuration management
• Automated reasoning
• Workflow optimization

Many seemingly unrelated optimization problems are actually state-space shortest-path problems in disguise.

Takeaway

State-space modeling transforms complex optimization problems into graph-search problems. The central task is identifying states, transitions, costs, and goals. Once these elements are defined, familiar shortest-path algorithms such as BFS, Dijkstra, or A* can often solve problems that initially appear unrelated to graph theory. In practice, the quality of the state representation usually matters more than the specific search algorithm used afterward.