The power of a pebble: exploring and mapping directed graphs
The power of a pebble: exploring and mapping directed graphs
复制标题
卵石的力量：探索和绘制有向图
DOI：
10.1145/276698.276759
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
S. Vadhan
中科院分区：
文献类型：
--
作者：
M. A. Bender;Antonio Fernández;D. Ron;A. Sahai;S. Vadhan
探索和映射一个未知的环境是一个基本问题，在各种情况下都研究了许多结果。并在此一般环境中解决映射问题。从每个顶点发出的边缘从“ 1”到“ D”，但我们不假设G的顶点被标记为标签，因为机器人无法区分顶点，除非有成功的希望。由于这个原因，我们提供了“卵石”的某些方法。知道顶点的上限，然后只能使用一个卵石（2）有效地学习图形。在这两种情况下，我们的算法都是确定性的。
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on finding efficient solutions to restricted versions of the problem. In this paper, we consider a model that makes very limited assumptions about the environment and solve the mapping problem in this general setting. We model the environment by an unknown directed graph G, and consider the problem of a robot exploring and mapping G. The edges emanating from each vertex are numbered from ‘1’ to ‘d’, but we do not assume that the vertices of G are labeled. Since the robot has no way of distinguishing between vertices, it has no hope of succeeding unless it is given some means of distinguishing between vertices. For this reason we provide the robot with a “pebble”—a device that it can place on a vertex and use to identify the vertex later. In this paper we show: (1) If the robot knows an upper bound on the number of vertices then it can learn the graph efficiently with only one pebble. (2) If the robot does not know an upper bound on the number of vertices n, then (log log n) pebbles are both necessary and sufficient. In both cases our algorithms are deterministic. C © 2002 Elsevier Science (USA)