- 在线时间
- 0 小时
- 最后登录
- 2009-10-10
- 注册时间
- 2009-7-18
- 听众数
- 9
- 收听数
- 0
- 能力
- 0 分
- 体力
- 104 点
- 威望
- 11 点
- 阅读权限
- 30
- 积分
- 271
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 234
- 主题
- 19
- 精华
- 1
- 分享
- 0
- 好友
- 0
升级   85.5% 该用户从未签到
 |
觉得是个有意思的问题,希望有兴趣的朋友一起探讨,当然这个世界级猜想早几个月才被复旦大学大三学生郭泽宇破解,很牛!也给我们大学本科阶段追求创新一些启示,这几天正在做中南大学的培训题《城市生活垃圾管理问题》,设计到垃圾收运路线的设计,而城市垃圾收运路线正是一个曼哈顿网络问题,当然是最小时间,还是最短路径,看个人理解,要解决这个问题看似方法很多,大多数是当做一个TSP图论问题来求解,或者建立规划模型,用的方法也大多是模拟退火、遗传算法、蚁群算法等等,比较有新意是分析曼哈顿的特殊结构,运用基于约束的网格聚类方法从类的角度考虑,就降低了数百个收集点的运算复杂度。当然更好的方法就是破解这个世界级难题,从而一劳永逸。到知网等网站搜了下,相关的学术文献很少, 有点意思。 4 }6 R, A& Z8 N$ e- b: p; W7 o
最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成电路(VLSI)设计、分布式算
; q3 F; r5 M; r D0 i # v+ ?/ t/ E F1 Z& P4 X
法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。
1 k# R% @0 u+ ~! v+ b 给定平面上一个点集T,其Manhattan网络由水平和垂直线段组成,并满足T中任意两点间在网络中存在Manhattan路径。可知2 o1 s ^1 Y- |( R9 K% _) ?3 `
* b' e" I8 K- |
Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner,由于具有良
+ M0 U0 O# V ?: A' r/ ^ y2 w/ k" M8 G# _; d
好的性质,其应用十分广泛,包括邻近问题(proximity problems)的求解、机器人的运动规划、通信网络的可靠性等等。
4 Z# I9 f8 H {1 t, o+ X
3 h) j4 Q" M4 ^" D# M h" K$ V 在本问题中,要求Manhattan网络中线段总长度最短,即以最小的代价构造给定点集的Manhattan网络。此外,F. Lam [5]
: i3 o9 h5 d2 G V+ `+ Y$ u
8 A A. R! J C 等人在生物序列比对问题中应用了Manhattan网络的近似算法,显著减小了搜索空间。这显示了最小Manhattan网络问题在计& C0 c! u2 Y7 L0 s% ]
9 f2 ]% H! U8 d4 m( K B
算生物学中的应用。8 O, T; t8 ]# g
由此可见,这一问题的研究无论在理论还是实际中都有十分重要的意义。( T8 z2 m }. M4 R( N2 T
最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan [4] 于1999年最早提出。之后,许多学者研 I. W- {) \) [
) c. @% p4 y! l0 n' d: v5 W
究并给出了这一问题多项式时间近似算法。之前通过组合方法设计的最佳近似算法(3-近似)由M. Benkert [1] 等人在
" \2 E5 g8 S; O $ A3 w& g" L/ t. G! ]6 X1 q3 x
2004年给出。2005年,V. Chepoi [2] 等人提出了基于线性规划的2-近似算法,这是目前所知关于这一问题的最好近似度。
4 v' j$ J( x- }; z9 z, t 在过去半年的研究中,我在朱洪教授的指导下得到了该问题的2-近似算法。这一结果被国际学术会议AAIM接受,同时获得了7 b; `1 I! f, A& ?( e
; G& M4 w+ U! `- w. Q' O
审稿人的好评。在此之前,同一近似度的算法(V. Chepoi [2], 2005)的时间复杂度高达Ω(n^8),而我们的算法时间复杂+ G2 {2 ]( w! h
* }, Y) L ~: Q4 f4 Y) k( A8 S
度仅为O(n^2)。此外,我们在这一问题的算法的设计和证明中首次应用了由D. E. Knuth和F. F. Yao [3] 提出的动态规划
1 ~& g* L9 {9 s H
& x& z# j+ l# c4 I. z1 }0 V/ L 加速方法,将动态规划过程的时间复杂度由O(n^3)降低到O(n^2)。
+ u m; k- ]& L7 H$ a' K6 g9 k 迄今为止,最小 Manhattan 网络问题的是否NP-难问题仍属未知,其不可近似性亦不清楚。因此,研究这一问题所属的复杂: f$ c* h) h5 E$ z
& w9 Z9 f- q/ G, G X5 V+ y
性类将具有极大的理论意义和实际价值。) @3 B( M) n1 w. H: K9 r. {
$ U( U- t- F) T% ?) M+ k
我们预期要解决的问题和解决途径包括:( Q" ^% h% e$ z7 l* a( z& ^
: L4 L: K) T+ v( N
(1)设计出具有更优近似度的近似算法。近似算法的设计方法主要包括:局部搜索,线性规划方法,原始对偶(primal-dual" [' n- I( _( l0 U) J' ]
! Z: i2 g3 a& l6 W# [0 b2 D
)方法等。本问题已知的近似算法可以分为两类:一类方法是将全局最优网络问题规约为局部最优网络问题,再通过局部网
- N. j' }( H2 s$ @' l f- X
/ ? ?7 C5 f0 N3 V# { 络的组合达到全局的较优解,如M. Benkert 等人在文献[1]提出的3-近似算法。在这一方法的使用中,我们已取得了国际领$ C6 b/ R( ~4 Q R1 M% ~( G' `
: H2 B( i* V5 X) R4 i 先的成果。另一类则基于线性规划方法,如V. Chepoi等人在文献[2]提出的2-近似算法。! k7 C) E i" P
在第一阶段的研究中,一方面在我们已知的最好近似算法基础上,对问题的性质进行更细致地分析以尝试改进;另一方面对
* X. y. L6 N3 L: z + Q8 m/ d' r& O7 q! V5 C8 `
近似算法的设计进行系统的学习,探索其他的算法设计思路。
# Z5 G! W0 v5 h% } 预计研究时间:2008/5-2008/11
* M4 Y S. \- c- o- T / l5 t# V" p* f
(2)研究该问题所属的复杂性类。尽管在过去的近十年里,最小Mahattan网络问题受到许多西方计算机科学家的重视,但是9 @, ^8 X. A( t4 [
; r! {# s+ P( b V0 ~6 T% `' M 到目前为止,人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是NP-完全的,但到目前为止还没有人给+ ]. N6 N# D$ r- {* n9 N
/ Q* K/ Y; C/ V" H 出有效的证明。* S6 U7 ?# p" E) N# S: D
一般来讲,证明一个问题是NP-完全的基本方式是将一已知的NP完全问题归约到所研究的问题上。这方面,已知的NP-完全的. v. g3 u: f7 n" m* G
R6 |" n: f" S; ~) A) Q ]" _ 计算几何和组合最优化问题的归约过程将具有很大参考价值。例如V. Chepoi [2] 在论文中提到的与最小Manhattan网络问. K% M$ p y7 `7 w8 D! U" |" D) P, w
* l: b* A# i; w
题相当类似的RSA问题,已经由W.Shi 和C. Su [6] 给出了从Planar-3-SAT问题到该问题的归约,从而证明了该问题为NP-完; Z& a @! x! B: s! n- V+ O
8 p; t3 Z _. {& ~4 V9 C3 W" e: ]
全的。因此,我将在这一方面深入研究,通过阅读更多的计算几何学NP-完全问题规约的文章,掌握各种复杂的技巧。试图' a+ |$ J! S2 e
0 B: h( d. @+ s# m( p' h 给出最小Manhattan网络问题的类似的归约方式,从而证明这一问题是NP-完全的。
. Y* W( `% g0 D/ O7 B. T5 \% a; q# ]; z! t/ z: k
; p8 w* w: ~' Y7 x' C+ v呵呵,我觉得高教杯出类似这样的题,意义重大。 |
zan
|