新建 文本文档.txt

具有障碍物的欧几里德最短路径问题及其实现

具有障碍物的欧几里德最短路径问题及其实现 
在以往的.NET大赛中有很多学校都选择了“我的大学.NET”作为题目。这次也不例外，在这个项目中有一块比较重要的就是学校电子地图的制作，难点之一就是两个有障碍物地点之间的最短路径问题。下面我就简单的介绍一下这个问题的处理方法：这个问题不是一个新问题，很久以前就有人提出并解决了这个问题。在历史上这个问题是计算几何学中的一个经典课题。被称为具有障碍物的欧几里德最短路径问题(ESP0)。 
ESPO可以描述如下:给定平面中两点s和t，及多边形障碍物集Ω={ω1,ω2,...,ωk}，要求由s至t并避开所有障碍物的最短路径。 
平面中的ESPO问题在多项式时间内可以求解，而E^3中具有多面体障碍物时确定最短路径长度的问题是NP难的。 
一个简单的算法如下：由s到t的最短路径是一条折线链，该链的顶点是多边形障碍物的顶点。利用Dijkstra的最短路算法和可视图算法可以求解ESPO问题，其时间复杂性为0(n^2)。如果可视图是稀疏的，则在O(m+nlogn)时间内可以确定解，其中m是可视图边的数目。 
下面结合最短路径问题简单介绍一下Dijkstra算法以便大家学习： 
最短路径问题： 
在联结图 G=(V,E)中， 顶点集E->R+（即是权值为正） ，在点集V中的固定顶点s，寻找s到V中各顶点 v的最短路径. 
Dijkstra算法 
Dijkstra算法是一种解决最短路径问题的非常有效的算法，时间复杂度为 O(|V|2)：（这段是MIT一位老先生写得，不翻译了，保持原作） 
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. 
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. 
4. Let Si+1 = Si cup {ui+1}. 
5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2. 
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. 
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. 
9. Let Si+1 = Si cup {ui+1}. 
10. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2. 
下面给出Kenji Ikeda老前辈的实现程序（Java版）： 
/********************************************/ 
/* Dijkstra.java                            */ 
/* Copyright (C) 1997, 1998, 2000  K. Ikeda */ 
/********************************************/ 

import java.applet.*; 
import java.awt.*; 
import java.awt.event.*; 
import java.util.*; 
import java.io.*; 
import java.net.URL; 

class Node { 
int x; 
int y; 
int delta_plus; /* edge starts from this node */ 
int delta_minus; /* edge terminates at this node */ 
int dist; /* distance from the start node */ 
int prev; /* previous node of the shortest path */ 
int succ,pred; /* node in Sbar with finite dist. */ 
int w; 
int h; 
int pw; 
int dx; 
int dy; 
String name; 
} 

class Edge { 
int rndd_plus; /* initial vertex of this edge */ 
int rndd_minus; /* terminal vertex of this edge */ 
int delta_plus; /* edge starts from rndd_plus */ 
int delta_minus; /* edge terminates at rndd_minus */ 
int len; /* length */ 
String name; 
} 

public class Dijkstra extends Applet implements MouseListener { 
int n,m; 
int u,snode; /* start node */ 
int pre_s_first, pre_s_last; 
boolean isdigraph; 
int iteration, step; 
Node v[] = new Node[100]; 
Edge e[] = new Edge[200]; 

int findNode(String name) { 
for (int i=0; i<n; i++) 
if (v[i].name.equals(name)) 
return i; 
return -1; 
} 

void input_graph(InputStream is) throws IOException { 
int x,y,l; 
String s; 

Reader r = new BufferedReader(new InputStreamReader(is)); 
StreamTokenizer st = new StreamTokenizer(r); 
st.commentChar('#'); 
st.nextToken(); n = (int)st.nval; 
st.nextToken(); m = (int)st.nval; 
st.nextToken(); s = st.sval; 
isdigraph = "digraph".equals(s); 
for (int i = 0; i<n; i++) { 
Node node = new Node(); 
st.nextToken(); node.name = st.sval; 
st.nextToken(); node.x = (int)st.nval; 
st.nextToken(); node.y = (int)st.nval; 
v[i] = node; 
} 
for (int i = 0; i<m; i++) { 
Edge edge = new Edge(); 
st.nextToken(); edge.name = st.sval; 
switch (st.nextToken()) { 
case StreamTokenizer.TT_NUMBER: 
edge.rndd_plus = (int)st.nval; 
break; 
case StreamTokenizer.TT_WORD: 
edge.rndd_plus = findNode(st.sval); 
break; 
default: 
break; 
} 
switch (st.nextToken()) { 
case StreamTokenizer.TT_NUMBER: 
edge.rndd_minus = (int)st.nval; 
break; 
case StreamTokenizer.TT_WORD: 
edge.rndd_minus = findNode(st.sval); 
break; 
default: 
break; 
} 
st.nextToken(); edge.len = (int)st.nval; 
e[i] = edge; 
} 
for (int i=0; i<n; i++) { 
v[i].succ = v[i].pred = -2; 
v[i].prev = v[i].dist = -1; 
v[i].pw = 0; 
} 
iteration = step = 0; 
} 

void rdb() { 
int i,k; 

for (i=0; i<n; i++) 
v[i].delta_plus = v[i].delta_minus = -1; 
for (i=0; i<m; i++) 
e[i].delta_plus = e[i].delta_minus = -1; 
for (i=0; i<m; i++) { 
k = e[i].rndd_plus; 
if (v[k].delta_plus == -1) 
v[k].delta_plus = i; 
else { 
k = v[k].delta_plus; 
while(e[k].delta_plus >= 0) 
k = e[k].delta_plus; 
e[k].delta_plus = i; 
} 
k = e[i].rndd_minus; 
if (v[k].delta_minus == -1) 
v[k].delta_minus = i; 
else { 
k = v[k].delta_minus; 
while(e[k].delta_minus >= 0) 
k = e[k].delta_minus; 
e[k].delta_minus = i; 
} 
} 
} 

void append_pre_s(int i) { 
v[i].succ = v[i].pred = -1; 
if (pre_s_first<0) 
pre_s_first = i; 
else 
v[pre_s_last].succ = i; 
v[i].pred = pre_s_last; 
pre_s_last = i; 
} 

void remove_pre_s(int i) { 
int succ = v[i].succ; 
int pred = v[i].pred; 

if (succ>=0) 
v[succ].pred = pred; 
else 
pre_s_last = pred; 
if (pred>=0) 
v[pred].succ = succ; 
else 
pre_s_first = succ; 
} 

void step1() { /* initialize */ 
u = snode; 
for (int i=0; i<n; i++) { 
v[i].succ = v[i].pred = -2; 
v[i].prev = v[i].dist = -1; 
} 
v[u].succ = -3; 
v[u].dist = 0; 
pre_s_first = pre_s_last = -1; 
} 

void step2() { /* replace labels */ 
int i,j; 

j = v[u].delta_plus; 
while (j>=0) { 
i = e[j].rndd_minus; 
if ((v[i].succ>=-2)&&((v[i].dist<0)|| 
(v[i].dist>v[u].dist+e[j].len))) { 
if (v[i].dist<0) 
append_pre_s(i); 
v[i].dist = v[u].dist + e[j].len; 
v[i].prev = u;   /* label */ 
} 
j = e[j].delta_plus; 
} 
if (!isdigraph) { 
j = v[u].delta_minus; 
while (j>=0) { 
i = e[j].rndd_plus; 
if ((v[i].succ>=-2)&&((v[i].dist<0)|| 
(v[i].dist>v[u].dist+e[j].len))) { 
if (v[i].dist<0) 
append_pre_s(i); 
v[i].dist = v[u].dist + e[j].len; 
v[i].prev = u;   /* label */ 
} 
j = e[j].delta_minus; 
} 
} 
v[u].succ = -4; 
} 

void step3() { /* find the shortest node in Sbar */ 
int i,rho; 

rho = -1; 
for (i = pre_s_first; i>=0; i = v[i].succ) { 
if ((rho < 0)||(rho>v[i].dist)) { 
rho = v[i].dist; 
u = i; 
} 
} 
remove_pre_s(u); 
v[u].succ = -3; 
} 

void step4() { 
v[u].succ = -4; 
} 

double weight(Node n, double x, double y) { 
double w,z,xx,yy; 

w = 0; 
for (int j = n.delta_plus; j>=0; j=e[j].delta_plus) { 
xx = (double)(v[e[j].rndd_minus].x - n.x); 
yy = (double)(v[e[j].rndd_minus].y - n.y); 
z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0; 
w += z*z*z*z; 
} 
for (int j = n.delta_minus; j>=0; j=e[j].delta_minus) { 
xx = (double)(v[e[j].rndd_plus].x - n.x); 
yy = (double)(v[e[j].rndd_plus].y - n.y); 
z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0; 
w += z*z*z*z; 
} 
return w; 
} 

void init_sub() { 
int x[] = {1, 0, -1, 1, 0, -1}; 
int y[] = {1, 1, 1, -1, -1, -1}; 
int i,j,k; 
double w,z; 

for (i=0; i<n; i++) { 
k=0; 
w=weight(v[i],(double)x[0],(double)y[0]); 
for (j=1; j<6; j++) { 
z=weight(v[i],(double)x[j],(double)y[j]); 
if (z<w) { 
w = z; 
k = j; 
} 
} 
v[i].dx = x[k]; 
v[i].dy = y[k]; 
} 
} 

public void init() { 
String mdname = getParameter("inputfile"); 
try { 
InputStream is; 

is = new URL(getDocumentBase(),mdname).openStream(); 
input_graph(is); 
try { 
if (is != null) 
is.close(); 
} catch(Exception e) { 
} 
} catch (FileNotFoundException e) { 
System.err.println("File not found."); 
} catch (IOException e) { 
System.err.println("Cannot access file."); 
} 

String s = getParameter("start"); 
if (s != null) 
snode = Integer.parseInt(s); 
else 
snode = 0; 

setBackground(Color.white); 
rdb(); 
init_sub(); 
addMouseListener(this); 
} 

public void paintNode(Graphics g, Node n, FontMetrics fm) { 
String s; 
int x = n.x; 
int y = n.y; 
int w = fm.stringWidth(n.name) + 10; 
int h = fm.getHeight() + 4; 
n.w = w; 
n.h = h; 

if (n.succ<-2) 
g.setColor(Color.blue); 
else if (n.succ==-2) 
g.setColor(Color.gray); 
else 
g.setColor(Color.red); 

g.drawRect(x-w/2,y-h/2,w,h); 

if (n.succ==-4) 
g.setColor(Color.cyan); 
else if (n.succ==-3) 
g.setColor(Color.pink); 
else if (n.succ>-2) 
g.setColor(Color.yellow); 
else 
g.setColor(getBackground()); 

g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1); 

g.setColor(Color.black); 
g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent()); 


if (n.dist<0) 
s = ""; 
else 
s = ""+n.dist; 
w = fm.stringWidth(s) + 10; 
x += (h+1)*n.dx; y += (h+1)*n.dy; 
g.setColor(getBackground()); 
g.fillRect(x-n.pw/2,y-h/2,n.pw,h); 
n.pw = w; 
if (n.succ<-2) 
g.setColor(Color.blue); 
else 
g.setColor(Color.red); 
g.drawString(s,x-(w-10)/2,y-(h-4)/2+fm.getAscent()); 
} 

int [] xy(int a, int b, int w, int h) { 
int x[] = new int[2]; 

if (Math.abs(w*b)>=Math.abs(h*a)) { 
x[0] = ((b>=0)?1:-1)*a*h/b/2; 
x[1] = ((b>=0)?1:-1)*h/2; 
} else { 
x[0] = ((a>=0)?1:-1)*w/2; 
x[1] = ((a>=0)?1:-1)*b*w/a/2; 
} 
return x; 
} 

void drawArrow(Graphics g,int x1,int y1,int x2,int y2) { 
int a = x1-x2; 
int b = y1-y2; 

if (isdigraph) { 
double aa = Math.sqrt(a*a+b*b)/16.0; 
double bb = b/aa; 
aa = a/aa; 
g.drawLine(x2,y2,x2+(int)((aa*12+bb*5)/13),y2+(int)((-aa*5+bb*12)/13)); 
g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),y2+(int)((aa*5+bb*12)/13)); 
} 
g.drawLine(x1,y1,x2,y2); 
} 

public void paintEdge(Graphics g, Edge e, FontMetrics fm) { 
Node v1 = v[e.rndd_plus]; 
Node v2 = v[e.rndd_minus]; 

int a = v1.x-v2.x; 
int b = v1.y-v2.y; 

int x1[] = xy(-a,-b,v1.w,v1.h); 
int x2[] = xy(a,b,v2.w,v2.h); 

if (v2.prev == e.rndd_plus) { 
if ((v1.succ<-2)&&(v2.succ>=-2)) 
g.setColor(Color.red); 
else 
g.setColor(Color.blue); 
} else { 
g.setColor(Color.lightGray); 
} 
if ((!isdigraph)&&(v1.prev == e.rndd_minus)) { 
if ((v2.succ<-2)&&(v1.succ>=-2)) 
g.setColor(Color.red); 
else 
g.setColor(Color.blue); 
} 
drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]); 

int w = fm.stringWidth("" + e.len); 
int h = fm.getHeight(); 

g.setColor(getBackground()); 
g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h); 

if ((v2.prev == e.rndd_plus)|| 
    ((!isdigraph)&&(v1.prev == e.rndd_minus))) 
g.setColor(Color.black); 
else 
g.setColor(Color.lightGray); 
g.drawString("" + e.len,(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent()); 
} 

public void paint(Graphics g) { 
FontMetrics fm = g.getFontMetrics(); 
for (int i=0; i<n; i++) 
paintNode(g,v[i],fm); 
for (int i=0; i<m; i++) 
paintEdge(g,e[i],fm); 
} 

public void update(Graphics g) { 
paint(g); 
} 

public void mousePressed(MouseEvent ev) { 
if (iteration==0) { 
step1(); 
iteration++; 
step = 2; 
} else if (iteration>=n) { 
step4(); 
iteration = 0; 
} else { 
if (step == 2) { 
step2(); 
step = 3; 
} else { 
step3(); 
iteration++; 
step = 2; 
} 
} 
repaint(); 
} 
public void mouseClicked(MouseEvent event) {} 
public void mouseReleased(MouseEvent event) {} 
public void mouseEntered(MouseEvent event) {} 
public void mouseExited(MouseEvent event) {} 
} 
对于该问题还有一些更好的算法，下面作一些简单的介绍：利用最短路径映射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)空间预处理障碍物的条件下达到。