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

Question

I'm a little squirrel living in a forest with, say, eight trees $A,B,C,\ldots,H$. I can jump from tree to tree, though not all jumps are possible. (The fact that I can jump from $A$ to $B$, for example, doesn't guarantee that I can jump from $B$ to $A$.) Basically, I live in a directed graph whose adjacency matrix contains a few (non-symmetrically distributed) zeros.

I have stored five sorts of nuts $a,b,c,d,e$ in my little forest, each tree containing some portion of these. For example, tree $A$ contains nuts $a,d,e$ (quantities don't matter).

Now my question is, does there exist an efficient algorithm to calculate a path (always starting in my home tree $A$) through the forest so that I will be able to pick up a given sequence of nuts along the way, say $d,c,e,a,a,b,c,d,c$? (I can only pick up one kind of nut per tree.)

Same question, but with weighted edges (that measure energy expenditure). In that case, how can I find the path with least total weight?

Final question, how long does an algorithm have to run as a function of the nut sequence length $N$?

Answer 1

You can solve this problem backwards with dynamic programming, where the value function $F$ has parameters for the starting vertex $i$ and for the number of nuts you collect $k$. Let me give an example for the sequence $d,c,e,a,a,b,c,d,c$.

Let $d_{ij}$ be the distance from $i$ to $j$ (obtained by, e.g., applying the Floyd–Warshall algorithm to the adjacency matrix), and let $N(x)$ be the set of nodes with nut $x$.

You initialize the method by setting $F(i,1) = \min_{j \in N(c)} \{d_{ij} \}$ to $0$ (nut $c$ since we work backwards), so $F(i,1)=0$ if nut $c$ is present at node $i$. You proceed by setting $F(i,2) = \min_{j \in N(d)} \{d_{ij} +F(j,1) : i \neq j\}$, where you minimize only over the nodes $j$ where the set $N(d)$ is used since nut $d$ is the second last one. Then set $F(i,3) = \min_{j \in N(c)} \{d_{ij} +F(j,2) : i\neq j\}$, etc.

The runtime is quadratic in the number of nodes and linear in the number of nuts (except for the preprocessing step of finding $d_{ij}$).

Answer 2

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*.

Answer 3

$\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.