Trade-offs between selection complexity and performance when searching the plane without communication
Trade-offs between selection complexity and performance when searching the plane without communication
复制标题
在没有通信的情况下搜索平面时选择复杂性和性能之间的权衡
DOI：
10.1145/2611462.2611463
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tsvetomira Radeva
中科院分区：
文献类型：
--
作者：
Christoph Lenzen;Nancy Lynch;Calvin Newport;Tsvetomira Radeva
我们认为，在计算机科学中的生物启发问题的背景下，除了研究解决方案的时间复杂性，研究选择复杂性也很重要，这是一个衡量给定算法策略在自然界中出现的可能性的指标。本着这种精神，我们提出了一个选择复杂性度量x的蚂蚁问题[Feinerman等人]。对于算法A，我们定义χ（A）= B + log l，其中B是每个代理使用的存储器位数，l限制可用概率的精度（代理使用至少1/2l的概率）。我们考虑n个代理在平面上搜索目标，在距离原点的（未知）距离D内。我们确定log log D作为我们选择复杂性度量的关键阈值。我们证明了一个新的上界，当χ（A）≤ 3loglogD + O（1）时，该上界使（D2/n +D）<$2O（l）达到近优加速，当l∈ O（1）时，该上界是渐近最优的.相比之下，以前的算法实现类似的加速要求χ（A）= Ω（log D）。通过证明如果χ（A）< log log D - ω（1），则如果每个代理执行D2-o（1）移动，则目标很有可能找不到。这与直接的Ω（D2/n + D）下界构成了相当大的差距。
We argue that in the context of biology-inspired problems in computer science, in addition to studying thetime complexityof solutions it is also important to study theselection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Feinerman et al.]. For algorithm A, we define χ(A) = b + log l, where b is the number of memory bits used by each agent and l bounds the fineness of available probabilities (agents use probabilities of at least 1/2l). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We identify log log D as a crucial threshold for our selection complexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D2/n +D) ⋅ 2O(l)for χ(A) ≤ 3 log log D + O(1), which is asymptotically optimal if l∈ O(1). By comparison, previous algorithms achieving similar speed-up require χ(A) = Ω(log D). We show that this threshold is tight by proving that if χ(A) < log log D - ω(1), then with high probability the target is not found if each agent performs D2-o(1)moves. This constitutes a sizable gap to the straightforward Ω(D2/n + D) lower bound.
登录
查看更多内容
DOI：
10.1007/978-3-540-71541-2_5
发表时间：
2006
期刊：
The Journal of Supercomputing
影响因子：
--
作者：
S. Berman;Á. Halász;Vijay R. Kumar;S. Pratt
通讯作者：
S. Pratt
最佳和中心位置觅食理论应用于沙漠收割蚁 Pogonomyrmex californicus
影响因子：
2.7
作者：
K. Holder;G. Polis
通讯作者：
G. Polis
蚂蚁（Cataglyphis bicolor Fab.）觅食的中心位置：搜索模型
影响因子：
2.5
作者：
R. D. Harkness;N. Maroudas
通讯作者：
N. Maroudas
卵石的力量：探索和绘制有向图
DOI：
10.1145/276698.276759
发表时间：
1998
期刊：
J. Vis. Lang. Comput.
影响因子：
--
作者：
M. A. Bender;Antonio Fernández;D. Ron;A. Sahai;S. Vadhan
通讯作者：
S. Vadhan
使用对数内存进行树探索
影响因子：
1.3
作者：
Ambühl C
通讯作者：
Ambühl C