1
$\begingroup$

I'm facing with the following problem.

Suppose to have a generic oriented graph with curl (there can be an edge from a node to itself). Suppose also that you have to perform a $n$-vertices-long path around the graph starting from a given vertex $S$. When one goes from the node $i$ to the node $j$ , then a cost function is updated accordingly to the movement.
In particular, let $c_0$ be a given initial cost. When one perform a movement, say we move from the vertex $S$ to the vertex $j$, then he can calculate $c_1$ with a certain function $ c_1 = f(c_0, \theta_j)$ where $\theta_j$ is a parameter attached to the node $j$. After this, he can move from node $j$ to node $k$ and then he will have $ c_2 = f(c_1, \theta_k)$ and so on. If $i(t)$ is the vertex visited at time $t$ then we have that: $ c_t = f(c_{t-1}, \theta_{i(t)})$ Finally, after $n$ steps, we have my $c_n$, which obviously depends on the particular path we followed.

My question is: is there some algorithm/theory about how to compute the path which guarantees that $c_n$ is the lowest (or the greatest)?

1 Answers 1

0

In the case that costs will always increase— so that $f(c, n) > c$— then you can use branch and bound search to efficiently find the lowest-cost path.

Branch and bound finds the lowest-cost path: The algorithm initializes a list with just the start-at-$S$ path in it. At every round, the paths in the queue are sorted from lowest cost to highest cost so far. Remove the lowest-cost path in the list— if it has $n$ nodes in it, we can prove that it has the lowest possible cost among paths with $n$ nodes, and we're done. Otherwise, find all possible ways of extending that path without introducing loops, and add those extended paths to the agenda for the next round.

Without the "cost always increases" restriction or similar restrictions on the behavior of $f$, I imagine it would be difficult to find the cost-minimizing (or cost-maximizing) path in an efficient way.

There's always breadth-first-search, of course.