数学建模社区-数学中国
标题:
最小曼哈顿网路算法
[打印本页]
作者:
xiaobingforever
时间:
2009-9-3 19:22
标题:
最小曼哈顿网路算法
觉得是个有意思的问题，希望有兴趣的朋友一起探讨，当然这个世界级猜想早几个月才被复旦大学大三学生郭泽宇破解，很牛！也给我们大学本科阶段追求创新一些启示，这几天正在做中南大学的培训题《城市生活垃圾管理问题》，设计到垃圾收运路线的设计，而城市垃圾收运路线正是一个曼哈顿网络问题，当然是最小时间，还是最短路径，看个人理解，要解决这个问题看似方法很多，大多数是当做一个TSP图论问题来求解，或者建立规划模型，用的方法也大多是模拟退火、遗传算法、蚁群算法等等，比较有新意是分析曼哈顿的特殊结构，运用基于约束的网格聚类方法从类的角度考虑，就降低了数百个收集点的运算复杂度。当然更好的方法就是破解这个世界级难题，从而一劳永逸。到知网等网站搜了下，相关的学术文献很少， 有点意思。
, _: c- Q3 E" a/ R5 }( X4 q
最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成电路（VLSI）设计、分布式算
2 M! _; w& a& u. E9 j. e
6 S! F, G& k$ T
法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。
& d' u) B* r) }: P& G4 [4 @* ~9 W/ A
给定平面上一个点集T，其Manhattan网络由水平和垂直线段组成，并满足T中任意两点间在网络中存在Manhattan路径。可知
$ _0 `3 D' P& ^* }; i
1 K3 _- g# P9 k' k; Q# f1 M
Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner，由于具有良
& }% L7 `# F @( \, f' R
2 _! Z M6 I; S7 ?) x$ _9 Q
好的性质，其应用十分广泛，包括邻近问题（proximity problems）的求解、机器人的运动规划、通信网络的可靠性等等。
9 u! [9 D% n7 g! y+ X1 O0 S! _- q
! x# @8 A$ G; i l& ?8 q
在本问题中，要求Manhattan网络中线段总长度最短，即以最小的代价构造给定点集的Manhattan网络。此外，F. Lam [5]
' K1 [6 N; c0 I& N
* U/ D, R5 n2 k+ R6 W2 ]. A
等人在生物序列比对问题中应用了Manhattan网络的近似算法，显著减小了搜索空间。这显示了最小Manhattan网络问题在计
- d$ s: V# l6 V5 O+ A4 E' U* ~2 l
6 ]4 \' \+ K/ f
算生物学中的应用。
4 e( v0 D0 ]/ i0 ]# E& s
由此可见，这一问题的研究无论在理论还是实际中都有十分重要的意义。
" R, L' b# u, h6 a: d* ]
最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan [4] 于1999年最早提出。之后，许多学者研
1 k% Z3 {5 m- i$ e
7 p. I i; _% q# |9 W
究并给出了这一问题多项式时间近似算法。之前通过组合方法设计的最佳近似算法（3-近似）由M. Benkert [1] 等人在
3 T6 v4 [- `) c! F1 K/ D
# G/ G* k6 u* E3 E3 Q& b5 i( [" j
2004年给出。2005年，V. Chepoi [2] 等人提出了基于线性规划的2-近似算法，这是目前所知关于这一问题的最好近似度。
$ d9 p" d* h: D
在过去半年的研究中，我在朱洪教授的指导下得到了该问题的2-近似算法。这一结果被国际学术会议AAIM接受，同时获得了
! a# v( v' o$ W5 g3 H8 z
4 ~3 u7 G, e: s4 @2 v' I
审稿人的好评。在此之前，同一近似度的算法（V. Chepoi [2], 2005）的时间复杂度高达Ω(n^8)，而我们的算法时间复杂
8 X# K2 ?1 o2 B
; ^2 ^) j& o( x
度仅为O(n^2)。此外，我们在这一问题的算法的设计和证明中首次应用了由D. E. Knuth和F. F. Yao [3] 提出的动态规划
; l: m& n8 B! y5 s1 O7 Q
9 X, S- x, @0 f$ S
加速方法，将动态规划过程的时间复杂度由O(n^3)降低到O(n^2)。
2 f6 i* j; L7 m; f& ?! g& I- z3 {( r
迄今为止，最小 Manhattan 网络问题的是否NP-难问题仍属未知，其不可近似性亦不清楚。因此，研究这一问题所属的复杂
7 V: n# ]5 m; p z0 M$ _
4 _. g* i2 {8 T& S' o
性类将具有极大的理论意义和实际价值。
; f9 k4 }5 Q" I1 ^# Q0 {& p |7 }% W
/ b0 _0 v% r+ B" _" U
我们预期要解决的问题和解决途径包括：
9 x [/ b6 ^. q( T8 m
) a+ n* b9 K4 B1 A$ B4 ^
(1)设计出具有更优近似度的近似算法。近似算法的设计方法主要包括：局部搜索，线性规划方法，原始对偶（primal-dual
* K; k; w- A- M K. v4 s- q9 B
7 c$ n1 D* |, ~$ i3 Y* T! r% p
）方法等。本问题已知的近似算法可以分为两类：一类方法是将全局最优网络问题规约为局部最优网络问题，再通过局部网
) C5 y: l9 w2 e; {1 F7 F) _
1 O p( n: v0 ?, D {0 \3 C
络的组合达到全局的较优解，如M. Benkert 等人在文献[1]提出的3-近似算法。在这一方法的使用中，我们已取得了国际领
! e! T% j# c* F' e
7 f* n1 m [9 J+ q
先的成果。另一类则基于线性规划方法，如V. Chepoi等人在文献[2]提出的2-近似算法。
2 s6 V3 c6 q7 l+ U
在第一阶段的研究中，一方面在我们已知的最好近似算法基础上，对问题的性质进行更细致地分析以尝试改进；另一方面对
1 p8 p x! a! ` t. U4 o9 a
# H) B _ `" n( B1 h1 ?
近似算法的设计进行系统的学习，探索其他的算法设计思路。
$ Y* r7 B: F3 K
预计研究时间：2008/5-2008/11
# P/ i9 O* L, k/ C* _( t& |
' O; p/ G/ f" P" T
(2)研究该问题所属的复杂性类。尽管在过去的近十年里，最小Mahattan网络问题受到许多西方计算机科学家的重视，但是
g3 a* R7 K! C
3 r; |4 ?' \- J
到目前为止，人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是NP-完全的，但到目前为止还没有人给
2 W8 X5 r s& n" k5 _9 E: s
2 Q: a: Q* X3 u
出有效的证明。
$ a# f3 O. V& \5 }9 Y
一般来讲，证明一个问题是NP-完全的基本方式是将一已知的NP完全问题归约到所研究的问题上。这方面，已知的NP-完全的
( J3 X/ u) j, g9 t3 b; {8 R( ^" W
- V$ ^7 `+ h. D6 i8 ] G5 c. R" l
计算几何和组合最优化问题的归约过程将具有很大参考价值。例如V. Chepoi [2] 在论文中提到的与最小Manhattan网络问
$ q$ X; Y5 ~/ j! S) g0 |! w) x% Q
' g: v/ v' \4 q+ H5 `
题相当类似的RSA问题，已经由W.Shi 和C. Su [6] 给出了从Planar-3-SAT问题到该问题的归约，从而证明了该问题为NP-完
1 _3 i8 K1 v5 Y J& |& r
b9 b# E6 B( ^+ _9 M/ K r
全的。因此，我将在这一方面深入研究，通过阅读更多的计算几何学NP-完全问题规约的文章，掌握各种复杂的技巧。试图
+ A0 W0 \, o& W: F' Y3 D
3 n+ n$ `. K1 z) ?$ B# r, T
给出最小Manhattan网络问题的类似的归约方式，从而证明这一问题是NP-完全的。
3 J, a, C1 \2 P: [6 H$ L% P$ c- u
5 K/ S$ L& a; C
. a# U$ |6 X" r6 B) Q& f- E
呵呵，我觉得高教杯出类似这样的题，意义重大。
作者:
高肖鹏
时间:
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