OPTIMAL PATHS IN GRAPHS WITH STOCHASTIC OR MULTIDIMENSIONAL WEIGHTS

被引：162

作者：

LOUI, RP ^{[1
]}

机构：

[1] HARVARD UNIV,CAMBRIDGE,MA 02138

来源：

COMMUNICATIONS OF THE ACM | 1983年 / 26卷 / 09期

关键词：

Computation theory - Graph theory - Stochastic systems;

D O I：

10.1145/358172.358406

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper explores computationally tractable formulations of stochastic and multidimensional optimal path problems, each as an extension of the shortest path problem. A single formulation encompassing both problems is considered, in which a utility function defines preference among candidate paths. The result is the ability to state explicit conditions for exact solutions using standard methods, and the applicability of well-understood approximation techniques. © 1983 ACM.

引用

页码：670 / 676

页数：7

共 25 条

[1]

[Anonymous], 1970, ESSAYS THEORY RISK B

[2] AVERAGE NUMBER OF MAXIMA IN A SET OF VECTORS AND APPLICATIONS [J].