Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.