单选题
在单机模式任务规划的时序分配中,旅行商问题(简称TSP)模型适合处理( )。
A
城市数量不太大时
B
城市数量值较大时
C
城市数量值适中时
答案解析
正确答案:A
解析:
**解析:**
旅行商问题(Traveling Salesman Problem, TSP)是一个经典的组合优化问题,属于 NP-hard 问题。其核心目标是寻找一条经过所有城市且仅经过一次的最短闭合路径。
1. **计算复杂度分析**:
TSP 问题的解空间随着城市数量 $n$ 的增加呈阶乘级增长($(n-1)!/2$)。这意味着随着城市数量的增加,找到精确最优解所需的计算时间会急剧增加。
2. **单机模式的限制**:
题目强调了“单机模式”。在单机环境下,计算资源(CPU、内存)是有限的,无法像分布式集群那样并行处理海量数据。因此,算法的执行效率受限于单核或有限多核的处理能力。
3. **选项分析**:
* **A. 城市数量不太大时**:当城市数量较少(例如 $n < 20-30$,具体取决于算法和硬件)时,使用精确算法(如动态规划、分支定界法)可以在可接受的时间内求出全局最优解。即使使用启发式算法,小规模数据也能快速收敛。这符合单机模式下的实际应用场景。
* **B. 城市数量值较大时**:当城市数量很大时,精确求解在单机上几乎是不可能的(可能需要数年甚至更久)。此时通常需要借助分布式计算、云计算或使用近似算法/启发式算法(如遗传算法、模拟退火)来寻找满意解而非最优解,且往往不再单纯依赖传统的 TSP 精确模型直接求解。
* **C. 城市数量值适中时**:“适中”是一个模糊概念,但在算法复杂性语境下,一旦规模超出“小”的范围,计算难度就会陡增。相比之下,“不太大”更准确地描述了适合使用标准 TSP 模型进行精确或高效求解的范围。
**结论:**
由于 TSP 是 NP-hard 问题,在单机模式下,为了保证任务规划的时效性和可行性,该模型最适合处理**城市数量不太大**的情况,以便在合理时间内获得高质量的路径规划结果。
故正确答案为 **A**。
相关知识点:
单机TSP适合城市数少
题目纠错
2023电力行业多旋翼无人机竞赛
