Premium
Stochastic shortest paths with recourse
Author(s) -
Andreatta Giovanni,
Romeo Luciano
Publication year - 1988
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230180306
Subject(s) - counterintuitive , shortest path problem , probabilistic logic , computer science , variety (cybernetics) , mathematical optimization , path (computing) , mathematics , theoretical computer science , graph , artificial intelligence , epistemology , programming language , philosophy
Abstract This paper considers Stochastic Shortest Path (SSP) problems in probabilistic networks. A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretations and applications. We have chosen to look at the case where detours from the original path must be taken whenever the “first‐choice” arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochastic programming to this problem and the proof that the computational complexity of a particular SSP problem is polynomial.