近日，电子科技大学计算机学院许超教授应邀访问beat365在线体育官网，为beat365在线体育官网师生作题为“在固定拓扑结构上的堆垛机问题的求解算法”的学术报告。

堆垛机问题（Stacker Crane Problem，SCP）来源于仓库、码头等场合货物运送车辆的路径规划。在仓库中，运送货物的车辆（堆垛机）接到若干请求，每个请求将某种货物从一个取货地点运送到一个存货地点。堆垛机问题的目标规划堆垛机的行程，完成所有送货请求，使行程的距离最短。在堆垛机问题中，如果所有存货点和取货点相同，则问题退化为Steiner TSP（STSP）问题。但一般的堆垛机问题的难度远远大于Steiner TSP问题：在树上，STSP问题有多项式时间算法，但在树上的SCP问题却是NP困难的。现在人们唯一已知的多项式时间可解的SCP实例是在路径或环上。有趣的是，在路径和环上，SCP问题可以归约到最小生成树问题解决。

在本次报告中，许超教授重新审视了路径和环上的SCP问题，并演示了如何将路径和环上的SCP问题的算法推广到固定的拓扑结构上，从而获得对于若干固定拓扑结构上的多项式时间算法。对于一般的拓扑结构，许超教授给出了的SCP问题的参数算法。许超教授给出的算法和图的以圈构成的线性空间密切相关，算法的分析用到深入的线性代数知识。

（文：张鹏 责任编辑：戴鸿君）