论文标题
使用鹅卵石在图中寻宝
Treasure Hunt in Graph using Pebbles
论文作者
论文摘要
在本文中，我们研究了移动代理图中的寻宝问题。图$ g =（v，e）$中的节点是匿名的，并且在V $中的顶点$ v \的边缘被任意标记为$ 0,1，\ ldots，deg（v）-1 $。在一个固定对象的节点$ t $ in $ g $中，称为{\ it trease}。最初位于节点$ s $ g $的移动代理，代理的起点必须通过达到节点$ t $来找到宝藏。 $ s $到$ t $的距离是$ d $。找到宝藏所需的{\ it Time}是代理商找到宝藏之前访问的边缘总数。代理没有关于图形或宝藏位置的任何先验知识。一个知道图形的甲骨文，代理的初始位置以及宝藏的位置，将一些卵石放在节点上，最多每个节点，最多一个卵石，以引导代理商朝着宝藏迈进。 本文旨在研究所提供的鹅卵石数量与找到宝藏所需的时间之间的权衡。具体来说，我们的目标是回答以下问题。 ``如果放置了$ k $ pebbles的最高度$δ$和直径$ d $的最低搜寻寻寻宝时间是多少？ “ 当$ k <d $或$ k = cd $的某些正整数$ c $时，我们会回答上述问题。我们为代理设计有效的算法，用于不同值的$ k $。我们还提出了$ k <d $的几乎匹配的下限结果。
In this paper, we study the treasure hunt problem in a graph by a mobile agent. The nodes in the graph $G=(V,E)$ are anonymous and the edges incident to a vertex $v\in V$ whose degree is $deg(v)$ are labeled arbitrarily as $0,1,\ldots, deg(v)-1$. At a node $t$ in $G$ a stationary object, called {\it treasure} is located. The mobile agent that is initially located at a node $s$ in $G$, the starting point of the agent, must find the treasure by reaching the node $t$. The distance from $s$ to $t$ is $D$. The {\it time} required to find the treasure is the total number of edges the agent visits before it finds the treasure. The agent does not have any prior knowledge about the graph or the position of the treasure. An oracle, that knows the graph, the initial position of the agent, and the position of the treasure, places some pebbles on the nodes, at most one per node, of the graph to guide the agent towards the treasure. This paper aims to study the trade-off between the number of pebbles provided and the time required to find the treasure. To be specific, we aim to answer the following question. ``What is the minimum time for treasure hunt in a graph with maximum degree $Δ$ and diameter $D$ if $k$ pebbles are placed? " We answer the above question when $k<D$ or $k=cD$ for some positive integer $c$. We design efficient algorithms for the agent for different values of $k$. We also propose an almost matching lower bound result for $k<D$.
