QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 6403|回复: 6
打印 上一主题 下一主题

最小曼哈顿网路算法

[复制链接]
字体大小: 正常 放大

19

主题

9

听众

271

积分

升级  85.5%

该用户从未签到

新人进步奖

跳转到指定楼层
1#
发表于 2009-9-3 19:22 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
觉得是个有意思的问题,希望有兴趣的朋友一起探讨,当然这个世界级猜想早几个月才被复旦大学大三学生郭泽宇破解,很牛!也给我们大学本科阶段追求创新一些启示,这几天正在做中南大学的培训题《城市生活垃圾管理问题》,设计到垃圾收运路线的设计,而城市垃圾收运路线正是一个曼哈顿网络问题,当然是最小时间,还是最短路径,看个人理解,要解决这个问题看似方法很多,大多数是当做一个TSP图论问题来求解,或者建立规划模型,用的方法也大多是模拟退火、遗传算法、蚁群算法等等,比较有新意是分析曼哈顿的特殊结构,运用基于约束的网格聚类方法从类的角度考虑,就降低了数百个收集点的运算复杂度。当然更好的方法就是破解这个世界级难题,从而一劳永逸。到知网等网站搜了下,相关的学术文献很少, 有点意思。  & B2 z% P5 q" X$ q
              最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成电路(VLSI)设计、分布式算
3 `. B* |, G8 ~! E! P+ r) m0 C    ) x4 F& B6 e) k& H+ w
    法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。
5 p$ M; ]9 Q1 J3 q# P5 d8 N$ o1 {$ {( i% D    给定平面上一个点集T,其Manhattan网络由水平和垂直线段组成,并满足T中任意两点间在网络中存在Manhattan路径。可知
1 v6 _0 c% }0 k4 B    
* A" `( u! M' a! W" G% C    Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner,由于具有良
2 W$ A8 ]3 E: O  n& j$ z, \; W    
% Z9 q1 \& o2 m) C  n& S    好的性质,其应用十分广泛,包括邻近问题(proximity problems)的求解、机器人的运动规划、通信网络的可靠性等等。: A! `: g" L( s7 t2 r; |
    
; R5 ]* p: Z5 e4 j    在本问题中,要求Manhattan网络中线段总长度最短,即以最小的代价构造给定点集的Manhattan网络。此外,F. Lam [5] ' X# O0 T$ @5 X" N
    
" n$ B: p  |9 v7 y" R1 L    等人在生物序列比对问题中应用了Manhattan网络的近似算法,显著减小了搜索空间。这显示了最小Manhattan网络问题在计6 C: y, m7 T1 B
    
4 J# V2 H8 L/ Q( f# t, Z    算生物学中的应用。% h  e+ F/ u( ?0 D* ?
    由此可见,这一问题的研究无论在理论还是实际中都有十分重要的意义。3 s$ C, z% c# @. u$ i0 L6 K
    最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan [4] 于1999年最早提出。之后,许多学者研
9 W9 D4 M' C' W; {: W    : ?: Z$ Q* |$ G$ s) r" j* S0 w1 i
    究并给出了这一问题多项式时间近似算法。之前通过组合方法设计的最佳近似算法(3-近似)由M. Benkert [1] 等人在$ M7 X) W5 u  _$ k* ]: O# q
    7 k* H& f2 `, b: f
    2004年给出。2005年,V. Chepoi [2] 等人提出了基于线性规划的2-近似算法,这是目前所知关于这一问题的最好近似度。4 |! ]0 \& T( M
    在过去半年的研究中,我在朱洪教授的指导下得到了该问题的2-近似算法。这一结果被国际学术会议AAIM接受,同时获得了
. w$ q% z3 V5 L5 z- K  @; i    
! M: {7 X9 h3 C6 ?4 _( G    审稿人的好评。在此之前,同一近似度的算法(V. Chepoi [2], 2005)的时间复杂度高达Ω(n^8),而我们的算法时间复杂' g8 `8 F! K2 B! ]2 W' O
    
; ]% B+ y) p" n/ n    度仅为O(n^2)。此外,我们在这一问题的算法的设计和证明中首次应用了由D. E. Knuth和F. F. Yao [3] 提出的动态规划# P9 |) j7 s8 ~& s
    
$ X# D0 C9 |3 J( j9 l1 N    加速方法,将动态规划过程的时间复杂度由O(n^3)降低到O(n^2)。, h3 ?+ k+ N: c. G; v. B
    迄今为止,最小 Manhattan 网络问题的是否NP-难问题仍属未知,其不可近似性亦不清楚。因此,研究这一问题所属的复杂
  @: L9 C5 Y) I' _: W, y    7 V( w; q  `) ^" @  r# T
    性类将具有极大的理论意义和实际价值。
' y4 A: x; i- x& W    
( v3 ~! o  K0 \. ^* e    我们预期要解决的问题和解决途径包括:- P% {4 v/ E4 ?% h
    5 k# w2 h& E! q( `) G8 {
    (1)设计出具有更优近似度的近似算法。近似算法的设计方法主要包括:局部搜索,线性规划方法,原始对偶(primal-dual
" T0 w( g# L  R4 }  X    
& i0 r$ M: y# d5 s; I    )方法等。本问题已知的近似算法可以分为两类:一类方法是将全局最优网络问题规约为局部最优网络问题,再通过局部网8 L( A2 A) k! ^$ s
    " D. j/ G3 n  E' H+ \; K5 `
    络的组合达到全局的较优解,如M. Benkert 等人在文献[1]提出的3-近似算法。在这一方法的使用中,我们已取得了国际领
* W/ t" O: A9 ?' v    
3 E3 d9 C; Z; q5 E7 b8 O    先的成果。另一类则基于线性规划方法,如V. Chepoi等人在文献[2]提出的2-近似算法。
' i# G" P/ z/ |* O$ ^    在第一阶段的研究中,一方面在我们已知的最好近似算法基础上,对问题的性质进行更细致地分析以尝试改进;另一方面对
5 i/ o; W4 I  L. ?: s5 K+ U    
0 |3 o& @' |1 s$ {2 I    近似算法的设计进行系统的学习,探索其他的算法设计思路。
8 R# w1 g0 C9 M( g2 `    预计研究时间:2008/5-2008/11  m& P  V: B' m+ |# U5 `
    
' O& C, E+ ^( P: P$ k    (2)研究该问题所属的复杂性类。尽管在过去的近十年里,最小Mahattan网络问题受到许多西方计算机科学家的重视,但是0 u* ^: f* y. L. r* K( _( |1 K% K
    / H9 d( k2 c, q5 S
    到目前为止,人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是NP-完全的,但到目前为止还没有人给
' u; n7 i/ a( b, {/ Y) k5 J1 p    9 w6 |# n2 H# U1 v- {! V
    出有效的证明。+ G: {- y" v, c$ Q5 c6 x
    一般来讲,证明一个问题是NP-完全的基本方式是将一已知的NP完全问题归约到所研究的问题上。这方面,已知的NP-完全的
7 f0 `0 i5 Q, T7 Z) M( T    
$ s9 Z) t2 [) ^" i. K6 Y& e0 a    计算几何和组合最优化问题的归约过程将具有很大参考价值。例如V. Chepoi [2] 在论文中提到的与最小Manhattan网络问& R6 i# t$ H5 w* q3 M2 y/ J
    
; r5 l* C7 [5 a, b    题相当类似的RSA问题,已经由W.Shi 和C. Su [6] 给出了从Planar-3-SAT问题到该问题的归约,从而证明了该问题为NP-完
/ v% ]4 }- }9 H  J9 p    
( J4 ?4 U- f) d, n+ R# N    全的。因此,我将在这一方面深入研究,通过阅读更多的计算几何学NP-完全问题规约的文章,掌握各种复杂的技巧。试图
9 g9 `# Y$ y( ~2 ^# }    
; K. m4 L8 N$ g6 F    给出最小Manhattan网络问题的类似的归约方式,从而证明这一问题是NP-完全的。5 p4 x" B0 R3 ~
" ?) {4 f1 |0 S* c* _4 I% D

- }* h. A; r+ O- B. L: v% x' Y呵呵,我觉得高教杯出类似这样的题,意义重大。
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
高肖鹏 实名认证       

1

主题

4

听众

159

积分

升级  29.5%

该用户从未签到

群组数学建模

回复

使用道具 举报

104476285 实名认证       

0

主题

3

听众

103

积分

升级  1.5%

该用户从未签到

群组数学建模

回复

使用道具 举报

4

主题

4

听众

426

积分

升级  42%

  • TA的每日心情
    开心
    2015-7-23 16:18
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    新人进步奖

    群组数学建摸协会

    回复

    使用道具 举报

    4

    主题

    4

    听众

    426

    积分

    升级  42%

  • TA的每日心情
    开心
    2015-7-23 16:18
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    新人进步奖

    群组数学建摸协会

    回复

    使用道具 举报

    4

    主题

    4

    听众

    426

    积分

    升级  42%

  • TA的每日心情
    开心
    2015-7-23 16:18
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    新人进步奖

    群组数学建摸协会

    回复

    使用道具 举报

    4

    主题

    4

    听众

    426

    积分

    升级  42%

  • TA的每日心情
    开心
    2015-7-23 16:18
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    新人进步奖

    群组数学建摸协会

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-16 15:15 , Processed in 0.488781 second(s), 84 queries .

    回顶部