How to solve a "foraging" problem on a directed graph?

The obvious approach of path-finding in a graph whose vertices are tuples (nut sequence index, tree) and have edges to tuples which increment the index and have a reachable tree with the appropriate nut is going to be hard to beat.

As to which path-finding algorithm to use: there's a wealth of literature here, but I'd start by reading up on A*.

$\color{brown}{\textbf{Parametrization.}}$

Denote

$T=8$ - the quantity of trees in the forest,

$a = 4$ - the average quantity of the available next trees,

$K=5$ - the quantity of kinds of the nuts in the forest,

$k=3$ - the average quantity of kinds of the nuts in the trees,

$D=9$ - the length of the given chain of the kinds of nuts,

$p=\dfrac kK = \dfrac35$ - the probability that the required kind of nuts is in the arbitrary tree,

$b=pa=\dfrac{12}{5}$ - the expectation of the quantity of the next trees with the required kind of nuts,

$C$ - the complexity of the algorithm for calculating the path, or the total number of checks "tree - sort of nuts."

$\color{brown}{\textbf{Calculating a path.}}$

Total quantity of sequences equals to $kK^{D-1}\approx=11\,71875.$

If $b>1,$ then the quantity of the variants in the ordinary search algorithms increases exponentially, $$C\approx a\sum\limits_{d=0}^{D-1} b^d = a\dfrac{b^D-1}{b-1} \approx 7545 < kK^{D-1}.\tag1$$ This means that the searching can not be broken quickly.

At the same time, required sequence "dceaabcdc" can be splitted to the subsequences in the form of ("dceaa","abc","cdc"), wherein the second and the third subsequences can start from the any tree.

Calculating paths for the subsequences require $$C_s \approx a\dfrac {b^{5}-1}{b-1}+2Tb\dfrac {b^{3}-1}{b-1} \approx 576\tag2$$ operations, with the approximate quantities of subpaths $$g_1 \approx \dfrac {b^{5}-1}{b-1} \approx 56,\quad g_2 \approx g_3 \approx Tp\dfrac {b^{3}-1}{b-1} \approx 44,\tag3$$ and that corresponds with the quantity of possible sequences $$N\approx \dfrac{g_1g_2g_3}{K^2} \approx 4337.$$

Subpaths $g_i$ can be placed in three arrays,wherein the special first index of the array $g_1$ corresponds to the number of the last tree, and the special first index of the array $g_3$ corresponds to the number of the first tree. The array $g_2$ has not special indexes.

Since the first tree in the next subpath should coinside with the last tree in the previous subpath, proposed structure allows to get any subpath of $g_2$ and to add the "head" from $g_1$ and "tail" from $g_3$ by the first indexes.

This means, that the first task has the complexity $(2),$ wherein the last step of this algorithm allows to calculate "the tail" by the entrance, from the given tree. This possibly accelerates the algorithm.

On the other hand, this approach allows to solve weighted edges task, if to place weights of the subpath in the same arrays. As minimum, it provides searching of the all variants. On the other hand, the subpaths can be sorted by the weights, and that accelerates the algorithm.