報(bào)告時(shí)間：2023年3月27日 星期一 下午14：00—15：30

報(bào)告地點(diǎn)：電航樓219

報(bào)告摘要：

Given a set of cites along with the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all the cites and returning to the starting point. It is well known that the TSP is NP-hard. However, if some order or a partial order of the cities to visit is given, polynomial-time solutions exist in most cases.

This talk gives a survey of recent work on the problems of touring a sequence of line segments, convex polygons in the plane and inside a polygonal region. The well-known watchman route problem, which asks for a shortest route along which a mobile robot can see a given polygon, can be also interpreted as a problem of touring a sequence of chords inside a polygon. Algorithmic techniques developed for the touring objects problems, including a data structure, called the last step shortest path maps, are investigated. An interesting result is that the traveling salesman problem for lines and rays in the plane can be solved in O() and O() time, respectively.

報(bào)告人簡(jiǎn)介：

譚學(xué)厚現(xiàn)任日本東海大學(xué)情報(bào)理工學(xué)院計(jì)算機(jī)應(yīng)用系教授，大連海事大學(xué)講座教授，并曾于1985年至1987年任教于南京大學(xué)計(jì)算機(jī)科學(xué)系。譚學(xué)厚1982年畢業(yè)于南京大學(xué)計(jì)算機(jī)科學(xué)系，1985年獲南京大學(xué)計(jì)算機(jī)科學(xué)系碩士學(xué)位，1991年獲日本名古屋大學(xué)工學(xué)部情報(bào)工學(xué)科博士學(xué)位。1992年至1993年在加拿大Montreal大學(xué)和McGill大學(xué)博士后工作站工作。譚學(xué)厚教授的主要研究方向是計(jì)算幾何，算法分析與設(shè)計(jì)，圖論和組合優(yōu)化。主持日本學(xué)術(shù)振興會(huì)項(xiàng)目6項(xiàng)，在Theoretical Computer Science，Algorithmica, Computational Geometry: Theory and Applications，Discrete Applied Mathematics, Journal of Combinatorial Optimization等理論計(jì)算機(jī)領(lǐng)域內(nèi)知名期刊發(fā)表學(xué)術(shù)論文50余篇。

信息科學(xué)技術(shù)學(xué)院

2023年3月23日