liveBook · Manning

Search tree

As explained in Applied Reinforcement Learning

A search tree is a branching data structure whose nodes represent states or decision points and whose edges represent possible actions or outcomes.

A search tree represents possible decisions as branches from a current state: each branch corresponds to an action and a possible future outcome. Simulating branches helps compare decisions before committing to them, as in logistics planning. section 4.1

In capacitated vehicle routing, each node can represent a partial solution, with some customers assigned to vehicle routes and others unvisited. Monte Carlo tree search grows a partial tree, using UCB1 to focus effort on promising branches rather than exploring every route combination. section 7.4

A routing decision tree can encode:

  • States: current routes, unvisited customers, and the vehicle being assigned. section 7.4
  • Actions: add an eligible customer to the current vehicle, or move to the next vehicle when needed. section 7.4
  • Outcomes: new partial routes, evaluated by whether all customers are served and by total travel distance. section 7.4

Planning a logistics expansion

Before opening a warehouse in Vancouver, simulate possible choices and their effects on delivery times, costs, and customer satisfaction. The tree lets decision-makers compare scenarios without first carrying them out. section 4.1

How Applied Reinforcement Learning covers it

How deep it goes
Defines state and action branches, then works through partial-tree MCTS selection, expansion, simulation, and reward updates instead of exhaustive route search.
Examples
Uses logistics-network expansion scenarios and capacitated vehicle routing with customer assignments, vehicle limits, and route distances.
What you can do after
Evaluate simulated decisions before committing and understand how MCTS concentrates search on promising routing solutions.
How it connects
Connects tree search with Markov decision processes, reinforcement learning, Monte Carlo tree search, and UCB1.

Also explained in

Compare how 2 books explain search tree →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.