文献

J-GLOBAL ID：201702286216261316   整理番号：17A1425535

ネットワーク探索のためのランダム中国郵便配達人ツアーの近似率について【Powered by NICT】

On the approximation ratio of the Random Chinese Postman Tour for network search

著者 (1件)： Lidbetter Thomas (Department of Management Science and Information Systems, Rutgers Business School, 1 Washington Park, Newark, NJ 07102, USA)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 263  号： 3  ページ： 782-788  発行年： 2017年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最初に探索者はネットワーク上の単位速度経路間のランダムGalによって提案された,最悪の場合における最小期待時間における隠れた点を見出すことを目指して古典的探索問題を考察した。サーチャ間の零和ゲームとHiderを最大化する時間として見ることができる。捜索救難活動など多くの探索問題のための天然モデルである軍用文脈における天敵,ボンベまたは兵器のための探索捕食者-被食者探索。中国郵便配達人探訪(CPT)は,すべての円弧を探索するネットワークの最小時間旅行であり,ランダム中国郵便配達人探訪(RCPT)は,任意の与えられたCPTとその逆の等確率選択である。RCPT最適ネットワークの全クラスが知られているが,ほとんどは実装が実用的であることを複雑な最適戦略を持つことをいくつかの特別な場合を除いてゲームの解知られていない。RCPTまたは他の探索戦略は,一般的なネットワークのためのどのように振舞うかという疑問は解析されていない。RCPTは,4/3の近似比を有することを示した:すなわち,ネットワーク上の点を見出すに要する最大期待時間は最適探索戦略の4/3倍以上ではない。,サーチャはHiderを発見後,出発点に戻らなければならないAlpernによって最近提案された関連探索ゲームにおけるRCPTの性能を調べた。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *旅行 ,  ゼロ和ゲーム ,  円弧 ,  *近似法 ,  救助 ,  *ネットワーク ,  探索問題 ,  兵器 ,  *中華人民共和国 ,  ゲーム
準シソーラス用語： 探索戦略 ,  最適戦略 ,  *近似率 , 【Automatic Indexing@JST】

著者キーワード (4件)： ゲーム理論 ,  探索ゲーム ,  中国郵便配達人ツアー ,  Networks

分類 (2件)： ネットワーク法  (KA03040X) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (6件)： 探索 ,  中国 ,  郵便 ,  配達 ,  ツアー ,  近似率