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 $\Delta$ 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$.


翻译:在本文中, 我们在一个移动代理商的图表中研究寻宝问题。 图形$G=( V, E) 中的节点是匿名的, 图形中的节点必须是匿名的, 边点事件是位于美元( V) 的顶点是美元( V) 美元( V) 美元) 。 本文中, 我们用移动代理商用移动代理商的图表来研究寻宝问题。 移动代理商最初位于一个节点, 美元为$( G) 的节点, 代理商的起始点是匿名的节点。 到达节点后, 美元( V) 的边点是美元( V) 美元( V) 。 找到宝所需的时间是代理商在找到宝之前访问的边缘的总数 。 代理商对图表或宝藏的位置没有任何事先了解。 我们知道图表、 代理商的初始位置和宝藏的位置, 将某些节点的比分值( 美元) 答案放在一个节点上, 。 我们的轨道上, 美元( ) 交易的底值是一定的答案, 。 我们的值是纸交易的答案是具体值 。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
145+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
100+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年10月18日
Arxiv
0+阅读 · 2022年10月17日
Arxiv
0+阅读 · 2022年10月13日
VIP会员
相关VIP内容
相关资讯
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员