依据曼哈顿城市图抽象化出去的数学题目:最少曼哈顿网络问题。给出平面图上的一个点集,结构总长,最少的互联网,促使随意两点之间都是有长短较短的途径相接——学者们给它取名“最少曼哈顿网络问题”。
最小曼哈顿网络问题是近些年得到普遍重视的计算几何和组成最优控制问题。在规模性电子器件(VLSI)设计方案、分布式系统优化算法、计算生物学、网络设计方案、城市规划建设等行业激发着越来越大的功效。
历史时间进步全过程
最少Manhattan网络问题由J.Gudmundsson,C.Levcopoulos和G.Narasimhan于1999年最开始明确提出。以后,很多学者科学研究并提供了这一问题多项式时间近似算法。以前根据组成方式设计的最好近似算法(3-类似)由M.Benkert等人们在2004年得出。2005年,V.Chepoi[2]等人明确提出了根据线性规划问题的2-近似算法,这也是现阶段孰知有关这一问题的最好是类似度。
2009年6月上海复旦大学计算机学院大三学员郭泽宇有关“最少曼哈顿网络问题”的毕业论文被第25届计算几何国际学术会议录取,文章内容与此同时做为最好毕业论文之一被邀约文章投稿到大会特刊DiscreteandComputationalGeometry(DCG)。这代表着计算几何行业十年来的关键猜测被这名年仅20岁的本科毕业生取得成功处理。计算几何国际学术会议是计算几何行业最高级的大会,这一会议,中国大陆一位数学家早已远离了整整的十八年。
环境
最少曼哈顿网络问题,是1999年明确提出的顶级计算几何关键猜测。1999年,J.Gudmundsson,C.Levcopoulos和G.Narasimhan最开始明确提出最少曼哈顿网络问题。以后,很多学者科学研究并提供了这一问题多项式时间近似算法。以前根据组成方式设计的最好近似算法(3-类似)由M.Benkert等人们在2004年得出。2005年,V.Chepoi等人明确提出了根据线性规划问题的2-近似算法,这也是现阶段孰知有关这一问题的最好是类似度。
2009年6月,被上海复旦仅20岁的本科毕业生郭泽宇取得成功处理。他的有关“最少曼哈顿网络问题”的毕业论文被第25届计算几何国际学术会议录取,文章内容与此同时做为最好毕业论文之一被邀约文章投稿到大会特刊DiscreteandComputationalGeometry(DCG)。
问题