为进一步夯实科研基础，提升教师的科研能力，信息科学与技术学院于2026年3月10日在E213成功举办了一场学术报告会，邀请日本东海大学计算机应用系资深教授、大连海事大学讲座教授——谭学厚博士，来校作题为《有序凸体遍历算法及其相关问题的研究》的专题报告。

图1：院士合照

会议伊始，蒋波教授首先向与会教师介绍了谭学厚教授的学术背景。谭教授获南京大学计算机科学系学士学位和硕士学位，获日本名古屋大学工学部情报工学科博士学位，在加拿大Montreal大学和McGill大学从事博士后研究工作。现任日本东海大学情报理工学院计算机应用系教授、大连海事大学讲座教授。谭教授在计算几何、算法分析与设计、图论和组合优化等领域造诣深厚，在计算机领域知名期刊上发表学术论文100余篇，学术成就享誉国际。

图2：蒋波教授讲话

谭学厚教授围绕“有序凸体遍历算法及其相关问题”，做了深入而系统的介绍。

谭教授首先介绍了有序凸体遍历问题的基本定义：给定起点、终点，以及由几何物体（如点、线、简单多边形等）构成的有序序列，寻找依次遍历这些给定几何物体的最优路径。根据遍历对象及遍历要求的不同，该问题可衍生出很多有趣的研究课题，且有些问题的求解方法是十分复杂的，甚至可能是NP难的。谭教授着重说明了旅行商问题（TSP）、巡逻员路径问题（Watchman Route Problem）、狩猎问题（Safari Problem）等经典问题的丰富理论内涵与实际应用价值。

图3：谭学厚教授讲话

谭教授详细介绍了巡逻员路径问题的研究历程，系统梳理了从1999年O(n⁴)精确算法到2017年O(n³)优化的演进脉络，并介绍了线性时间√2-近似算法等高效求解策略。特别值得关注的是，谭教授团队在线多边形探索领域取得的突破——2022年提出的7-竞争策略，通过将问题分解为子问题并在线实现√2-近似，显著提升了机器人在未知环境探索的理论性能边界。

图4：谭教授分享心得

为解决遍历多边形序列问题，谭教授引入了一种强大的数据结构——LSSPM（Last Step Shortest Path Maps）。该数据结构的成功应用，不仅为狩猎问题、巡逻员路径等经典难题提供了高效的解决方案，还为机器人路径规划、GIS开发等应用领域提供了坚实的算法支撑。

图5：LSSPM结构图

本场报告的高潮部分聚焦于射线TSP的最新突破。该问题长期悬而未决，直到2020年才获得多项式时间算法。谭教授深入剖析了核心思想：通过引入圆形区域和射线段的扩展结构确定访问顺序，利用伪巡视路线的构造与迭代调整，最终提出O(n⁵)时间的求解算法。这一成果标志着几何优化领域的重要里程碑，也为最小周长相交多边形等扩展问题开辟了新的研究路径。

报告会最后，王立娟院长作总结发言，对谭学厚教授的精彩报告表示衷心感谢，并高度概括了本次学术交流的重要意义，并鼓励与会教师多与谭教授进行交流，力争在计算几何、算法设计等基础领域深耕细作，产出具有影响力的高质量原创性成果。

图6：王立娟院士讲话

同时指出，信息科学与技术学院将持续优化科研生态，完善团队建设机制，为教师成长成才提供全方位支持，共同谱写信息科学与技术学院高质量发展的新篇章。

信息科学与技术学院信息新闻中心