2004-3-15 13:21
carol
<span style='font-size:14pt;line-height:100%'><span style='color:blue'>具有障碍物的欧几里德最短路径问题及其实现</span></span><br /><br />撰文：曾毅<br />最后更新：2004年3月13日<br /><br />声明：文章由我执笔整理，程序代码由Kenji Ikeda写于1997年<br /><br />两个有障碍物地点之间的最短路径问题。不是一个新问题，很久以前就有人提出并解决了这个问题。在历史上这个问题是计算几何学中的一个经典课题。被称为具有障碍物的欧几里德最短路径问题(ESP0)。ESPO可以描述如下:给定平面中两点s和t，及多边形障碍物集Ω={ω1,ω2,...,ωk}，要求由s至t并避开所有障碍物的最短路径。<br /><br />平面中的ESPO问题在多项式时间内可以求解，而E^3中具有多面体障碍物时确定最短路径长度的问题是NP难的。<br /><br />一个简单的算法如下：由s到t的最短路径是一条折线链，该链的顶点是多边形障碍物的顶点。利用Dijkstra的最短路算法和可视图算法可以求解ESPO问题，其时间复杂性为0(n^2)。如果可视图是稀疏的，则在O(m+nlogn)时间内可以确定解，其中m是可视图边的数目。<br /><br />下面结合最短路径问题简单介绍一下Dijkstra算法以便大家学习：<br /><br /><span style='color:purple'>最短路径问题</span>：<br /><br />在联结图G=(V,E)中，顶点集E->R+(即是权值为正) ，在点集V中的固定顶点s，找s到V中各顶点 v的最短路径. <br /><br /><span style='color:purple'>Dijkstra算法</span><br /><br />Dijkstra算法是一种解决最短路径问题的非常有效的算法，时间复杂度为 O(|V|2):(这段是MIT一位老先生写得，不翻译了，保持原作)<br /><br /><!--QuoteBegin--><div class='quotetop'>QUOTE</div><div class='quotemain'><!--QuoteEBegin-->1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2. <br /><br />2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v. 3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1. <br /><br />4. Let Si+1 = Si cup {ui+1}. <br /><br />5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2. <br /><br />6. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2. <br /><br />7. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v. 8. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1. <br /><br />9. Let Si+1 = Si cup {ui+1}. <br /><br />10. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.<!--QuoteEnd--></div><!--QuoteEEnd--><br /><br />下面给出Kenji Ikeda老前辈的实现程序(Java版)：<br /><br /><!--c1--><div class='codetop'>CODE</div><div class='codemain'><!--ec1-->/********************************************/<br />/* Dijkstra.java */<br />/* Copyright (C) 1997, 1998, 2000 K. Ikeda */<br />/********************************************/<br /> <br />import java.applet.*;<br />import java.awt.*;<br />import java.awt.event.*;<br />import java.util.*;<br />import java.io.*;<br />import java.net.URL;<br /><br />class Node {<br /> int x;<br /> int y;<br /> int delta_plus; /* edge starts from this node */<br /> int delta_minus; /* edge terminates at this node */<br /> int dist; /* distance from the start node */<br /> int prev; /* previous node of the shortest path */<br /> int succ,pred; /* node in Sbar with finite dist. */<br /> int w;<br /> int h;<br /> int pw;<br /> int dx;<br /> int dy;<br /> String name;<br />}<br /> <br />class Edge {<br /> int rndd_plus; /* initial vertex of this edge */<br /> int rndd_minus; /* terminal vertex of this edge */<br /> int delta_plus; /* edge starts from rndd_plus */<br /> int delta_minus; /* edge terminates at rndd_minus */<br /> int len; /* length */<br /> String name;<br />}<br /><br />public class Dijkstra extends Applet implements MouseListener {<br /> int n,m;<br /> int u,snode; /* start node */<br /> int pre_s_first, pre_s_last;<br /> boolean isdigraph;<br /> int iteration, step;<br /> Node v[] = new Node[100];<br /> Edge e[] = new Edge[200];<br /><br /> int findNode(String name) {<br /> for (int i=0; i<n; i++)<br /> if (v[i].name.equals(name))<br /> return i;<br /> return -1;<br /> }<br /><br /> void input_graph(InputStream is) throws IOException {<br /> int x,y,l;<br /> String s;<br /><br /> Reader r = new BufferedReader(new InputStreamReader(is));<br /> StreamTokenizer st = new StreamTokenizer(r);<br /> st.commentChar('#');<br /> st.nextToken(); n = (int)st.nval;<br /> st.nextToken(); m = (int)st.nval;<br /> st.nextToken(); s = st.sval;<br /> isdigraph = "digraph".equals(s);<br /> for (int i = 0; i<n; i++) {<br /> Node node = new Node();<br /> st.nextToken(); node.name = st.sval;<br /> st.nextToken(); node.x = (int)st.nval;<br /> st.nextToken(); node.y = (int)st.nval;<br /> v[i] = node;<br /> }<br /> for (int i = 0; i<m; i++) {<br /> Edge edge = new Edge();<br /> st.nextToken(); edge.name = st.sval;<br /> switch (st.nextToken()) {<br /> case StreamTokenizer.TT_NUMBER:<br /> edge.rndd_plus = (int)st.nval;<br /> break;<br /> case StreamTokenizer.TT_WORD:<br /> edge.rndd_plus = findNode(st.sval);<br /> break;<br /> default:<br /> break;<br /> }<br /> switch (st.nextToken()) {<br /> case StreamTokenizer.TT_NUMBER:<br /> edge.rndd_minus = (int)st.nval;<br /> break;<br /> case StreamTokenizer.TT_WORD:<br /> edge.rndd_minus = findNode(st.sval);<br /> break;<br /> default:<br /> break;<br /> }<br /> st.nextToken(); edge.len = (int)st.nval;<br /> e[i] = edge;<br /> }<br /> for (int i=0; i<n; i++) {<br /> v[i].succ = v[i].pred = -2;<br /> v[i].prev = v[i].dist = -1;<br /> v[i].pw = 0;<br /> }<br /> iteration = step = 0;<br /> }<br /> <br /> void rdb() {<br /> int i,k;<br /> <br /> for (i=0; i<n; i++)<br /> v[i].delta_plus = v[i].delta_minus = -1;<br /> for (i=0; i<m; i++)<br /> e[i].delta_plus = e[i].delta_minus = -1;<br /> for (i=0; i<m; i++) {<br /> k = e[i].rndd_plus;<br /> if (v[k].delta_plus == -1)<br /> v[k].delta_plus = i;<br /> else {<br /> k = v[k].delta_plus;<br /> while(e[k].delta_plus >= 0)<br /> k = e[k].delta_plus;<br /> e[k].delta_plus = i;<br /> }<br /> k = e[i].rndd_minus;<br /> if (v[k].delta_minus == -1)<br /> v[k].delta_minus = i;<br /> else {<br /> k = v[k].delta_minus;<br /> while(e[k].delta_minus >= 0)<br /> k = e[k].delta_minus;<br /> e[k].delta_minus = i;<br /> }<br /> }<br /> }<br /> <br /> void append_pre_s(int i) {<br /> v[i].succ = v[i].pred = -1;<br /> if (pre_s_first<0)<br /> pre_s_first = i;<br /> else<br /> v[pre_s_last].succ = i;<br /> v[i].pred = pre_s_last;<br /> pre_s_last = i;<br /> }<br /><br /> void remove_pre_s(int i) {<br /> int succ = v[i].succ;<br /> int pred = v[i].pred;<br /> <br /> if (succ>=0)<br /> v[succ].pred = pred;<br /> else<br /> pre_s_last = pred;<br /> if (pred>=0)<br /> v[pred].succ = succ;<br /> else<br /> pre_s_first = succ;<br /> }<br /> <br /> void step1() { /* initialize */<br /> u = snode;<br /> for (int i=0; i<n; i++) {<br /> v[i].succ = v[i].pred = -2;<br /> v[i].prev = v[i].dist = -1;<br /> }<br /> v[u].succ = -3;<br /> v[u].dist = 0;<br /> pre_s_first = pre_s_last = -1;<br /> }<br /> <br /> void step2() { /* replace labels */<br /> int i,j;<br /> <br /> j = v[u].delta_plus;<br /> while (j>=0) {<br /> i = e[j].rndd_minus;<br /> if ((v[i].succ>=-2)&&((v[i].dist<0)||<br /> (v[i].dist>v[u].dist+e[j].len))) {<br /> if (v[i].dist<0)<br /> append_pre_s(i);<br /> v[i].dist = v[u].dist + e[j].len;<br /> v[i].prev = u; /* label */<br /> }<br /> j = e[j].delta_plus;<br /> }<br /> if (!isdigraph) {<br /> j = v[u].delta_minus;<br /> while (j>=0) {<br /> i = e[j].rndd_plus;<br /> if ((v[i].succ>=-2)&&((v[i].dist<0)||<br /> (v[i].dist>v[u].dist+e[j].len))) {<br /> if (v[i].dist<0)<br /> append_pre_s(i);<br /> v[i].dist = v[u].dist + e[j].len;<br /> v[i].prev = u; /* label */<br /> }<br /> j = e[j].delta_minus;<br /> }<br /> }<br /> v[u].succ = -4;<br /> }<br /><br /> void step3() { /* find the shortest node in Sbar */<br /> int i,rho;<br /> <br /> rho = -1;<br /> for (i = pre_s_first; i>=0; i = v[i].succ) {<br /> if ((rho < 0)||(rho>v[i].dist)) {<br /> rho = v[i].dist;<br /> u = i;<br /> }<br /> }<br /> remove_pre_s(u);<br /> v[u].succ = -3;<br /> }<br /><br /> void step4() {<br /> v[u].succ = -4;<br /> }<br /> <br /> double weight(Node n, double x, double y) {<br /> double w,z,xx,yy;<br /> w = 0;<br /> for (int j = n.delta_plus; j>=0; j=e[j].delta_plus) {<br /> xx = (double)(v[e[j].rndd_minus].x - n.x);<br /> yy = (double)(v[e[j].rndd_minus].y - n.y);<br /> z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+.0;<br /> w += z*z*z*z;<br /> }<br /> for (int j = n.delta_minus; j>=0; j=e[j].delta_minus) {<br /> xx = (double)(v[e[j].rndd_plus].x - n.x);<br /> yy = (double)(v[e[j].rndd_plus].y - n.y);<br /> z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0;<br /> w += z*z*z*z;<br /> }<br /> return w;<br /> }<br /><br /> void init_sub() {<br /> int x[] = {1, 0, -1, 1, 0, -1};<br /> int y[] = {1, 1, 1, -1, -1, -1};<br /> int i,j,k;<br /> double w,z;<br /> <br /> for (i=0; i<n; i++) {<br /> k=0;<br /> w=weight(v[i],(double)x[0],(double)y[0]);<br /> for (j=1; j<6; j++) {<br /> z=weight(v[i],(double)x[j],(double)y[j]);<br /> if (z<w) {<br /> w = z;<br /> k = j;<br /> }<br /> }<br /> v[i].dx = x[k];<br /> v[i].dy = y[k];<br /> }<br /> }<br /> <br /> public void init() {<br /> String mdname = getParameter("inputfile");<br /> try {<br /> InputStream is;<br /> <br /> is = new URL(getDocumentBase(),mdname).openStream();<br /> input_graph(is);<br /> try {<br /> if (is != null)<br /> is.close();<br /> } catch(Exception e) {<br /> }<br /> } catch (FileNotFoundException e) {<br /> System.err.println("File not found.");<br /> } catch (IOException e) {<br /> System.err.println("Cannot access file.");<br /> }<br /> <br /> String s = getParameter("start");<br /> if (s != null)<br /> snode = Integer.parseInt(s);<br /> else<br /> snode = 0;<br /> <br /> setBackground(Color.white);<br /> rdb();<br /> init_sub();<br /> addMouseListener(this);<br /> }<br /> <br /> public void paintNode(Graphics g, Node n, FontMetrics fm) {<br /> String s;<br /> int x = n.x;<br /> int y = n.y;<br /> int w = fm.stringWidth(n.name) + 10;<br /> int h = fm.getHeight() + 4;<br /> n.w = w;<br /> n.h = h;<br /> <br /> if (n.succ<-2)<br /> g.setColor(Color.blue);<br /> else if (n.succ==-2)<br /> g.setColor(Color.gray);<br /> else<br /> g.setColor(Color.red);<br /> <br /> g.drawRect(x-w/2,y-h/2,w,h);<br /> <br /> if (n.succ==-4)<br /> g.setColor(Color.cyan);<br /> else if (n.succ==-3)<br /> g.setColor(Color.pink);<br /> else if (n.succ>-2)<br /> g.setColor(Color.yellow);<br /> else<br /> g.setColor(getBackground());<br /> <br /> g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);<br /> <br /> g.setColor(Color.black);<br /> g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent());<br /> <br /> <br /> if (n.dist<0)<br /> s = "";<br /> else<br /> s = ""+n.dist;<br /> w = fm.stringWidth(s) + 10;<br /> x += (h+1)*n.dx; y += (h+1)*n.dy;<br /> g.setColor(getBackground());<br /> g.fillRect(x-n.pw/2,y-h/2,n.pw,h);<br /> n.pw = w;<br /> if (n.succ<-2)<br /> g.setColor(Color.blue);<br /> else<br /> g.setColor(Color.red);<br /> g.drawString(s,x-(w-10)/2,y-(h-4)/2+fm.getAscent());<br /> }<br /> <br /> int [] xy(int a, int b, int w, int h) {<br /> int x[] = new int[2];<br /> <br /> if (Math.abs(w*b)>=Math.abs(h*a)) {<br /> x[0] = ((b>=0)?1:-1)*a*h/b/2;<br /> x[1] = ((b>=0)?1:-1)*h/2;<br /> } else {<br /> x[0] = ((a>=0)?1:-1)*w/2;<br /> x[1] = ((a>=0)?1:-1)*b*w/a/2;<br /> }<br /><br /> return x;<br /> }<br /> <br /> void drawArrow(Graphics g,int x1,int y1,int x2,int y2) {<br /> int a = x1-x2;<br /> int b = y1-y2;<br /> <br /> if (isdigraph) {<br /> double aa = Math.sqrt(a*a+b*b)/16.0;<br /> double bb = b/aa;<br /> aa = a/aa;<br /> g.drawLine(x2,y2,x2+(int)((aa*12+bb*5)/13),y2+(int)((-aa*5+bb*12)/13));<br /> g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),y2+(int)((aa*5+bb*12)/13));<br /> }<br /> g.drawLine(x1,y1,x2,y2);<br /> }<br /> <br /> public void paintEdge(Graphics g, Edge e, FontMetrics fm) {<br /> Node v1 = v[e.rndd_plus];<br /> Node v2 = v[e.rndd_minus];<br /> <br /> int a = v1.x-v2.x;<br /> int b = v1.y-v2.y;<br /> <br /> int x1[] = xy(-a,-b,v1.w,v1.h);<br /> int x2[] = xy(a,b,v2.w,v2.h);<br /> <br /> if (v2.prev == e.rndd_plus) {<br /> if ((v1.succ<-2)&&(v2.succ>=-2))<br /> g.setColor(Color.red);<br /> else<br /> g.setColor(Color.blue);<br /> } else {<br /> g.setColor(Color.lightGray);<br /> }<br /> if ((!isdigraph)&&(v1.prev == e.rndd_minus)) {<br /> if ((v2.succ<-2)&&(v1.succ>=-2))<br /> g.setColor(Color.red);<br /> else<br /> g.setColor(Color.blue);<br /> }<br /> drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]);<br /> int w = fm.stringWidth("" + e.len);<br /> int h = fm.getHeight();<br /> <br /> g.setColor(getBackground());<br /> g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h);<br /><br /> if ((v2.prev == e.rndd_plus)||<br /> ((!isdigraph)&&(v1.prev == e.rndd_minus)))<br /> g.setColor(Color.black);<br /> else<br /> g.setColor(Color.lightGray);<br /> g.drawString("" + e.len,(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent());<br /> }<br /> <br /> public void paint(Graphics g) {<br /> FontMetrics fm = g.getFontMetrics();<br /> for (int i=0; i<n; i++)<br /> paintNode(g,v[i],fm);<br /> for (int i=0; i<m; i++)<br /> paintEdge(g,e[i],fm);<br /> }<br /> <br /> public void update(Graphics g) {<br /> paint(g);<br /> }<br /> <br /> public void mousePressed(MouseEvent ev) {<br /> if (iteration==0) {<br /> step1();<br /> iteration++;<br /> step = 2;<br /> } else if (iteration>=n) {<br /> step4();<br /> iteration = 0;<br /> } else {<br /> if (step == 2) {<br /> step2();<br /> step = 3;<br /> } else {<br /> step3();<br /> iteration++;<br /> step = 2;<br /> }<br /> }<br /> repaint();<br /> }<br /> public void mouseClicked(MouseEvent event) {}<br /> public void mouseReleased(MouseEvent event) {}<br /> public void mouseEntered(MouseEvent event) {}<br /> public void mouseExited(MouseEvent event) {}<br />}<!--c2--></div><!--ec2--><br /><br /><span style='color:blue'>对于该问题还有一些更好的算法，下面作一些简单的介绍：利用最短路径映射SPM(s,Ω)在O(n(k+logn))时间内求解任意多边形障碍物的ESPO问题的方法是由Reif和Storer提出的。如果给定SPM(s,Ω)，则在O(logn)时间内可以确定包含t的域，而在0(b+logn)时间内能够确定到t的路径，其中b是路径上线段的数目。Welzl等人利用可视图给出了求解平面上n条线段的ESPO问题的算法，该算法要求0(n^2)时间。不难修改这个算法使其能处理多边形障碍物，并且具有相同的时间复杂性。注意，如果使用可视图方法，那么对限界0(n^2)将不可能改进。多边形物体中两个物体(而非点)之间的最短路径的0(n^2)算法是已知的。当n是平行线段集合时，Lee和Preparata提出θ(nlogn)平面扫描算法。线段穿过扫描线并且把最短路径映射到扫描线。平面上没有最短路径的0(n^2)算法能处理避开n条任意相交的线段。Rohnert给出平面中避开k个凸障碍物最短路径的O(nlogn+k^2)时间的算法。这个时间限界在O(k^2logn+n)时间和O(n+k^2)空间预处理障碍物的条件下达到。预处理包括构造可视图的子图。Rohnert还给出平面中避开k个凸障碍物最短路径的O(knlogn)时间和O(n)空间的算法。后者不需预先处理障碍物，而是利用Dijkstra最短路径算法在线计算可视性。当平面中有k个凸障碍物并且其边界至多相交两次时，Rohnert给出的算法能找到平面中任意两点之间的最短路径，其时间复杂性为O(nlogn+k^2)。这个时间限界在O(nlogn+k^3)时间和O(n+k^2)空间预处理障碍物的条件下达到。<br /> </span>
页: [1]
查看完整版本: 逻辑算法 - 具有障碍物的欧几里德最短路径问题及其实现
Powered by Discuz! Archiver 5.5.0 © 2001-2006 Comsenz Inc.