liveBook · Manning

Tree search

As explained in Applied Reinforcement Learning

Tree search is a planning technique that represents possible action sequences and outcomes as branches of a search tree and uses them to guide decisions.

Tree search represents possible decisions as branches from a current state, with each path showing a sequence of actions and outcomes. Comparing simulated paths can guide a choice before it is made. section 4.1

Choosing a delivery route

Start at a depot, branch into North or South routes, then add choices about which customer to visit first. Each completed plan has an accumulated cost. Searching the tree helps compare routes rather than treating the initial choice in isolation. section 7.1

Breadth-first search explores all paths at one depth before going deeper; depth-first search follows one branch to its end before returning to alternatives. BFS finds a shortest route when each step has equal cost, while the route example compares total travel costs. section 7.2

Figure 7.1 Tree data structure in vehicle route planning problem

A route-planning tree illustrates how customer choices branch beneath an initial route decision. section 7.1

How Applied Reinforcement Learning covers it

How deep it goes
Defines branching decisions and compares BFS with DFS through route examples, stopping short of explaining Monte Carlo Tree Search in detail.
Examples
Uses delivery-route choices, customer visit orders, and warehouse expansion scenarios to illustrate search trees.
What it assumes
Starts with a depot root and explains branches and leaf plans before introducing search algorithms.
What you can do after
Understand how to map delivery choices into a search tree and distinguish level-by-level BFS from branch-deepening DFS.
How it connects
Connects breadth-first search, depth-first search, Monte Carlo tree search, and reinforcement learning.

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.