.png){kind=icon}
返回
A sampling method based on distributed learning automata for solving stochastic shortest path problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2020.106638.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper studies an iterative stochastic algorithm for solving the stochastic shortest path problem. This algorithm, which uses a distributed learning automata, tries to find the shortest path by taking a sufficient number of samples from the edges of the graph. In this algorithm, which edges to be sampled are determined dynamically as the algorithm proceeds. At each iteration of this algorithm, a distributed learning automata used to determine which edges to be sampled. This sampling method, which uses distributed learning automata, reduces the number of samplings from those edges, which may not be along the shortest path, and resulting in a reduction in the number of the edges to be sampled. In this paper, we propose a new method for analysis of the algorithm. The method proposed in this paper, unlike the previous ones, which were based on the Martingale theory, is based on the sampling. The proof given in this paper, unlike the previous ones, which were for a specific input graph, is not restricted to the input graph and is general. We also show that as the number of samples taken from the edges increases, the probability of finding the shortest path also increases. Experimental results obtained from some benchmark stochastic graphs and some random graphs also confirm the theoretical results. (C) 2020 Elsevier B.V. All rights reserved.
Keyword:
Distributed learning automata
Learning automata
Shortest path problem
Stochastic graph
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
K
IF:
7.6
论文数:
1.2W
被引数:
4.5W
机构
引用论文
Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems
OAAI
.png){kind=icon}
OAAI分享收藏
分享收藏
查看更多内容