Chapter 6 Probabilistic networks and network algorithms
Timothy Law Snyder, J. Michael Steele · Handbooks in operations research and management science · 1995
This chapter discusses probabilistic networks and network algorithms. Probability enters into the theory of networks and network algorithms in several different ways. The most direct way is through probabilistic modeling of some aspect of the network. For example, in some freight management models the cost of transportation along the arcs of the network are modeled by random variables. In models such as these probability helps us grasp a little better a world that comes with its own physical randomness. A second important way probability enters is through more stylized stochastic models where the aim is to provide deeper insight into our technical understanding of the methods of operations research. Here there is considerably less emphasis on building detailed models that hope to capture aspects of randomness that live in a specific application context; rather, the aim is to provide mathematically tractable models of reasonable generality that can be used to explore a variety of different computational or estimation methods. Among the types of issues that have been studied in such models are the efficacies of deterministic algorithms and of deterministic heuristic methods. Many of the 'average case' analyses of algorithms would fit into this second role for probability. The third path by which probability enters into network theory is through randomized algorithms. This is the newest of the roles for probability, but it is a role that is of increasing importance. To make certain of the distinction that makes an algorithm 'randomized,' consider a version of depth-first search where one chooses the next vertex to be explored by selecting it at random from a set of candidates.