How is the state-space tree expanded level by level in this example?

Conditions

• The tree is explored level by level.
• At each node, only jobs not already used on the path from the root are appended.
• The clip shows structural expansion only, not pruning by bounds.

Reasoning, step by step

1. Start from the root node representing the empty partial sequence.
2. Create one child for each possible first job choice: $J_1$, $J_2$, $J_3$, $J_4$.
3. Finish all immediate choices from the root, then expand node 2, then node 3, then node 4, then node 5.
4. Continue similarly across the rest of the frontier until all displayed nodes reach depth 4.

Example

The instructor says, "Now this one level is completed. See, I have considered all the jobs one by one," and then proceeds to expand the next node on the frontier rather than diving deeper under the just-created children.

Common misconceptions

• Assuming the tree is expanded depth-first, going down one branch to full depth before moving to siblings.
• Thinking that all jobs can be appended at each node, ignoring those already used on the path.

Watch the explanation

Explore next

• What does a root-to-node path mean in the job-sequencing tree?
• Why does this lecture say branch and bound is breadth-first rather than depth-first?
• How does the Least Cost Branch and Bound algorithm decide which node to explore next?