Decision Trees and State Graphs

Decision Trees

A decision tree is a rooted tree that models a sequence of decisions, where:
- Each internal node represents a decision point (question/choice)
- Each edge represents a possible outcome/answer
- Each leaf node represents a final outcome or solution

Structure

                     [Start]
                    /       \
             [Choice A]  [Choice B]
            /     \           \
         [A1]    [A2]        [B1]

Properties

• Trees (acyclic, connected)
• Depth of tree = number of sequential decisions
• Number of leaves ≤ branching_factor^depth (exponential growth)

Applications in VCE Algorithmics

• Combinatorial search: Enumerate all solutions (e.g., all permutations)
• Game trees: Possible moves in a game (chess, tic-tac-toe)
• Backtracking algorithms: Explore possibilities, prune dead ends
• Planning problems: Sequence of actions to reach a goal state

KEY TAKEAWAY: Decision trees make the search space of a problem explicit. The branching factor and depth determine the size of the search space — exponential growth is a key concern.

Worked Example: Route Planning

Find all routes from A to D in a graph. The decision tree represents choices at each step:

Root: at A
├── Go to B → at B
│   ├── Go to C → at C → Go to D [SOLUTION]
│   └── Go to D [SOLUTION]
└── Go to C → at C → Go to D [SOLUTION]

Search Strategies on Decision Trees

• Breadth-First Search (BFS): Explore level by level — finds shortest path first
• Depth-First Search (DFS): Explore branch fully before backtracking — uses less memory

State Graphs

A state graph (state machine / state transition graph) is a directed graph where:
- Each node represents a state of a system
- Each directed edge represents a transition from one state to another
- Edges may be labelled with the condition or action that triggers the transition

Properties

• Directed graph (transitions have direction)
• May contain cycles (the system can return to earlier states)
• Has a designated initial state and often goal states

Applications

• Planning problems: Find a sequence of transitions from the initial state to a goal state
• Game solving: States represent board configurations
• Process modelling: States represent stages of a workflow
• AI search problems: BFS/DFS on the state graph finds a solution plan

Worked Example: Water Jug Problem

Two jugs: 3L and 5L capacity. Goal: Measure exactly 4L.
- Each state: (amount in 3L jug, amount in 5L jug)
- Initial state: (0, 0)
- Goal state: (_, 4)
- Transitions: fill jug, empty jug, pour between jugs

(0,0) → fill 5L → (0,5) → pour to 3L → (3,2) → empty 3L → (0,2) → pour to 3L → (2,0) ... → (1,4) GOAL

EXAM TIP: For planning problems, distinguish whether to use a decision tree (enumerate all choices) or a state graph (model system states). State graphs allow cycles (revisiting states); decision trees typically do not re-visit states.

Comparison