Optimal graph exploration without good maps
Optimal graph exploration without good maps
复制标题
没有好的地图的最佳图探索
DOI：
10.1016/j.tcs.2004.07.031
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
A. Pelc
中科院分区：
文献类型：
--
作者：
Anders Dessmark;A. Pelc
机器人必须访问所有节点并遍历未知无向连通图的所有边，使用尽可能少的边遍历。探索算法A的质量通过将其成本（边缘遍历的数量）与具有图的全部知识的最优算法的成本进行比较来测量。在图中的所有起始节点和给定类U中的所有图上最大化的这些成本之间的比率称为算法A对于图的类U的开销。我们考虑三种情况下，提供不同数量的信息的机器人。机器人可能对所探索的图一无所知，或者具有其未标记的同构副本（未锚定的地图），或者具有带有标记的起始节点的副本（锚定的地图）。对于上述所有场景，我们构建了具有最小开销的自然探索算法，或者在一种情况下接近最小开销。虽然对于所有图的类，深度优先搜索被证明是所有场景的最佳算法，但树的情况却大不相同。我们表明，在没有任何知识的情况下，DFS仍然是最佳的树，但这是不是这种情况下，如果地图是可用的。在无锚映射的情况下，我们证明了最佳开销至少为3，但严格低于2（因此DFS不是最佳的）。在锚定地图的情况下，我们构造了一个树的最优算法，并表明其开销为32。我们还考虑探索类的线（简单路径）。在这种情况下，深度优先搜索对于没有任何知识的场景仍然是最佳的，开销为2。在无锚地图的情况下，我们构造了一个最优算法，并证明其开销为3。最后，在锚定地图的情况下，我们构造了一个最优算法，并证明了其开销为75。本文的一个重要贡献是建立下界证明这些探索算法的最优性。
A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class U, is called the overhead of algorithm A for the class U of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, or—in one case—close to smallest, overhead. While for the class of all graphs, depth-first search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at least 3 but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is 32. We also consider exploration of the class of lines (simple paths). In this case, depth-first search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is 3. Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is 75. An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms.