Graph Algorithm Question

[trelokamenos]

Hello people!

I'm new here...but

The things I'll talk about came up as I was doing independent research and it's not homework related, however I'm not sure where else I should post it except in a computer science subforum. Since it's not homework, you might want to give it less priority.

I have a state graph (directed acyclic) with a beginning state (lets call it S) and an end state (N). Each transition happens in the following way:

When I'm currently at the state s, I choose an "action" from a set of actions (lets call it A). Then there is a probability distribution P(a), a E A to move from the current state to a set of states according to the action taken.

The problem is that at each step, I want to choose the action which minimizes the expected number of remaining hops to the end state.

Is there a name for this model or similar/equivalent one?
Has this algorithm been thought of before?

Thanks!

[TrustyTony]

Looks normal graph minimal distance probability coloring the edges.

[griswolf]

This is a variation of traveling salesman problem where the cost of any outbound edge is a probabilistic function of the distance to N from that edge's other node. That function ought to be interesting to write :)

As Tony points out, you can start by considering the known minimum distance algorithms. However you will need to adjust them to take account of the probabilistic nature of your particular problem.

[trelokamenos]

Hey! Thanks for your answers! Didn't have much time to verify, but I'll try to write for feedback sometime!

[mrnutty]

Also check out HMM