| 講演名 | 2001/6/18 木およびリングにおけるマルチエージェント最適巡回アルゴリズム 増澤 利光, 桝田 秀夫, 本山 均勇, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では, 複数のノードから送出されたモバイル・エージェントが, ネットワークのすべてのノードを巡回して最初のノードに戻るための最小時間の移動計画(移動経路と移動タイミング)を求める問題をマルチエージェント巡回問題として定式化する. ただし, 巡回中の任意の時点において, 各ノードに存在するエージェントは高々1つであると制約する. マルチエージェント巡回問題はNP困難である. そこで本稿では, ネットワークの形状を木, リングに制限し, n個(nはネットワークのノード数)のエージェントの最小時間のネットワーク巡回法を示す. |
| 抄録(英) | This paper introduces the multi-agent traversal problem: the problem to find a travel schedule of each mobile agent so that each agent can visit all nodes and return to its originating node. The problem requires us to find the schedule with the minimum travel time under the constraint that no two agents can simultaneously occupy a node. The problem is clearly NP-hard in arbitrary networks. This paper considers the problem for trees and rings and presents the optimal traversal plans of n agents in these networks, where n is the number of nodes in a network. |
| キーワード(和) | 分散システム / モバイル・エージェント / マルチエージェント巡回問題 / 木 / リング |
| キーワード(英) | distributed system / mobile agent / multi-agent traversal problem / tree / ring |
| 資料番号 | COMP2001-21 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木およびリングにおけるマルチエージェント最適巡回アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Optimal Multi-Agent Traversal Algorithms for Trees and Rings |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散システム / distributed system |
| キーワード(2)（和/英） | モバイル・エージェント / mobile agent |
| キーワード(3)（和/英） | マルチエージェント巡回問題 / multi-agent traversal problem |
| キーワード(4)（和/英） | 木 / tree |
| キーワード(5)（和/英） | リング / ring |
| 第 1 著者 氏名（和/英） | 増澤 利光 / Toshimitsu MASUZAWA |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科 Graduate School of Engineering Science Osaka University |
| 第 2 著者 氏名（和/英） | 桝田 秀夫 / Hideo MASUDA |
| 第 2 著者 所属（和/英） | 大阪大学サイバーメディアセンター Cybermedia Center Osaka University |
| 第 3 著者 氏名（和/英） | 本山 均勇 / Masao MOTOYAMA |
| 第 3 著者 所属（和/英） | 松下システムエンジニアリング(株) Matsushita System Engineering Co. |
| 発表年月日 | 2001/6/18 |
| 資料番号 | COMP2001-21 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 133 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |