Java中的A*(A star)寻径实现

布满荆棘的人生 2022-08-07 02:47 88阅读 0赞

据我个人所知，目前流行的寻径方法大体有两种，即A\* 和Dijkstra（SP算法）

Dijkstra算法：

![1.jpg][]  
     
    由Edsger Wybe Dijkstra先生发明（已故）  
    Dijkstra算法是典型的最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是一种逐步搜索算法，通过为每个顶点n保留目前为止所找到的从m到n的最短路径来工作的。

搜索过程：  
   假如在第m步搜索到一个最短路径，而该路径上有n个距离源节点最近的节点，则将他们认为是一个节点集合N；在第m+1步，搜索不属于N的距离源节点最近的节点，并搜索到的节点加入到N中；继续搜索，直至到达目的节点，N中的节点集合便是从源节点到目的节点的最短路径。

算法描述：

Dijkstra算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d\[s\]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d\[v\]= ∞）。当算法结束时，d\[v\]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d\[u\]+w(u,v)。如果这个值比目前已知的d\[v\]的值要小，我们可以用新值来替代当前d\[v\]中的值。拓展边的操作一直执行到所有的d\[v\]都代表从s到v最短路径的花费。这个算法经过组织因而当d\[u\]达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集S和Q。集合S保留了我们已知的所有d\[v\]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S 初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d\[u\]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。

A\*（A Star）算法：

![2.jpg][]

A\*（A-Star)算法是一种静态路网中求解最短路最有效的方法。  
    公式表示为：f(n)=g(n)+h(n), 其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

搜索过程：  
      
     创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值.

While(OPEN!=NULL)  
        \{  
        从OPEN表中取估价值f最小的节点n;  
        if(n节点==目标节点) break;  
        else  
        \{  
        if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值  
        if( X的估价值小于OPEN表的估价值 )  
        　　　更新OPEN表中的估价值; //取最小路径的估价值  
        if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值  
        if( X的估价值小于CLOSE表的估价值 )  
        　　　更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值  
        if(X not in both)  
        求X的估价值;  
        　　　并将X插入OPEN表中;　//还没有排序  
        \}  
        将n节点插入CLOSE表中;  
        按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。  
        \}

就实际应用而言，A\*算法和Dijistra算法的最大区别就在于有无估价值，本质上Dijistra算法相当于A\*算法中估价值为0的情况。所以此次我选取A\*算法进行Java实现。

抛开理论性的数学概念，通常的A\*算法，其实只有两个步骤，一是路径评估，以保证移动的下一个位置离目标最近，评估的结果越精确则寻径的效率也将越高。二是路径查询，也即将评估结果进行反应，而后从新位置再次进行评估指导无路可走为止，以此遍历出可行的路径。

在A\*算法的程序实现中，本质上我们只需要关心三点，即起点、终点和地图信息，有了这三项基本数据，我们就可以构建任何情况下的A\*实现。

下面我现在提供的是一个A\*的Java静态寻径算法实现，逻辑见代码注释。

运行效果如下图(1,1 to 10,13)：

![3.jpg][]  
(1,1 to 7,9 小房子门口中间)

![4.jpg][]  
(1,1 to 6,7 小房子内部)

![5.jpg][]

Node.java  
package org.test.astar;

import java.awt.Point;  
import java.util.LinkedList;

/\*\* \*//\*\* 
 \* 
 \* Title: LoonFramework 
 \* 
 \* 
 \* Description:描述路径节点用类 
 \* 
 \* 
 \* Copyright: Copyright (c) 2008 
 \* 
 \* 
 \* Company: LoonFramework 
 \* 
 \* 
 \* License: [http://www.apache.org/licenses/LICENSE-2.0][http_www.apache.org_licenses_LICENSE-2.0] 
 \* 
 \* 
 \* @author chenpeng 
 \* @email：[ceponline@yahoo.com.cn][ceponline_yahoo.com.cn] 
 \* @version 0.1 
 \*/ 
public class Node implements Comparable ...\{ 
    // 坐标 
    public Point \_pos;

// 开始地点数值  
    public int \_costFromStart;

// 目标地点数值  
    public int \_costToObject;

// 父节点  
    public Node \_parentNode;

private Node() ...\{  
    \}

/\*\* \*//\*\*  
     \* 以注入坐标点方式初始化Node  
     \*  
     \* @param \_pos  
     \*/  
    public Node(Point \_pos) ...\{  
        this.\_pos = \_pos;  
    \}

/\*\* \*//\*\*  
     \* 返回路径成本  
     \*  
     \* @param node  
     \* @return  
     \*/  
    public int getCost(Node node) ...\{  
        // 获得坐标点间差值 公式：(x1, y1)-(x2, y2)  
        int m = node.\_pos.x - \_pos.x;  
        int n = node.\_pos.y - \_pos.y;  
        // 取两节点间欧几理德距离（直线距离）做为估价值，用以获得成本  
        return (int) Math.sqrt(m \* m + n \* n);  
    \}

/\*\* \*//\*\*  
     \* 检查node对象是否和验证对象一致  
     \*/  
    public boolean equals(Object node) ...\{  
        // 验证坐标为判断依据  
        if (\_pos.x == ((Node) node).\_pos.x && \_pos.y == ((Node) node).\_pos.y) ...\{  
            return true;  
        \}  
        return false;  
    \}

/\*\* \*//\*\* 
     \* 比较两点以获得最小成本对象 
     \*/ 
    public int compareTo(Object node) ...\{ 
        int a1 = \_costFromStart + \_costToObject; 
        int a2 = ((Node) node).\_costFromStart + ((Node) node).\_costToObject; 
        if (a1 < a2) ...\{ 
            return -1; 
        \} else if (a1 == a2) ...\{ 
            return 0; 
        \} else ...\{ 
            return 1; 
        \} 
    \}

/\*\* \*//\*\*  
     \* 获得上下左右各点间移动限制区域  
     \*  
     \* @return  
     \*/  
    public LinkedList getLimit() ...\{  
        LinkedList limit = new LinkedList();  
        int x = \_pos.x;  
        int y = \_pos.y;  
        // 上下左右各点间移动区域(对于斜视地图，可以开启注释的偏移部分，此时将评估8个方位)  
        // 上  
        limit.add(new Node(new Point(x, y - 1)));  
        // 右上  
        // limit.add(new Node(new Point(x+1, y-1)));  
        // 右  
        limit.add(new Node(new Point(x + 1, y)));  
        // 右下  
        // limit.add(new Node(new Point(x+1, y+1)));  
        // 下  
        limit.add(new Node(new Point(x, y + 1)));  
        // 左下  
        // limit.add(new Node(new Point(x-1, y+1)));  
        // 左  
        limit.add(new Node(new Point(x - 1, y)));  
        // 左上  
        // limit.add(new Node(new Point(x-1, y-1)));

return limit;  
    \}

PathFinder.java  
package org.test.astar;

import java.awt.Point;  
import java.util.LinkedList;  
import java.util.List;

/\*\* \*//\*\* 
 \* 
 \* Title: LoonFramework 
 \* 
 \* 
 \* Description:A\*寻径处理用类(此类为演示用，并不意味着算法是最佳实现) 
 \* 
 \* 
 \* Copyright: Copyright (c) 2008 
 \* 
 \* 
 \* Company: LoonFramework 
 \* 
 \* 
 \* License: [http://www.apache.org/licenses/LICENSE-2.0][http_www.apache.org_licenses_LICENSE-2.0] 
 \* 
 \* 
 \* @author chenpeng 
 \* @email：[ceponline@yahoo.com.cn][ceponline_yahoo.com.cn] 
 \* @version 0.1 
 \*/ 
public class PathFinder ...\{ 
    // 路径优先等级list(此示例中为内部方法) 
    private LevelList \_levelList;

// 已完成路径的list  
    private LinkedList \_closedList;

// 地图描述  
    private int\[\]\[\] \_map;

// 行走区域限制  
    private int\[\] \_limit;

/\*\* \*//\*\*  
     \* 以注入地图的2维数组及限制点描述初始化此类  
     \*  
     \* @param \_map  
     \*/  
    public PathFinder(int\[\]\[\] map, int\[\] limit) ...\{  
        \_map = map;  
        \_limit = limit;  
        \_levelList = new LevelList();  
        \_closedList = new LinkedList();  
    \}

/\*\* \*//\*\* 
     \* A\*方式寻径,注入开始坐标及目标坐标后运算,返回可行路径的List 
     \* 
     \* @param startPos 
     \* @param objectPos 
     \* @return 
     \*/ 
    public List searchPath(Point startPos, Point objectPos) ...\{ 
        // 初始化起始节点与目标节点 
        Node startNode = new Node(startPos); 
        Node objectNode = new Node(objectPos); 
        // 设定起始节点参数 
        startNode.\_costFromStart = 0; 
        startNode.\_costToObject = startNode.getCost(objectNode); 
        startNode.\_parentNode = null; 
        // 加入运算等级序列 
        \_levelList.add(startNode); 
        // 当运算等级序列中存在数据时，循环处理寻径，直到levelList为空 
        while (!\_levelList.isEmpty()) ...\{ 
            // 取出并删除最初的元素 
            Node firstNode = (Node) \_levelList.removeFirst(); 
            // 判定是否和目标node坐标相等 
            if (firstNode.equals(objectNode)) ...\{ 
                // 是的话即可构建出整个行走路线图，运算完毕 
                return makePath(firstNode); 
            \} else ...\{ 
                // 否则 
                // 加入已验证List 
                \_closedList.add(firstNode); 
                // 获得firstNode的移动区域 
                LinkedList \_limit = firstNode.getLimit(); 
                // 遍历 
                for (int i = 0; i < \_limit.size(); i++) ...\{ 
                    //获得相邻节点 
                    Node neighborNode = (Node) \_limit.get(i); 
                    //获得是否满足等级条件 
                    boolean isOpen = \_levelList.contains(neighborNode); 
                    //获得是否已行走 
                    boolean isClosed = \_closedList.contains(neighborNode); 
                    //判断是否无法通行 
                    boolean isHit = isHit(neighborNode.\_pos.x, 
                            neighborNode.\_pos.y); 
                    //当三则判定皆非时 
                    if (!isOpen && !isClosed && !isHit) ...\{ 
                        //设定costFromStart 
                        neighborNode.\_costFromStart = firstNode.\_costFromStart + 1; 
                        //设定costToObject  
                        neighborNode.\_costToObject = neighborNode 
                                .getCost(objectNode); 
                        //改变neighborNode父节点 
                        neighborNode.\_parentNode = firstNode; 
                        //加入level 
                        \_levelList.add(neighborNode); 
                    \} 
                \} 
            \}

\} 
        //清空数据 
        \_levelList.clear(); 
        \_closedList.clear(); 
        //当while无法运行时，将返回null 
        return  null; 
    \} 
    
    /\*\* \*//\*\* 
     \* 判定是否为可通行区域 
     \* 
     \* @param x 
     \* @param y 
     \* @return 
     \*/ 
    private boolean isHit(int x, int y) ...\{ 
        for (int i = 0; i < \_limit.length; i++) ...\{ 
            if (\_map\[y\]\[x\] == \_limit\[i\]) ...\{ 
                return true; 
            \} 
        \} 
        return false; 
    \}

/\*\* \*//\*\*  
     \* 通过Node制造行走路径  
     \*  
     \* @param node  
     \* @return  
     \*/  
    private LinkedList makePath(Node node) ...\{  
        LinkedList path = new LinkedList();  
        // 当上级节点存在时  
        while (node.\_parentNode != null) ...\{  
            // 在第一个元素处添加  
            path.addFirst(node);  
            // 将node赋值为parent node  
            node = node.\_parentNode;  
        \}  
        // 在第一个元素处添加  
        path.addFirst(node);  
        return path;  
    \}

private class LevelList extends LinkedList ...\{  
        /\*\* \*//\*\*  
         \*  
         \*/  
        private static final long serialVersionUID = 1L;

/\*\* \*//\*\* 
         \* 增加一个node 
         \* 
         \* @param node 
         \*/ 
        public void add(Node node) ...\{ 
            for (int i = 0; i < size(); i++) ...\{ 
                if (node.compareTo(get(i)) <= 0) ...\{ 
                    add(i, node); 
                    return; 
                \} 
            \} 
            addLast(node); 
        \} 
    \} 
\}

TestMap.java  
package org.test.astar;

import java.awt.Graphics;  
import java.awt.Image;  
import org.loon.framework.game.image.Bitmap;

/\*\* \*//\*\* 
 \* 
 \* Title: LoonFramework 
 \* 
 \* 
 \* Description:一个简单的地图实现 
 \* 
 \* 
 \* Copyright: Copyright (c) 2008 
 \* 
 \* 
 \* Company: LoonFramework 
 \* 
 \* 
 \* License: [http://www.apache.org/licenses/LICENSE-2.0][http_www.apache.org_licenses_LICENSE-2.0] 
 \* 
 \* 
 \* @author chenpeng 
 \* @email：[ceponline@yahoo.com.cn][ceponline_yahoo.com.cn] 
 \* @version 0.1 
 \*/ 
public class TestMap ...\{

final static private int CS = 32;

// 地图描述  
    final static public int\[\]\[\] MAP = ...\{  
            ...\{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 \},  
            ...\{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 \} \};

// 无法移动区域  
    final static public int\[\] HIT = ...\{ 1 \};

// 设定背景方格默认行数  
    final static private int ROW = 15;

// 设定背景方格默认列数  
    final static private int COL = 15;

private Image floorImage;

private Image wallImage;

public TestMap() ...\{  
        floorImage = new Bitmap("./astart/floor.gif").getImage();  
        wallImage = new Bitmap("./astart/wall.gif").getImage();  
    \}

public void draw(Graphics g) ...\{ 
        for (int i = 0; i < ROW; i++) ...\{ 
            for (int j = 0; j < COL; j++) ...\{ 
                switch (MAP\[i\]\[j\]) ...\{ 
                case 0: 
                    g.drawImage(floorImage, j \* CS, i \* CS, null); 
                    break; 
                case 1: 
                    g.drawImage(wallImage, j \* CS, i \* CS, null); 
                    break; 
                \} 
            \} 
        \} 
    \}

Main.java  
package org.test.astar;

import java.awt.Color;  
import java.awt.Frame;  
import java.awt.Graphics;  
import java.awt.Image;  
import java.awt.Panel;  
import java.awt.Point;  
import java.awt.event.WindowAdapter;  
import java.awt.event.WindowEvent;  
import java.util.List;

import org.loon.framework.game.image.Bitmap;

/\*\* \*//\*\* 
 \* 
 \* Title: LoonFramework 
 \* 
 \* 
 \* Description:Java的A\*寻径实现 
 \* 
 \* 
 \* Copyright: Copyright (c) 2008 
 \* 
 \* 
 \* Company: LoonFramework 
 \* 
 \* 
 \* License: [http://www.apache.org/licenses/LICENSE-2.0][http_www.apache.org_licenses_LICENSE-2.0] 
 \* 
 \* 
 \* @author chenpeng 
 \* @email：[ceponline@yahoo.com.cn][ceponline_yahoo.com.cn] 
 \* @version 0.1 
 \*/ 
public class Main extends Panel ...\{

/\*\* \*//\*\*  
     \*  
     \*/  
    final static  private  long serialVersionUID = 1L;

final static  private  int WIDTH = 480;

final static  private  int HEIGHT = 480;

final static  private  int CS = 32;

private TestMap map;

private PathFinder astar;

// 起始坐标1,1  
    private static Point START\_POS = new Point(1, 1);

// 目的坐标10,13  
    private static Point OBJECT\_POS = new Point(10, 13);

private Image screen;

private Graphics graphics;

private List path;

public Main() ...\{

setSize(WIDTH, HEIGHT);  
        setFocusable(true);  
        screen = new Bitmap(WIDTH, HEIGHT).getImage();  
        graphics = screen.getGraphics();  
        map = new TestMap();  
        // 注入地图描述及障碍物描述  
        astar = new PathFinder(TestMap.MAP, TestMap.HIT);  
        // searchPath将获得两点间移动路径坐标的List集合  
        // 在实际应用中，利用Thread分步处理List中坐标即可实现自动行走  
        path = astar.searchPath(START\_POS, OBJECT\_POS);  
    \}

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

public void paint(Graphics g) ...\{  
        // 绘制地图  
        map.draw(graphics);  
        graphics.setColor(Color.RED);  
        graphics.fillRect(START\_POS.x \* CS, START\_POS.y \* CS, CS, CS);

graphics.setColor(Color.BLUE);  
        graphics.fillRect(OBJECT\_POS.x \* CS, OBJECT\_POS.y \* CS, CS, CS);

// 绘制路径 
        if (path != null) ...\{ 
            graphics.setColor(Color.YELLOW); 
            //遍历坐标，并一一描绘 
            for (int i = 0; i < path.size(); i++) ...\{ 
                Node node = (Node) path.get(i); 
                Point pos = node.\_pos; 
                // 描绘边框 
                graphics.fillRect(pos.x \* CS + 7, pos.y \* CS + 7, CS - 14, 
                        CS - 14); 
            \} 
        \} 
        g.drawImage(screen, 0, 0, this); 
    \}

public static void main(String\[\] args) ...\{  
        Frame frame = new Frame();  
        frame.setTitle("Java的A\*寻径实现");  
        frame.setSize(WIDTH, HEIGHT + 20);  
        frame.setResizable(false);  
        frame.setLocationRelativeTo(null);  
        frame.add(new Main());  
        frame.setVisible(true);  
        frame.addWindowListener(new WindowAdapter() ...\{  
            public void windowClosing(WindowEvent e) ...\{  
                System.exit(0);  
            \}  
        \});  
    \}  
\}

本文来自CSDN博客，转载请标明出处：[http://blog.csdn.net/cping1982/archive/2008/03/04/2146743.aspx][http_blog.csdn.net_cping1982_archive_2008_03_04_2146743.aspx]

==============================================================

epinszteinic 发表于2008年3月10日 15:15:51  IP:10.100.127.\*举报  
1.走不到中间小房子的门口中间  
2.穿墙走进房子内部cping1982 发表于2008年3月10日 15:35:40  IP:举报  
epinszteinic先生你好，我刚才按您说的又测试了一下，测试效果图已加载入文章中，暂未发现您所说的现象。能否把您的用例代码公布一下，或者把错误状态图传到[ceponline@yahoo.com.cn][ceponline_yahoo.com.cn]这个邮箱中？epinszteinic 发表于2008年3月10日 15:36:27  IP:10.100.127.\*举报  
找到原因了！！  
PathFinder.java的isHit（）方法的第二行：  
\_map\[y\]\[x\] ---> \_map\[x\]\[y\]  
x和y搞反了epinszteinic 发表于2008年3月10日 15:37:48  IP:10.100.127.\*举报  
你贴出来的代码里面反了epinszteinic 发表于2008年3月10日 15:43:43  IP:10.100.127.\*举报  
谢谢你的代码:)  
一直没机会接触这个tangjie\_0 发表于2008年11月29日 14:57:27  IP:举报  
epinszteinic 说错了，上面代码是正确的xiaokan 发表于2008年12月8日 23:05:11  IP:举报  
很高兴遇见这么一位java高手，我对算法还行，我可以告诉你一种比这个更简单且快的算法，请联系我，qq 191971525zjb\_dill 发表于2009年3月4日 5:49:35  IP:举报  
为什么反着写是是正确的??  
\_map\[y\]\[x\] ?  
如果邻近节点在openlist中重复了，是不是应该要比较一个g值？如果新g值比openlist中节点要少，应该要更新一下g值/f值和父节点zjb\_dill 发表于2009年3月4日 5:55:38  IP:举报  
我很喜欢java，现在学做java游戏，博主的游戏教程，真是受益匪浅，希望能加好友得到你的指导dadaodc 发表于2009年5月23日 19:46:58  IP:举报  
想知道为什么都用LinkedList 只是看到再add 没有频繁的删除插入 Arraylist 感觉要比LinkedList 快好多啊。难道是因为这算法不是频繁使用所以不用计较这些效率问题？麻烦给指点一下好不？要是搞一个大型网游的后台，要频繁运算路径效率还是很关键的啊dadaodc 发表于2009年5月23日 19:59:38  IP:举报  
晕倒刚才没看完就说了。看到了有删除。只是没测试只是同一个方向插入，同一个方向删除，没有从中间插入删除，哪个效率高。

[1.jpg]: /images/20220805/786f776460814c4caed44c4c32bee150.png
[2.jpg]: /images/20220805/dec2ac47e66c48aea0ba413284f889cd.png
[3.jpg]: /images/20220805/0fa1aa3732334e3cb6b13d52791541cb.png
[4.jpg]: /images/20220805/18877f1523144aebb181ee50b1d7588f.png
[5.jpg]: /images/20220805/e3d56e3d26ce46afbffb953da803cce1.png
[http_www.apache.org_licenses_LICENSE-2.0]: http://www.apache.org/licenses/LICENSE-2.0
[ceponline_yahoo.com.cn]: mailto:ceponline@yahoo.com.cn
[http_blog.csdn.net_cping1982_archive_2008_03_04_2146743.aspx]: http://blog.csdn.net/cping1982/archive/2008/03/04/2146743.aspx