文献

J-GLOBAL ID：202002235244815937   整理番号：20A0981405

確率的最短経路問題:多面体組合せ論の展望【JST・京大機械翻訳】

The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective

著者 (2件)： Guillot Matthieu (Univ. Grenoble Alpes, CNRS, Grenoble INP*, G-SCOP, 38000 Grenoble, France) ,  Stauffer Gautier (The Centre of Excellence in Supply Chain (CESIT), KEDGE Business School, Talence, France)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 285  号： 1  ページ： 148-158  発行年： 2020年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,有限状態および行動空間における確率的最短経路問題に対する新しいフレームワークを与えた。著者らのフレームワークは,BertsekasとTsitsikis(1991)によって提案されたフレームワークとBertsekasとYu(2016)の両方を一般化する。著者らは,(i)初期状態から目標状態に到達する方法があるとき,問題が明確で(弱い)多項式であることを証明し,(ii)負のコストの遷移サイクルがない(負のコストサイクルの一般化)。これらの仮定は決定論的最短経路問題に対する標準的仮定を一般化し,著者らのフレームワークは後者の問題(以前の研究とは対照的に)をカプセル化する。この新しい設定において,(a)一つは決定論的および定常的な政策に限定できる,(b)問題は線形計画法を通して依然として(弱い)多項式,(c)値反復と極性化収束,(d)Dijkstraのアルゴリズムを拡張できることを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： Markov過程 ,  アルゴリズム ,  極性 ,  線形計画法 ,  多項式 ,  *最短路問題 ,  *組合せ論
準シソーラス用語： 初期状態 ,  決定論 ,  政策反復 ,  *最短経路 , 【Automatic Indexing@JST】

著者キーワード (5件)： Markov過程 ,  確率的最短経路 ,  価値反復 ,  政策反復 ,  Dijkstra

分類 (4件)： ネットワーク法  (KA03040X) ,  ゆらぎ,ランダム過程,Brown運動,輸送過程の一般的理論  (BA08020B) ,  数値計算  (JE02000J) ,  計算機網  (JC03000K)

タイトルに関連する用語 (5件)： 確率 ,  最短経路問題 ,  多面体 ,  組合せ論 ,  展望