数学建模社区-数学中国

标题: 最小曼哈顿网路算法 [打印本页]
作者: xiaobingforever    时间: 2009-9-3 19:22
标题: 最小曼哈顿网路算法
觉得是个有意思的问题，希望有兴趣的朋友一起探讨，当然这个世界级猜想早几个月才被复旦大学大三学生郭泽宇破解，很牛！也给我们大学本科阶段追求创新一些启示，这几天正在做中南大学的培训题《城市生活垃圾管理问题》，设计到垃圾收运路线的设计，而城市垃圾收运路线正是一个曼哈顿网络问题，当然是最小时间，还是最短路径，看个人理解，要解决这个问题看似方法很多，大多数是当做一个TSP图论问题来求解，或者建立规划模型，用的方法也大多是模拟退火、遗传算法、蚁群算法等等，比较有新意是分析曼哈顿的特殊结构，运用基于约束的网格聚类方法从类的角度考虑，就降低了数百个收集点的运算复杂度。当然更好的方法就是破解这个世界级难题，从而一劳永逸。到知网等网站搜了下，相关的学术文献很少， 有点意思。  
, ^9 K& g% U" D: F! K/ E4 M              最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成电路（VLSI）设计、分布式算
9 @! I1 _$ ?: D: U- g+ W　　　　
- l- q9 s$ K% ?0 s" G; [6 J2 z3 ~0 b+ |- R　　　　法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。
" d# t6 H2 R7 V　　　　给定平面上一个点集T，其Manhattan网络由水平和垂直线段组成，并满足T中任意两点间在网络中存在Manhattan路径。可知9 q: W6 X4 D, q- Z: @+ S) j
　　　　
0 e; p% w9 @5 Q! |　　　　Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner，由于具有良5 ^6 v! s9 N9 i# V& I. Y/ T6 `
　　　　
; \! m' u0 u( B1 S0 i　　　　好的性质，其应用十分广泛，包括邻近问题（proximity problems）的求解、机器人的运动规划、通信网络的可靠性等等。
6 y" j1 B3 f0 m- \1 _8 b& c　　　　4 l4 R& B$ Y1 O, I- y+ T
　　　　在本问题中，要求Manhattan网络中线段总长度最短，即以最小的代价构造给定点集的Manhattan网络。此外，F. Lam [5]
% ?2 F( Q& K5 @$ ^4 G) B0 U　　　　# \) {" [3 `" M5 N* @
　　　　等人在生物序列比对问题中应用了Manhattan网络的近似算法，显著减小了搜索空间。这显示了最小Manhattan网络问题在计% _4 t4 x% {5 T6 H( Z% _+ l9 J% p
　　　　/ Z% ~- N* }2 z4 b
　　　　算生物学中的应用。+ \! x- z& K9 a% k% a3 |/ D
　　　　由此可见，这一问题的研究无论在理论还是实际中都有十分重要的意义。& r# G+ r: i8 P' n4 H! k* W
　　　　最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan [4] 于1999年最早提出。之后，许多学者研
- d  p0 ]/ m4 _: d5 k3 k　　　　
0 D7 _& G1 h$ K: @- n* B% M　　　　究并给出了这一问题多项式时间近似算法。之前通过组合方法设计的最佳近似算法（3-近似）由M. Benkert [1] 等人在
. i: j7 [" Q$ `4 [/ L　　　　7 b$ F: |2 L5 m9 h6 D; k, i
　　　　2004年给出。2005年，V. Chepoi [2] 等人提出了基于线性规划的2-近似算法，这是目前所知关于这一问题的最好近似度。
# B7 i- z7 v4 A5 [9 z: W% X8 K+ d6 W　　　　在过去半年的研究中，我在朱洪教授的指导下得到了该问题的2-近似算法。这一结果被国际学术会议AAIM接受，同时获得了9 U0 G3 f3 h' H
　　　　- g2 `2 ^2 d, `/ e3 V
　　　　审稿人的好评。在此之前，同一近似度的算法（V. Chepoi [2], 2005）的时间复杂度高达Ω(n^8)，而我们的算法时间复杂0 A% S# m* r1 j
　　　　$ r1 o. M. h( p: |
　　　　度仅为O(n^2)。此外，我们在这一问题的算法的设计和证明中首次应用了由D. E. Knuth和F. F. Yao [3] 提出的动态规划# @% D0 Z3 H% v! q+ y* d5 R
　　　　, B! B' j( Q: Q# W7 n4 d$ E
　　　　加速方法，将动态规划过程的时间复杂度由O(n^3)降低到O(n^2)。9 a- h  G4 I# t
　　　　迄今为止，最小 Manhattan 网络问题的是否NP-难问题仍属未知，其不可近似性亦不清楚。因此，研究这一问题所属的复杂" `9 _: A5 R* ~7 q- I
　　　　6 O/ p- N# ]6 L- V
　　　　性类将具有极大的理论意义和实际价值。
7 N; N1 ~) I4 L- t　　　　
4 s' g* `1 o; r0 L　　　　我们预期要解决的问题和解决途径包括：9 U. r- j1 d! c# t) ], T' j5 Q* t
　　　　8 M- Q% x) n, ^
　　　　(1)设计出具有更优近似度的近似算法。近似算法的设计方法主要包括：局部搜索，线性规划方法，原始对偶（primal-dual
6 A0 h! d9 A9 r* j- P; z$ _　　　　
( y3 f: P7 o2 ]　　　　）方法等。本问题已知的近似算法可以分为两类：一类方法是将全局最优网络问题规约为局部最优网络问题，再通过局部网
5 J& n0 |2 Y, I8 \( B8 z　　　　
. `  n( p5 l- m" Q! M　　　　络的组合达到全局的较优解，如M. Benkert 等人在文献[1]提出的3-近似算法。在这一方法的使用中，我们已取得了国际领# a1 G" n( p7 v; L4 I& r
　　　　
$ y) c; _* o* d6 l7 A: |8 V　　　　先的成果。另一类则基于线性规划方法，如V. Chepoi等人在文献[2]提出的2-近似算法。
0 t/ s5 S; i! ~( T* l- I8 C) R　　　　在第一阶段的研究中，一方面在我们已知的最好近似算法基础上，对问题的性质进行更细致地分析以尝试改进；另一方面对
. t3 x0 b+ f! z　　　　3 g* _) |& Y2 X9 A4 N% b
　　　　近似算法的设计进行系统的学习，探索其他的算法设计思路。
! T* K6 H- q" P+ K4 S6 [　　　　预计研究时间：2008/5-2008/114 f6 Q3 [& c, a- s4 C9 g
　　　　" o" f0 b* q0 c( {8 A4 d
　　　　(2)研究该问题所属的复杂性类。尽管在过去的近十年里，最小Mahattan网络问题受到许多西方计算机科学家的重视，但是! z3 ?, G% `" A
　　　　* O2 W- s) b/ D( m
　　　　到目前为止，人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是NP-完全的，但到目前为止还没有人给
7 O' ^# P$ U7 {! A; q/ A3 Z　　　　
3 M& {% d& g& {8 T# @% U' C　　　　出有效的证明。7 O3 h  S4 `( h5 g, s7 @8 J' x8 W
　　　　一般来讲，证明一个问题是NP-完全的基本方式是将一已知的NP完全问题归约到所研究的问题上。这方面，已知的NP-完全的* w  X2 m7 e! I7 o: B% ?
　　　　1 \; ], Z9 T) L: [4 X3 P
　　　　计算几何和组合最优化问题的归约过程将具有很大参考价值。例如V. Chepoi [2] 在论文中提到的与最小Manhattan网络问
% H- x/ c" g$ _4 h/ s& v  |1 j　　　　
4 u# j6 _2 y$ u8 o8 P. c5 E　　　　题相当类似的RSA问题，已经由W.Shi 和C. Su [6] 给出了从Planar-3-SAT问题到该问题的归约，从而证明了该问题为NP-完
( |- j2 S) |3 k" e+ E　　　　
3 J4 p. A( H# b* [$ o$ t5 B) v# R　　　　全的。因此，我将在这一方面深入研究，通过阅读更多的计算几何学NP-完全问题规约的文章，掌握各种复杂的技巧。试图
& s  g+ _$ |2 @+ T% z　　　　$ r* @' @" x; T) t0 h/ i( m, u
　　　　给出最小Manhattan网络问题的类似的归约方式，从而证明这一问题是NP-完全的。
+ U7 Y. k9 _- g, M' b: _. F8 O- `$ P( Y" U. C) ]" ]9 f1 W* F+ E3 W7 K

# b, R8 [4 P: p1 C6 R4 U呵呵，我觉得高教杯出类似这样的题，意义重大。
作者: 高肖鹏    时间: 2009-9-3 19:32
where????????????
作者: 104476285    时间: 2009-9-3 20:05
恩  很有意思
作者: 小小雨112233    时间: 2009-9-3 20:15
这样啊圆满你来时、
作者: 小小雨112233    时间: 2009-9-3 20:48
where????????????
作者: 小小雨112233    时间: 2009-9-3 20:49
恩  很有意思
作者: 小小雨112233    时间: 2009-9-3 20:52
呵呵，我觉得高教杯出类似这样的题，意义重大。



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5