论文标题
在任意图中几乎最佳的确定性寻宝
Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs
论文作者
论文摘要
沿着一个简单连接图的边缘导航的移动代理，无论是有限的还是无限的，都必须找到一个隐藏在一个节点中的惰性目标（宝藏）。这项任务被称为寻宝活动。代理没有对图形，宝藏的位置或与之初始距离的先验知识。寻宝算法的成本是代理商执行的最差的边缘遍历数量，直到找到宝藏。 Awerbuch，Betke，Rivest和Singh [3]在受限的模型中考虑了图形探索和寻宝图图，在该模型中，该代理具有一个只能在启动节点$ S $中补充的油箱。油箱的尺寸为$ b = 2（1+α）r $，对于某些积极的真实常数$α$，其中$ r $（称为图的半径）是从$ s $到任何其他节点的最大距离。 $ b $的坦克允许代理商最多可制作$ \ lfloor b \ rfloor $ edge travers travers travers travers travers the Node $ s $的连续访问。 令$ e（d）$为边缘的数量，其至少一个末端的距离小于$ s $的$ d $。 Awerbuch，Betke，Rivest和Singh [3]猜想，不可能在节点中以$ d $的价格找到一个藏在节点中的宝藏，价格几乎是$ e（d）$。我们首先设计了一种在模型中工作的确定性寻宝算法，而无需限制代理商以成本$ \ MATHCAL {O}（e（d）\ log d）$的限制，然后展示如何修改该算法以从[3]中使用相同的复杂性从[3]中使用。因此，我们反驳上述二十岁的猜想。我们观察到，所有图表都没有任何寻宝算法可以击败$θ（e（d））$，因此我们的算法也几乎是最佳的。
A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node $s$. The size of the tank is $B=2(1+α)r$, for some positive real constant $α$, where $r$, called the radius of the graph, is the maximum distance from $s$ to any other node. The tank of size $B$ allows the agent to make at most $\lfloor B\rfloor$ edge traversals between two consecutive visits at node $s$. Let $e(d)$ be the number of edges whose at least one extremity is at distance less than $d$ from $s$. Awerbuch, Betke, Rivest and Singh [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most $d$ at cost nearly linear in $e(d)$. We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost $\mathcal{O}(e(d) \log d)$, and then show how to modify this algorithm to work in the model from [3] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost $Θ(e(d))$ for all graphs and thus our algorithms are also almost optimal.
