非同期ツリーにおけるモバイルエージェントの移動最適な部分的収集【Powered by NICT】

Shibata Masahiro; Ooshita Fukuhito; Kakugawa Hirotsugu; Masuzawa Toshimitsu

文献

J-GLOBAL ID：201702268548651877 整理番号：17A1965622

非同期ツリーにおけるモバイルエージェントの移動最適な部分的収集【Powered by NICT】

Move-optimal partial gathering of mobile agents in asynchronous trees

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=17A1965622&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=17A1965622&from=J-GLOBAL&jstjournalNo=T0022A") }}

著者 (4件)： , , ,
資料名：
巻： 705 ページ： 9-30 発行年： 2018年
JST資料番号： T0022A ISSN： 0304-3975 CODEN： TCSDIQ 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：オランダ (NLD) 言語：英語 (EN)

本論文では,非同期ツリーネットワークにおけるモバイルエージェントの部分集合問題を考察した。部分収集問題は古典的収集問題の一般化,すべてのエージェントが同じ節で満たすことを必要とする。部分収集問題は,与えられた正整数gに対して少なくともg剤は,これらが終端ノードの各々で満たすように各エージェントは,ノードに移動し,終了すべきであることを必要とする。部分集合問題のための必要条件である(井戸investigated)古典的収集問題のそれよりも弱く,このようにして,著者らはそれらの間の動きの複雑さの違いを明らかにした。二多重度検出モデル:弱い多重度検出と強い多重度検出モデルを考察した。弱い多重度検出モデルでは,各エージェントが電流ノードで存在する他のエージェントかどうかを検出することができるが,剤の正確な数を数えることはできない。強力な多重度検出モデルでは,各エージェントが電流ノードでのエージェントの数を数えることができる。添加では,二トークンモデル:非トークンモデルと移動可能なトークンモデルを考察した。非トークンモデルでは,エージェントはノードやエッジを示すいかなる方法でもできない。トークンモデルでは,各エージェントは最初にその初期ノードにトークンを残し,トークンを除去することができる。著者らの貢献は以下の通りである。非トークンモデルのためのエージェントは部分的収集問題を解くためのΩ(k n)全移動必要とすることを示す,nはノードの数,Kは,エージェントの数であった。第二に,弱い多重度検出と非トークンモデルを考察した。このモデルでは,非対称ツリーのための,以前の結果によってエージェントはO(k n)全移動,全移動を用いた漸近最適である部分的収集を達成することができる。さらに,対称ツリーのための,部分集合問題を解決するアルゴリズムは存在しないことを示した。第三に,強力な多重度検出と非トークンモデルを考察した。このモデルでは,任意の木に対するO(k n)全移動,全移動を用いた漸近最適である部分的収集を達成するためのアルゴリズムを提案した。最後に,弱い多重度検出と除去可能なトークンモデルを考察した。このモデルでは,O(g n)全移動における部分的収集を達成するためのアルゴリズムを提案した。このモデルでは,エージェントは部分的収集問題を解くためのΩ(g n)全移動必要とすることに注意すべきである。,第二の提案アルゴリズムは全移動に関してもは漸近的に最適である。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

, , , , , , , ,
, 【Automatic Indexing@JST】

著者キーワード (4件)： , , ,

計算機網 , 人工知能

, ,

前のページに戻る