OPTIMAL PATHS IN GRAPHS WITH STOCHASTIC OR MULTIDIMENSIONAL WEIGHTS

被引:162
作者
LOUI, RP [1 ]
机构
[1] HARVARD UNIV,CAMBRIDGE,MA 02138
关键词
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].
BENTLEY, JL ;
KUNG, HT ;
SCHKOLNICK, M ;
THOMPSON, CD .
JOURNAL OF THE ACM, 1978, 25 (04) :536-543
[3]   MULTIDIMENSIONAL DIVIDE-AND-CONQUER [J].
BENTLEY, JL .
COMMUNICATIONS OF THE ACM, 1980, 23 (04) :214-229
[4]  
BENTLEY JL, 1978, SLAC PUB2189 STANF L
[5]  
BLONIARZ PA, 1980, SUNY TR803 ALB COMP
[6]  
BLONIARZ PA, 1979, SUNY TR796 ALB COMP
[7]   NOTE ON MULTIPLE OBJECTIVE DYNAMIC-PROGRAMMING [J].
DAELLENBACH, HG ;
DEKLUYVER, CA .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1980, 31 (07) :591-594
[8]  
Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
[9]   AN APPRAISAL OF SOME SHORTEST-PATH ALGORITHMS [J].
DREYFUS, SE .
OPERATIONS RESEARCH, 1969, 17 (03) :395-&
[10]   UTILITY THEORY [J].
FISHBURN, PC .
MANAGEMENT SCIENCE, 1968, 14 (05) :335-378