METHOD FOR FINDING OPTIMAL PATHS USING A STOCHASTIC NETWORK MODEL

摘要

A method finds an optimal path from a source to a destination. The possible paths from the source to the destination are represented as a stochastic graph of nodes connected by edges. Each edge has an independent probability distribution over a cost of the edge. A constraint for reaching the destination is defined. The graph is reduced to a relatively small set of deterministic minimum cost problems, which can be solved to determine an optimal path that maximizes a probability of reaching the destination within the constraint.