Skip to content

Search Space and Pruning: Navigating the Tree

During the Pairing Generation phase, the system must piece together flights to form legal trips. The search space of the Generator is a tree structure whose nodes represent all possible trips of a flight schedule.

Understanding how this tree is built and pruned is one of the most critical operations research concepts a Rave Developer must master.

1. Building the Search Tree

The root of the search space is an empty node representing an empty trip starting in some airport. For each leg in the flight schedule starting in that airport, a child node is created. Traversing down the search tree from the root, each child node represents adding a leg to the trip in progress.

graph TD
    Root((Empty Trip<br>Base: OSL))
    Root --> A(Flight OSL-BGO)
    Root --> B(Flight OSL-CPH)
    A --> C(Flight BGO-TRD)
    A --> D(Flight BGO-OSL)

    style Root fill:#4299e1,color:#fff

2. Pruning the Search Space

Because the number of nodes grows exponentially with each level in the tree structure, the generator cannot explore every branch. It must cut off (prune) bad paths as early as possible. This is where Rave rule classification dictates solver behavior:

Final Rules (Hard Pruning)

When a rule is violated for a node n, there exist no legal continuation of n. The generator prunes the search tree instantly.

Illegal Subchain Rules (Soft Pruning / Deferral)

When the rule is violated for a node n, there may exist a legal continuation of n. The generator does not prune the tree and keeps searching, expecting that adding subsequent flights will satisfy the condition.

3. The Dangers of Misclassification

  • Misclassifying a Final Rule as an Illegal Subchain: Every violation implies a subtree in search space that is explored for which no subnode can represent a legal trip. This causes severe inefficiency.
  • Misclassifying an Illegal Subchain as a Final Rule: The generator incorrectly prunes the search space when there may exist legal continuations, meaning many possible solutions are never found.