标题： BusOut 是 NP 完全的 显示英文标题

标题： BusOut is NP-complete

摘要： 本研究考察了基于智能手机游戏Bus Out的决策问题的计算复杂性。 该游戏的目标是通过在地图上选择和派遣公交车，使用有限数量的公交车停车点将队列中的所有乘客装载到合适的公交车上。 我们证明了即使对于高度限制的实例，该问题也是NP完全的。 我们还表明，近似求解给定实例所需的最小停车点数量是困难的。 显示英文摘要

摘要： This study examines the computational complexity of the decision problem modeled on the smartphone game Bus Out. The objective of the game is to load all the passengers in a queue onto appropriate buses using a limited number of bus parking spots by selecting and dispatching the buses on a map. We show that the problem is NP-complete, even for highly restricted instances. We also show that it is hard to approximate the minimum number of parking spots needed to solve a given instance.