Given a collection of red and blue mobile vehicles scattered across two discrete horizontal grid lanes, we seek to move all the blue vehicles to the far left-hand side and all the red vehicles to the far right-hand side, thus \textit{physically sorting} them according to color. The vehicles move simultaneously at discrete time steps $T=0, 1, \ldots$, and must not collide with each other. Our goal is to design a centralized algorithm that controls the vehicles so as to sort them in the least number of time steps. We find an optimal algorithm for this problem and prove its correctness. Furthermore, we derive an \textbf{exact} lower bound for the amount of time it takes to sort the vehicles given any staring configuration. Our sorting algorithm matches this lower bound, thus it is instance optimal, attaining the best possible sorting time for any initial configuration.


翻译:根据分散在两条离散的横向网格通道上的红色和蓝色机动车辆的集合情况,我们力求将所有蓝色车辆和所有红色车辆移到最左侧的极右侧,从而根据颜色对车辆进行物理排序。这些车辆在离散时间步骤同时移动 $T=0, 1,\ldots$, 并且不能相互碰撞。我们的目标是设计一种集中算法,控制车辆,以便以最少的时间步骤对车辆进行分类。我们为这一问题找到一种最佳算法,并证明其正确性。此外,我们为根据任何凝视配置对车辆进行排序所需的时间,得出了一种较低界限。我们的算法匹配了这个更低的界限,因此是最佳的,为任何初始配置取得最佳的排序时间。

0
下载
关闭预览

相关内容

Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
机器人开发库软件大列表
专知
10+阅读 · 2018年3月18日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
已删除
将门创投
3+阅读 · 2017年10月27日
Andrew NG的新书《Machine Learning Yearning》
我爱机器学习
11+阅读 · 2016年12月7日
Smoothed Model-Assisted Small Area Estimation
Arxiv
0+阅读 · 2022年1月21日
Arxiv
0+阅读 · 2022年1月19日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
机器人开发库软件大列表
专知
10+阅读 · 2018年3月18日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
已删除
将门创投
3+阅读 · 2017年10月27日
Andrew NG的新书《Machine Learning Yearning》
我爱机器学习
11+阅读 · 2016年12月7日
Top
微信扫码咨询专知VIP会员