English
Competitive Online Approximation of the Optimal Search Ratio
文件大小：
211k
资源说明：这篇研究论文探讨了在线环境中对未知环境中未知目标的搜索效率问题，以及环境已知时对搜索效率的提升作用。文章通过为简单多边形和无向图提供了在线搜索策略，这些策略的效果与最佳的离线搜索算法相当，差距仅在固定因子上。对于其他设置，论文证明了不存在这样的在线算法。为了衡量搜索效率，研究引入了一种自然度量标准，这一标准比纯粹悲观的竞争分析更为合理且现实。研究论文的内容涉及在线运动规划、竞争比、搜索、探索和自然度量等关键词，并涵盖了相关的数学与计算理论。
在介绍部分，论文提出生活中反复出现的任务是搜索环境中的未知目标。搜索问题有多种变体，例如搜索者可以有视觉，或者仅限于通过触摸来感知，环境可能是简单的多边形如公寓，或者是图如街道网络。搜索环境可能是已知的，也可能是未知的。搜索问题在在线运动规划领域受到广泛关注，搜索成本通常以搜索路径长度来衡量，这一长度与从起始点到目标点的最短路径长度进行比较。搜索算法的竞争比定义为这些值的最大商，覆盖了所有环境和环境中的所有目标位置。
论文还以搜索从共同起点发出的两条半线为例，展示了“加倍”策略交替访问两条半线，每次探索深度加倍，从而达到目标点最多经过比起点距离长9倍的路径，对于这个问题，9的竞争比是最优的。这一加倍方法构成了后续论述在线搜索策略的基准。
文章指出，大多数研究集中于已知或未知环境下的搜索，但问题在于，对于在线搜索者来说，环境的未知性可能对搜索效率造成很大的影响。一种理想的在线搜索算法应当能够快速适应环境的变化，找到目标位置。然而，由于在线搜索者没有关于环境的先验知识，因此必须实时做出决策。这使得在线算法通常不如离线算法有效，因为离线算法在搜索之前就知道了环境的全部信息。
论文接着介绍了在线搜索策略的重要概念——竞争比。竞争比是一种度量在线算法性能的指标，比较了在线算法找到目标所需的路径长度与最优路径长度之间的比率。一个在线算法的性能越好，它的竞争比就越低。然而，竞争比也有悲观的一面，因为它可能不会考虑到搜索者在搜索过程中的学习和适应能力。
为了解决这一缺陷，论文提出了自然度量的概念，这是一种更实际的评估在线搜索策略的方法。它在不牺牲算法性能的同时，提供了一种更准确的评估方式。自然度量考虑了在线搜索过程中搜索者能够获取到的关于环境的信息，以及搜索者如何利用这些信息来指导搜索。
论文中提出的在线搜索策略是通过在简单多边形和无向图中搜索未知目标来实现的。对于这些场景，论文指出，存在有效的在线搜索策略，这些策略的效果与最佳的离线搜索算法相当，二者之间的差距仅在一个常数因子范围内。然而，对于其他一些场景，研究者证明了不存在这样的在线算法。这意味着在线搜索策略的效果是有限的，并非对所有类型的环境都适用。
文章还提到了一些算法的关键概念，例如路径长度的测量、探索深度的加倍策略以及对算法性能的评价标准等。研究论文强调了竞争分析在评估在线搜索算法中的重要性，并提出了改进方案，即引入自然度量标准。这种度量标准考虑了搜索者在搜索过程中的实际表现，以及其对环境信息的实时处理能力，从而为在线搜索算法的评价提供了一个更加合理和现实的评价体系。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
