文献

J-GLOBAL ID：201002297037281650   整理番号：10A0444816

白板を利用したモバイルエージェントによる効率的なグラフ探索

Time and Space Efficient Graph Exploration by a Mobile Agent Using Whiteboard

著者 (6件)： SUDO Yuichi (Osaka Univ., Osaka, JPN) ,  BABA Daisuke (Osaka Univ., Osaka, JPN) ,  NAKAMURA Junya (Osaka Univ., Osaka, JPN) ,  OOSHITA Fukuhito (Osaka Univ., Osaka, JPN) ,  KAKUGAWA Hirotsugu (Osaka Univ., Osaka, JPN) ,  MASUZAWA Toshimitsu (Osaka Univ., Osaka, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 465(COMP2009 49-58)  ページ： 57-64  発行年： 2010年03月05日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 1体のエージェントによる無向グラフ探索問題を考える。グラフ探索問題では,エージェントは,グラフ中の任意の頂点から実行を開始してすべての頂点・辺を訪問し,実行開始点に帰還して停止しなければならない。本研究の目的は,エージェントの総移動回数とメモリ量を最小化することである。本稿では,頂点訪問時にエージェントが,白板と呼ばれる頂点上の記憶装置の内容を自由に読み書きできることを仮定する(白板モデル)。一方,既存研究の多くは白板の存在を仮定していない(白板なしモデル)。白板なしモデルでは,ネットワークの探索に必要なすべての情報をエージェントが記憶しなければならないため,エージェントのメモリ量が小さいアルゴリズムの設計は難しい。本稿では,白板モデルのもとで探索問題を解く,総移動回数とメモリ量がともに小さい4つのアルゴリズムを提案する。(著者抄録)

シソーラス用語： エージェント ,  用途別板 ,  *無向グラフ ,  *探索問題 ,  *頂点 ,  *計算量 ,  記憶容量 ,  効率
準シソーラス用語： *ホワイトボード ,  *モバイルエージェント ,  *計算効率

分類 (1件)： 数値計算  (JE02000J)

引用文献 (9件)：

• ALBERS, S. Exploring unknown environments. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, 1997. 1997, 416-425
• BENDER, M. A. The power of a pebble : Exploring and mapping directed graphs. Information and Computation. 2002, 176, 1, 1-21
• BUDACH, L. Automata and labyrinths. Math. Nachrichten. 1978, 86, 195-282
• DENG, X. Exploring an unknown graph. Journal of Graph Theory. 1999, 32, 3, 265-297
• DIKS, K. Tree exploration with little memory. Journal of Algorithms. 2004, 51, 1, 38-63

タイトルに関連する用語 (3件)： モバイルエージェント ,  グラフ ,  探索