精华内容
下载资源
问答
  • 与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索...下面是一个非常简单的宽度优先搜索例子,核心是用队列去存储节点。 代码如下:package sort;//第一步,定义一个GraphNode class GraphNode{ int val; Grap

    与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索。深度优先搜索非常简单,你可以从根节点开始循环整个邻居节点。下面是一个非常简单的宽度优先搜索例子,核心是用队列去存储节点。

                                     这里写图片描述

    代码如下:

    package sort;
    
    //第一步,定义一个GraphNode
    class GraphNode{
        int val;
        GraphNode next;
        GraphNode[] neighbors;
        boolean visited;
    
        GraphNode(int x){
            val = x;
        }
    
        GraphNode(int x,GraphNode[] n){
            val = x;
            neighbors = n;
        }
    
        public String toString(){
            return "value:"+this.val;
        }
    }
    
    //第二步,定义一个队列
    class Queue{
        GraphNode first,last;
        public void enqueue(GraphNode n){
            if(first == null){
                first = n;
                last = first;
            }else{
                last.next = n;
                last = n;
            }
        }
    
        public GraphNode dequeue(){
            if(first == null){
                return null;
            }else{
                GraphNode temp = new GraphNode(first.val,first.neighbors);
                first = first.next;
                return temp;
            }
        }
    }
    //第三步,使用队列进行宽度优先搜索 
    public class GraphTest {
        public static void main(String[] args) {
            GraphNode n1 = new GraphNode(1);
            GraphNode n2 = new GraphNode(2);
            GraphNode n3 = new GraphNode(3);
            GraphNode n4 = new GraphNode(4);
            GraphNode n5 = new GraphNode(5);
    
            n1.neighbors = new GraphNode[]{n2,n3,n5};
            n2.neighbors = new GraphNode[]{n1,n4};
            n3.neighbors = new GraphNode[]{n1,n4,n5};
            n4.neighbors = new GraphNode[]{n2,n3,n5};
            n5.neighbors = new GraphNode[]{n1,n3,n4};
    
            breathFirstSearch(n1,5);
        }
    
        public static void breathFirstSearch(GraphNode root,int x){
            if(root.val == x){
                System.out.println("find in root");
            }
    
            Queue queue = new Queue();
            root.visited = true;
            queue.enqueue(root);
    
            while(queue.first!=null){
                GraphNode c = (GraphNode)queue.dequeue();
                for(GraphNode n:c.neighbors){
                    if(!n.visited){
                        System.out.println(n+" ");
                        n.visited = true;
                        if(n.val==x){
                            System.out.println("Find "+n);
                        }
                        queue.enqueue(n);
                    }
                }
            }
        }
    
    
    }
    
    展开全文
  • 【作者简介】 冒绿光盒子,公众号投稿作者...走迷宫显示迷宫迷宫生成等等再提,先看一下迷宫读取和显示。第一行是行数和列数,代表有101行101列,这个迷宫后面可以使用最小生成树生成。读进一个迷宫:publicclas...

    点击上方“简说Python”,选择“置顶/星标公众号”

    福利干货,第一时间送达!

    d559af3071bc3f5cedd1649a1681f3af.gif

    【作者简介】

      冒绿光的盒子,公众号投稿作者,个人简书主页:https://www.jianshu.com/u/cbacf40d927f。

    走迷宫

    显示迷宫

    迷宫生成等等再提,先看一下迷宫的读取和显示。

    469e41efd3eccc95743a3d93a44adee8.png

    第一行是行数和列数,代表有101行101列,这个迷宫后面可以使用最小生成树生成。读进一个迷宫:

    public class MazeData {private char[][] maze;private int N, M;public static final char ROAD = '#';public static final char WALL = ' ';public MazeData(String fileName) {if (fileName == null) {throw new IllegalArgumentException("filename can't be null!");
            }
            Scanner scanner = null;try {
                File file = new File(fileName);if (!file.exists()) {throw new IllegalArgumentException("File is not exist!");
                }
                FileInputStream fileInputStream = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fileInputStream), "UTF-8");
                String nm = scanner.nextLine();
                String[] nmC = nm.trim().split("\\s+");
                N = Integer.parseInt(nmC[0]);
                M = Integer.parseInt(nmC[1]);
                maze = new char[N][M];for (int i = 0; i                 String line = scanner.nextLine();if (line.length() != M) {throw new IllegalArgumentException("Message of file is not completed!");
                    }for (int j = 0; j                     maze[i][j] = line.charAt(j);
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            } finally {if (scanner != null) {
                    scanner.close();
                }
            }
        }public char getMaze(int i, int j) {if (!inArea(i, j)) {throw new IllegalArgumentException("out of range!");
            }return maze[i][j];
        }public boolean inArea(int x, int y) {return x >= 0 && x = 0 && y     }public int N() {return N;
        }public int M() {return M;
        }
    }

    使用File来获得当前文件,如果没有就要抛出异常。scanner获得输入流之后可以通过读取下一行获得每一行的内容,列数在前面已经提到了,所以要检查每一行是不是M列,不是就没得读了。#就是墙,空格是路,可以设置两个静态变量表示。同时还需要各种辅助函数,比如是否是在整区域里面的,返回当前区域的值等等。然后就是显示函数了:

                int w = canvasWidth / data.M();
                int h = canvasHeight / data.N();for (int i = 0; i data
    .N(); i++) {for (int j = 0; j data.M(); j++) {if (data.getMaze(i, j) == MazeData.ROAD){
                            AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
                        }else {
                            AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.White);
                        }
                        AlgorithmHelper.fillRectangle(graphics2D, j * w, i * h, w, h);
                    }
                }

    墙的宽度自适应,这样整个屏幕刚刚够。#号画浅蓝色,其余的白色。之后就是再控制器里面调用repaint即可。

    6a46b0088f18cd3ab9c512d9544e1f3e.png

    迷宫问题

    白色方块是可以走的路径,红色的就是墙。迷宫的本质就是一个图结构。可以把整个迷宫当成是一个图,而走迷宫的过程就可以等价成是图的遍历。从起始点开始遍历,直到遍历到了某一个终止点即可。如果遍历了所有点都没有得到结果,那么就可以确认无解了。
    图的遍历可以分成两种遍历。深度优先遍历和广度优先遍历,一种遍历是按照深度,先往一个方向深了走,没有路了再回头,而广度是先广度走一遍再一层一层下去。首先固定了每一个迷宫的出口和入口位置,从一开始,就需要从相邻的四个方向走迷宫,如果可以就继续,不能就回头,其实就是递归实现。

    深度优先

    首先还是递归实现,递归比较方便,首先要准备递归函数,和上述的一样,走四个方向,一个一个尝试,如果下一个格子是在这个图里面,是一条路,而且还没有被访问过,那么久可以继续走,否则就需要返回。

        private boolean go(int x, int y) {if (!data.inArea(x, y)) {throw new IllegalArgumentException("Paramenter is illgel!");
            }data.visited[x][y] = true;
            setData(x, y, true);if (x == data.getExitX() && y == data.getExitY()) {return true;
            } else {for (int i = 0; i 4
    ; i++) {
                    int nexX = x + direction[i][0];
                    int nexY = y + direction[i][1];if (data.inArea(nexX, nexY) &&data.getMaze(nexX, nexY) == MazeData.ROAD &&
                            !data.visited[nexX][nexY]) {if (go(nexX, nexY)) {return true;
                        }
                    }
                }
                setData(x, y, false);return false;
            }
        }

    如果四个点都尝试过了,都是走不了的,那么还需要消除画的格子。相对来说还是比较简单的。再消除格子上这个步骤对于递归来说是相对方便,因为再回溯的过程中是有保留之前的点的信息的,所以相对简单。

    d1137b25d33dfa120a48e48a75403275.png

    这就是生成的结果了。
    如果是非递归,用栈就可以模拟,因为递归本身就是用栈实现的。对于删除无用路径的情况,其实有点难,因为无用的路径是直接丢弃的,先前的递归可以是因为递归的栈保留了更加多的内容,而这里只是保留了点而已。

        private boolean go_iteration() {
            Stack stack = new Stack<>();
            Position entrance = new Position(data.getEntanceX(), data.getEntanceY());stack.push(entrance);
            data.visited[entrance.getX()][entrance.getY()] = true;while (!stack.isEmpty()) {
                Position position = stack.pop();
                setData(position.getX(), position.getY(), true);for (int i = 0; i 4
    ; i++) {int newX = position.getX() + direction[i][0];int newY = position.getY() + direction[i][1];if (newX == data.getExitX() && newY == data.getExitY()) {
                        setData(newX, newY, true);return true;
                    }
                    Position newPosition = new Position(newX, newY, position);if (data.inArea(newPosition.getX(), newPosition.getY()) &&
                            data.getMaze(newPosition.getX(), newPosition.getY()) == MazeData.ROAD
                            && !data.visited[newPosition.getX()][newPosition.getY()]) {stack.push(newPosition);
                        data.visited[newPosition.getX()][newPosition.getY()] = true;
                    }
                }
            }return false;
        }

    883775adaf1d759a3ed82655fedc737b.png

    广度优先

    广度和深度在搜索策略上是不同的。深度是走到死路才回头,广度是对于每一次都是齐头并进。和遍历的深度优先的区别就是在于他们的数据结构不一样,一个是队列,一个是栈,其他的基本差不多。

        private boolean go_level() {
            Queue queue = new LinkedList<>();
            Position position = new Position(data.getEntanceX(), data.getEntanceY());queue.add(position);
            data.visited[position.getX()][position.getY()] = true;while (!queue.isEmpty()) {
                Position position1 = queue.poll();
                setData(position1.getX(), position1.getY(), true);for (int i = 0; i 4
    ; i++) {int newX = position1.getX() + direction[i][0];int newY = position1.getY() + direction[i][1];if (newX == data.getExitX() && newY == data.getExitY()) {
                        findPath(position1);
                        setData(newX, newY, true);return true;
                    }
                    Position newPosition = new Position(newX, newY, position1);if (data.inArea(newPosition.getX(), newPosition.getY()) &&
                            data.getMaze(newPosition.getX(), newPosition.getY()) == MazeData.ROAD
                            && !data.visited[newPosition.getX()][newPosition.getY()]) {queue.add(newPosition);
                        data.visited[newPosition.getX()][newPosition.getY()] = true;
                    }
                }
            }return false;
        }

    9496e06268926ef27751c63fd00eb2af.png

    如果迷宫有很多个解,深度优先遍历那么久只会搜索到第一个碰到的解,搜索到的解那么就是一个随缘排序出来,广度优先就是会查找最短的路径。广度优先可以找到无全图的最短路径。深度和广度的非递归差不多,只是使用的数据结构不同而已。

    生成迷宫

    刚刚是走迷宫,刚刚生成的那个用例其实就是生成的迷宫。对于一个迷宫,只有一个入口一个出口,为了简单化,入口就是第二行的第一个口,出口是倒数第二行的第一个口。而且只有一个解,并且路径是连续的,有些游戏里面的迷宫是有传送点的,改变起来也很简单。
    首先迷宫其实就是一棵树,每一个点都会有分支,任何一个叶子或者是节点都可以作为是一个入口,生成一个迷宫其实就是一个生成树的过程。之前在数据结构有提到过一个最小生成树,但是由于是一个随机的迷宫,所以应该是随机生成树。无论是什么树,都是基于树的。而图的遍历结果就是一颗树,每一个节点只是访问一次,且没有环,深度优先遍历的结果是一颗深度优先树,广度优先的结果是广度优先树。可以先把一张画布分成很多很多小格子,然后每隔一个格子就挖空一个点,没有挖空点的都是墙,用一种遍历方法来遍历这些点所生成的树就是一个迷宫了。但是这样的迷宫其实带有偏见的,随机性不高,所以可以在选择点的进行遍历的时候进行随机选择。
    @@@@@
      @
    @@@@@
    @  _ @    _@
    @@@@@
    可以看的出无论怎么看,行和列一定要是基数,限制还是蛮多的。深度优先生成迷宫其实和之前的差不多,没有上面打的差别。首先是要得到一个格子布。然后通过深度遍历把格子全部连接起来。递归实现:

        private void run() {
            setData(-1-1);
            go(data.getEntranceX(), data.getEntranceY() + 1);
            setData(-1-1);
        }private void go(int x, int y) {if (!data.inArea(x, y)) {throw new IllegalArgumentException("x or y is illegal!");
            }
            data.visited[x][y] = true;for (int i = 0; i 4
    ; i++) {int newX = x + direction[i][0] * 2;int newY = y + direction[i][1] * 2;if (data.inArea(newX, newY) &&
                        !data.visited[newX][newY]) {
                    setData(x + direction[i][0], y + direction[i][1]);
                    go(newX, newY);
                }
            }
        }

    这里要注意每两个格子之间的差距是2,因为中间都隔着一堵墙。go的参数是开始的参数,开始不能直接从入口开始,因为入口是我们新加的,不符合迷宫节点的规矩,比如每一个格子相差两个点,但是出口和第一个点差一个而已。

                int newX = x + direction[i][0] * 2;
                int newY = y + direction[i][1] * 2;

    乘上2的原因就是因为两个格子之间相差了2。而渲染都放在了setData里面处理。渲染的点就不是我们newX和newY了,因为那两个点本来就是road,渲染的应该是两个点之间的墙,所以是加1的。和前面深度搜索对比区别就是,这里没有终止点,不是到了exit就退出,事实上是不一定有解的。因为我们这里是要全部生成而不是生成到了终点就停止,所以是无终止条件的。但是for循环里面是隐含了的。还有一个就是条件确认是不是一条路,这个决策是不必要的,因为就要生成路的。但是这样导致的迷宫很无随机性:

    6d8ed291b79eb7f5f37a38a906dc1038.png

    因为方向都是一样的,从左上右下这样。
    这是递归方法,非递归方法

        private void go_iterator(){
            Stack stack = new Stack<>();
            Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);stack.push(firstPosition);
            data.visited[firstPosition.getX()][firstPosition.getY()] = true;while (!stack.isEmpty()){
                Position position = stack.pop();for (int i = 0; i 4
    ; i++) {int newX = position.getX() + direction[i][0] * 2;int newY = position.getY() + direction[i][1] * 2;if (data.inArea(newX, newY) &&
                            !data.visited[newX][newY]) {
                        setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);stack.push(new Position(newX, newY));
                        data.visited[newX][newY] = true;
                    }
                }
            }
        }

    677f3e7be04059a20bba8188a9580bce.png

    不一样的原因就是因为在加入栈的时候就已经上下左右看了,看看能不能走,走就直接把墙消去了,所以会出现锯齿型。至于大体的trend的不一样的因为两个方向是相反的。广度遍历:之前提到过了和深度遍历差不多:

        private void go_level(){
            LinkedList stack = new LinkedList<>();
            Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);stack.addLast(firstPosition);
            data.visited[firstPosition.getX()][firstPosition.getY()] = true;while (stack.size() != 0){
                Position position = stack.removeFirst();for (int i = 0; i 4
    ; i++) {int newX = position.getX() + direction[i][0] * 2;int newY = position.getY() + direction[i][1] * 2;if (data.inArea(newX, newY) &&
                            !data.visited[newX][newY]) {
                        setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);stack.addLast(new Position(newX, newY));
                        data.visited[newX][newY] = true;
                    }
                }
            }
        }

    974ccf13d49520a6afff58188ed8bd01.png

    生成的图像都很规则。 一个很重要的原因的因为我们在数据结构的选择过程中都是栈和队列,可预期性太强了。我们只需要在数据结构中加上随机性就好了。出队或者是删除都是随机队列。

    public class RandomQueue {private ArrayList queue;public RandomQueue() {queue = new ArrayList<>();
        }public void add(E e) {queue.add(e);
        }public E remove() {if (queue.size() == 0) {throw new IllegalArgumentException("no elements!");
            }int randomIndex = (int) (Math.random() * queue.size());
            E Ele = queue.get(randomIndex);queue.set(randomIndex, queue.get(queue.size() - 1));queue.remove(queue.size() - 1);return Ele;
        }public boolean isEmpty(){return queue.isEmpty();
        }
    }

    在广度优先里面把队列改一下:

    514c2c2a54efe5f3f2d2f4078a25deae.png

    这样就有一定的随机性了。可以看到在很多空白的小格子很容易让别人猜到我们是怎么生成的。所以可以加上如果没有遍历到的格子全部变黑色。

        private void go_level(){
            RandomQueue stack = new RandomQueue<>();
            Position firstPosition = new Position(data.getEntranceX(), data.getEntranceY() + 1);stack.add(firstPosition);
            data.openMinst(firstPosition.getX(), firstPosition.getY());
            data.visited[firstPosition.getX()][firstPosition.getY()] = true;while (!stack.isEmpty()){
                Position position = stack.remove();for (int i = 0; i 4
    ; i++) {int newX = position.getX() + direction[i][0] * 2;int newY = position.getY() + direction[i][1] * 2;if (data.inArea(newX, newY) &&
                            !data.visited[newX][newY]) {
                        data.openMinst(newX, newY);
                        setData(position.getX() + direction[i][0], position.getY() + direction[i][1]);stack.add(new Position(newX, newY));
                        data.visited[newX][newY] = true;
                    }
                }
            }
        }

    9f96727016ab72ddc6d9049cbb759749.png

    但是其实还有一个问题,很多时候这个迷宫的路径顺序是都是斜向下的趋势,所以有时候是可以猜到怎么走的。可以通过改进随机队列:

        public void add(E e) {if (Math.random() 0.5){queue.addFirst(e);
            }else {queue.addLast(e);
            }
        }public E remove() {if (queue.size() == 0) {throw new IllegalArgumentException("no elements!");
            }//        int randomIndex = (int) (Math.random() * queue.size());//        E Ele = queue.get(randomIndex);//        queue.set(randomIndex, queue.get(queue.size() - 1));//        queue.remove(queue.size() - 1);//        return Ele;if (Math.random() 0.5){return queue.removeFirst();
            }else {return queue.removeLast();
            }
        }

    这个时候随机性就更强了:

    d7d9c212196e4226676979db9d103865.png

    |今日打卡主题

    请在头条内打卡!

    推荐阅读  

    Python来看啥是佩奇

    我爬取了人人都是产品经理6574篇文章,发现产品经理竟然在看这些

    Python骚操作:用Python来PS

    aa8e3c70f05a68211060b0d6842799e8.png

    2019,我们一起让知识『好

    展开全文
  • 全文共5764字,预计学习时长11分钟人工智能与搜索通常,我们在浏览一些与人工智能相关话题、教程、或者文章时会发现,作者为了解释人工智能代理工作原理,常会用搜索问题作为例子。这是为什么呢?人工智能和...
    全文共5764字,预计学习时长11分钟
    c6e304b1cd40c33b349c8e826086ae1b.png

    人工智能与图搜索

    通常,我们在浏览一些与人工智能相关的话题、教程、或者文章时会发现,作者为了解释人工智能代理的工作原理,常会用图搜索问题作为例子。这是为什么呢?人工智能和经典的图搜索问题之间有什么关系呢?

    ea9041a6de05427702516919a2c3d7ca.png

    什么是人工智能

    查找各种资料后你会发现,对于人工智能并没有一个清晰而明确的定义。部分人认为“人工智能就是对理性主体的研究,此处的理性主体指任何能够作出决策的主体,可以是一个人、一个公司,也可以是机器或者软件”。在分析了过去和现在的感知经历和背景信息之后(即主体在某一特定环境中的感知输入),理性主体能够选择执行会产生最佳结果的行为。此外,对于人工智能还有其他一些定义,但它们主要从哲学的角度来探讨人类智能与机器智能之间的界限问题。

    然而,所有这些定义在谈的都是,当你不知道怎么做而又想知道怎么做的时候,人工智能就是能够给予你帮助的一门研究学科。理性主体会通过一些传感器来感知目前的环境,在分析过去已执行的行为之后,选择执行会带来最佳结果的行为。

    接下来,一起来了解一下经典的最佳路径问题。给出一幅图,上面有许多节点,你需要找出两个节点间总代价最小的路径。这个时候,人工智能代理就可以发挥作用了。当然,你自己不知道哪条是最佳路径;但是理性主体可以,它通过感知周围环境(此处也就是这幅图),快速找出最佳路径。

    但大家知道,能够解决图搜索问题的算法多种多样,比如深度优先搜索(DFS)、宽度优先搜索(BFS)、迪杰斯特拉算法(Dijkstra)和A星算法。一些人在高中可能就已经学过了,因此稀奇之处在哪呢?难道这就是人工智能代理的工作方式吗?的确是这样的,但也不全是。人工智能不仅仅包括图搜索算法这类编程模式,正如上文提到的,它依旧是对理性主体的研究,即通过对环境的分析,执行某一动作以取得最佳结果。

    人工智能代理是一个涵盖面比较宽泛的术语,它可以是机器学习、神经网络和深度学习等。此外,它也在金融、医疗和安保等领域得到广泛应用。所以,图搜索不过是人工智能的一个子领域。

    对于经典的图搜索算法与能够找出两节点间最短路径的人工智能代理之间的区别,不过是其各自使用的术语不同而已。如果你想要构建一个人工智能代理,其实这和构建一个传统的算法没什么区别,理解好这一点非常重要。

    ea9041a6de05427702516919a2c3d7ca.png

    传统算法

    能够进行图搜索的方法诸多,比较经典的算法有宽度优先搜索和深度优先搜索,这两种算法能够找到目标节点但无法计算最佳路径;此外还有一致代价搜索(Uniform Cost Search)、迪杰斯特拉算法和A星算法,这三类算法都能够计算出从源节点到目标节点之间的最短路径。总的来说,以上几类算法都属于生成树算法,唯一一点值得注意的是,图搜索可能包含回路,因此树形或许不会很明显。

    对于以上所有算法来说,最重要的一点是当我们在访问完一个节点之后,必须选择下一个未访问的节点继续访问,从而确认是否已经到达目标节点。

    宽度优先搜索

    正如上文所说,宽度优先搜索也是一种生成树算法。它之所以叫做宽度优先搜索,是因为整个图的遍历是逐层进行的。从源节点开始,首先访问它的邻接点(即同一层的节点),然后以此类推,继续访问下一层的节点。

    让我们来具体分析一下以下这幅图:

    1c9829edf88ef799956f7a0a0bd8afe9.png

    从节点A开始,看看它是如何长成“一棵树”的。

    4f54e4e99e936fb79efcf9d304cddf29.png

    A作为初始节点,处于0层,B和C处于1层,D和E处于2层。而这,正是宽度优先搜索将遍历整个图的顺序。

    即如果用宽度优先搜索算法遍历整个图,那么其访问顺序为:A -> B -> C -> D -> E。

    仔细观察整棵树,会发现B、C、E、D之间是连通的。之所以会这样,是因为这个图本身包含回路。但是,如果要以最优的方式遍历整个图,那么已经访问过的节点就不能再访问。因此在选择要访问的节点时,条件之一就是该节点未被访问过。

    宽度优先搜索算法的工作原理

    在访问了源节点之后,需要继续访问它所有的邻接点,然后再访问下一层的节点,所以此处需要一个队列。在访问一个节点之后,我们需要搜索它的邻接点,如果这些邻接点还未被访问,那么就需要将其加入到队列之中。然后,从队列中选出下一个节点继续访问。另一件非常重要的事,就是要记得标记已访问过的节点,避免重复访问。通过这种方式,我们就能遍历图中所有的节点,确保每个节点仅访问一次。

    一起来学习下面的这组伪代码:

    BFS(G, s, goal) Let Q be queue Q.enqueue(s) Mark s as visited while (Q is not empty) //Removing that vertex from queue v = Q.dequeue() If v is goal  return “found the goal” //processing all the neighbours of v  for all neighbours w of v in Graph G if w is not visited  //Stores w in Q to further visit its neighbour Q.enqueue(w)  mark w as visited

    因此通过这种算法,只要源节点和目标节点之间有至少一条路径,那么我们就能找到任何目标节点。

    寻找最小代价路径

    现在改变一下这幅图,在其每条边上都加上一定的代价值。

    5f1f142e02ac733dfaac7762e5a94f3a.png

    假设要从A到D,寻找出一条总代价最小的路径。要想从A到D,可选择的路径有许多。我们可以选择A - > B -> D,总代价是20;或者选择A -> C -> B -> D,而这条路的总代价低一点,但也要16。实际上,存在一条总代价为3的最优路径,即A -> C -> E -> D。但是,我们该如何找到这一路径呢?此刻我们需要改变选取下一个访问节点的方式。在使用经典的宽度优先搜索算法时,我们通常使用先进先出队列(FIFO)的方式来选择下一个访问的节点。通过这种方式,我们最终的确能找到目标节点,但是却并不一定是最小代价路径。因此,为了找到能到达目标节点的最小代价路径,我们需要改变一下从队列中选取访问节点的方式。

    接下来要介绍的这种算法叫做“一致代价搜索算法”(Uniform Cost Search),它其实算是迪杰斯特拉算法的改良版,因为在使用迪杰斯特拉算法时,一旦找到目标节点,搜索就会立即停止。在经典的迪杰斯特拉算法中,为了找到源节点到图中其他所有节点的最小代价路径,该算法会访问完图中所有节点,直至队列穷尽。此外,一致代价搜索与宽度优先搜索的不同之处就在于,在一致代价搜索中,从源节点到目前访问的节点的总代价值都会被储存起来。

    并且,队列中的顺序也不再是根据先进先出原则,而是基于目前的总代价值。也就是说,该算法会优先选择队列中未被访问、且当前代价值最低的节点进行访问。

    一起来看一下以下这组代码:

    UniformCostSrearch(G, s) s.costSoFar = 0; for all nodes w in G except s w.costSoFar = Int.maxInt Let Q be a priority queue ordered by cost_so_far Q.enqueue(s) while (Q is not empty) //Removing that vertex from queue v = Q.dequeue() If v is goal return “found the goal”  //processing all the neighbours of v  for all neighbours w of v in Graph G currentCost = dist[v,w] newCost = v.costSoFar + currentCost; If (newCost < w.costSoFar) w.costSoFar = newCost ; Q.enqueue(w)

    因此,基于最低代价原则,我们就能选出下一个继续访问的节点。

    但是,当前的最低代价需要不断更新,因为在继续遍历整个图的过程中,我们总是能找到更优的路径。因此,在访问某个节点时,需要了解一下它所有的邻接点,并且将它们目前的代价与新的代价进行比较,新的代价也就是目前所访问的节点的总代价和该节点与其邻接点间的距离。

    currentCost = dist[v,w]newCost = v.costSoFar + currentCost;If (newCost < w.costSoFar) { w.costSoFar = newCost ; Q.enqueue(w);}

    如果新的代价更低,那么这意味着我们找到了一条抵达目标节点更好的路径,所以需要继续更新当前的代价。进一步了解该算法的更多细节:https://dzone.com/articles/from-dijkstra-to-a-star-a,并且通过使用估价函数,也能将该算法转换为A星算法。

    ea9041a6de05427702516919a2c3d7ca.png

    图搜索与人工智能的关系

    现在,我们再来总结一下人工智能到底是什么。正如上文所给出的定义,人工智能就是对理性主体的研究,此处的理性主体指任何能够作出决策的主体,可以是一个人、一个公司,也可以是机器或者软件”。在分析了过去和现在的感知经历和背景信息之后(即主体在某一特定环境中的感知输入),理性主体能够选择执行对自己有最佳结果的行为。

    但是通过图搜索算法,我们能获得什么呢?能获得一个函数、一个程序、一个理性主体。因此,如果给出一幅图,一个环境,以及一个源节点,那么通过使用图搜索算法,在分析了过去和当前对环境的感知经验之后,便能计算出一系列的行动以找到目标节点。

    以上我们可以看出,图搜索算法的功能是符合人工智能代理的定义的。因此,我们也完全可以将其视为一种初级的人工智能。所以说,人工智能也并不是什么高深莫测、不可企及的科学。人工智能的定义是非常宽泛的,甚至包括像图搜索这种简单算法。通过这些例子,我们也能大概了解一下人工智能的基本概念。

    了解了人工智能的概念之后,我们可以试着来构建一个人工智能代理来分析周围环境,并且计算出一系列行动以帮助我们达到某一特定目的(在这里本质上使用的还是图搜索算法,只是借助了人工智能的术语)。

    以下是一幅罗马尼亚(Romania)地图。

    21c85f5b53fca4b5936425cb564190cb.png

    假设我们目前正处于Arad,想要走一条最近的路前往Bucharest。很明显,我们有很多条路线可以选择,比如可以从Arad先到Timisoara,然后经过Lugoj等城市最后到达Bucharest;或者,也可以选择经过Sibiu和Fagaras后直接到达目的地。但是,我们仍然不知道哪条路径的代价最低。

    罗马尼亚问题的定义

    该问题可以分解为几个部分:

    · 初始状态:位于Arad。

    · 函数行动(s):当我们处于某一状态,则会有一系列的可能行动。例如:我们位于Arad,则可能会前往Zerind、Sibiu,或者Timisoara。

    · 函数结果(s,a) -> s’:如果我们处于状态s,执行行动a就会到达s’。

    · 函数目标测试 (s) -> t/f:它能告诉我们是否已经到达目的地。

    · 步骤代价 (s,a,s’) -> 行动代价:当我们执行行动a,从s到s'时,它能告诉我们该过程中每一步的代价。

    · 代价 (S1 -> S2 -> … -> Sn) -> n (路径代价):该路径的总代价。

    现在,让我们来分析一下这幅罗马尼亚地图是如何在该路径问题中体现出来的。我们的初始状态是在Arad,当我们到达Bucharest,则目标测试函数回溯。该过程中,所有可能的状态叫做状态空间,并且我们必须通过执行行动来逐个搜索状态空间。初始状态于Arad并且执行函数行动 (“Arad”),会产生三种可能的行动,即去往Zerind,Timisoara,或者Sibiu。现在,记住这一点,接下来我们将把状态空间分为三部分:

    · 已扩展的状态:目前仅指Arad。

    · 前驱节点:目前已扩展的最远的状态(也就是Zerind、Timisoara,以及Sibiu)。

    · 尚未扩展的状态:剩下的所有城市。

    因此,当处于已扩展的状态时,我们就需要从前驱节点中选择一个新状态,执行一个行动,然后进入这个新状态,这样前驱节点也得以扩展。

    TreeSearch(G, s) s.costSoFar = 0; for all nodes w in G except s w.costSoFar = Int.maxInt Let frontier be a priority queue ordered by the cost_so_far frontier.enqueue(s) while (frontier is not empty) //Removing that vertex from frontier,whose neighbour will be visited now v = frontier.dequeue() If v is goal return “found the goal”  //processing all the neighbours of v  for all neighbours w of v in Graph G currentCost = dist[v,w] newCost = v.costSoFar + currentCost; If (newCost < w.costSoFar) { w.costSoFar = newCost ; frontier.enqueue(w)

    因此在初始阶段,前驱节点中只有一个源节点。在之后的每一次迭代过程中,我们从前驱节点中获取一个节点,然后进入下一个状态。一旦我们到达目标状态,就会发出信息“已找到目标”并随即结束搜索。我们也可以选择打印路径,或者将新状态添加到前驱节点中。

    因此,根据你从前驱节点中选择新状态的不同方式,相应地也会执行不同的算法,比如可以执行经典的宽度优先搜索、一致代价搜索,或者A星算法。

    想要更加清楚地了解这些算法之间的区别,并且找到最适合的算法来搜索从Arad到Bucharest的最短路径:https://dzone.com/articles/from-dijkstra-to-a-star-a

    ea9041a6de05427702516919a2c3d7ca.png

    结语

    当然,人工智能代理也不只是应用于图搜索,相关的人工智能算法也广泛应用于面部识别、机器学习、神经网络和统计算法领域,但要理解这些需要一定的数学基础。实际上,也不必过多担心或者被它们的难度吓到,因为总的来说,它们的基本概念还是不难理解的。

    74a97e0f551142e50ba047d2a18fdb60.png

    留言 点赞 关注

    我们一起分享AI学习与发展的干货

    如需转载,请后台留言,遵守转载规范

    展开全文
  • 全文共5764字,预计学习时长11分钟人工智能与搜索通常,我们在浏览一些与人工智能相关话题、教程、或者文章时会发现,作者为了解释人工智能代理工作原理,常会用搜索问题作为例子。这是为什么呢?人工智能和...
    全文共5764字,预计学习时长11分钟
    ce11f5b3871032f9893849cc1492a91c.png

    人工智能与图搜索

    通常,我们在浏览一些与人工智能相关的话题、教程、或者文章时会发现,作者为了解释人工智能代理的工作原理,常会用图搜索问题作为例子。这是为什么呢?人工智能和经典的图搜索问题之间有什么关系呢?

    aaf661c99f3edec64edd73b3f3c3fb83.png

    什么是人工智能

    查找各种资料后你会发现,对于人工智能并没有一个清晰而明确的定义。部分人认为“人工智能就是对理性主体的研究,此处的理性主体指任何能够作出决策的主体,可以是一个人、一个公司,也可以是机器或者软件”。在分析了过去和现在的感知经历和背景信息之后(即主体在某一特定环境中的感知输入),理性主体能够选择执行会产生最佳结果的行为。此外,对于人工智能还有其他一些定义,但它们主要从哲学的角度来探讨人类智能与机器智能之间的界限问题。

    然而,所有这些定义在谈的都是,当你不知道怎么做而又想知道怎么做的时候,人工智能就是能够给予你帮助的一门研究学科。理性主体会通过一些传感器来感知目前的环境,在分析过去已执行的行为之后,选择执行会带来最佳结果的行为。

    接下来,一起来了解一下经典的最佳路径问题。给出一幅图,上面有许多节点,你需要找出两个节点间总代价最小的路径。这个时候,人工智能代理就可以发挥作用了。当然,你自己不知道哪条是最佳路径;但是理性主体可以,它通过感知周围环境(此处也就是这幅图),快速找出最佳路径。

    但大家知道,能够解决图搜索问题的算法多种多样,比如深度优先搜索(DFS)、宽度优先搜索(BFS)、迪杰斯特拉算法(Dijkstra)和A星算法。一些人在高中可能就已经学过了,因此稀奇之处在哪呢?难道这就是人工智能代理的工作方式吗?的确是这样的,但也不全是。人工智能不仅仅包括图搜索算法这类编程模式,正如上文提到的,它依旧是对理性主体的研究,即通过对环境的分析,执行某一动作以取得最佳结果。

    人工智能代理是一个涵盖面比较宽泛的术语,它可以是机器学习、神经网络和深度学习等。此外,它也在金融、医疗和安保等领域得到广泛应用。所以,图搜索不过是人工智能的一个子领域。

    对于经典的图搜索算法与能够找出两节点间最短路径的人工智能代理之间的区别,不过是其各自使用的术语不同而已。如果你想要构建一个人工智能代理,其实这和构建一个传统的算法没什么区别,理解好这一点非常重要。

    aaf661c99f3edec64edd73b3f3c3fb83.png

    传统算法

    能够进行图搜索的方法诸多,比较经典的算法有宽度优先搜索和深度优先搜索,这两种算法能够找到目标节点但无法计算最佳路径;此外还有一致代价搜索(Uniform Cost Search)、迪杰斯特拉算法和A星算法,这三类算法都能够计算出从源节点到目标节点之间的最短路径。总的来说,以上几类算法都属于生成树算法,唯一一点值得注意的是,图搜索可能包含回路,因此树形或许不会很明显。

    对于以上所有算法来说,最重要的一点是当我们在访问完一个节点之后,必须选择下一个未访问的节点继续访问,从而确认是否已经到达目标节点。

    宽度优先搜索

    正如上文所说,宽度优先搜索也是一种生成树算法。它之所以叫做宽度优先搜索,是因为整个图的遍历是逐层进行的。从源节点开始,首先访问它的邻接点(即同一层的节点),然后以此类推,继续访问下一层的节点。

    让我们来具体分析一下以下这幅图:

    08b76c0278d854b50b417d7e62a8f3ac.png

    从节点A开始,看看它是如何长成“一棵树”的。

    3e1a86d5dbbf9510d86ae7f4e309d785.png

    A作为初始节点,处于0层,B和C处于1层,D和E处于2层。而这,正是宽度优先搜索将遍历整个图的顺序。

    即如果用宽度优先搜索算法遍历整个图,那么其访问顺序为:A -> B -> C -> D -> E。

    仔细观察整棵树,会发现B、C、E、D之间是连通的。之所以会这样,是因为这个图本身包含回路。但是,如果要以最优的方式遍历整个图,那么已经访问过的节点就不能再访问。因此在选择要访问的节点时,条件之一就是该节点未被访问过。

    宽度优先搜索算法的工作原理

    在访问了源节点之后,需要继续访问它所有的邻接点,然后再访问下一层的节点,所以此处需要一个队列。在访问一个节点之后,我们需要搜索它的邻接点,如果这些邻接点还未被访问,那么就需要将其加入到队列之中。然后,从队列中选出下一个节点继续访问。另一件非常重要的事,就是要记得标记已访问过的节点,避免重复访问。通过这种方式,我们就能遍历图中所有的节点,确保每个节点仅访问一次。

    一起来学习下面的这组伪代码:

    BFS(G, s, goal) Let Q be queue Q.enqueue(s) Mark s as visited while (Q is not empty) //Removing that vertex from queue v = Q.dequeue() If v is goal  return “found the goal” //processing all the neighbours of v  for all neighbours w of v in Graph G if w is not visited  //Stores w in Q to further visit its neighbour Q.enqueue(w)  mark w as visited

    因此通过这种算法,只要源节点和目标节点之间有至少一条路径,那么我们就能找到任何目标节点。

    寻找最小代价路径

    现在改变一下这幅图,在其每条边上都加上一定的代价值。

    656eea9361fdfd48883609446d22a1b3.png

    假设要从A到D,寻找出一条总代价最小的路径。要想从A到D,可选择的路径有许多。我们可以选择A - > B -> D,总代价是20;或者选择A -> C -> B -> D,而这条路的总代价低一点,但也要16。实际上,存在一条总代价为3的最优路径,即A -> C -> E -> D。但是,我们该如何找到这一路径呢?此刻我们需要改变选取下一个访问节点的方式。在使用经典的宽度优先搜索算法时,我们通常使用先进先出队列(FIFO)的方式来选择下一个访问的节点。通过这种方式,我们最终的确能找到目标节点,但是却并不一定是最小代价路径。因此,为了找到能到达目标节点的最小代价路径,我们需要改变一下从队列中选取访问节点的方式。

    接下来要介绍的这种算法叫做“一致代价搜索算法”(Uniform Cost Search),它其实算是迪杰斯特拉算法的改良版,因为在使用迪杰斯特拉算法时,一旦找到目标节点,搜索就会立即停止。在经典的迪杰斯特拉算法中,为了找到源节点到图中其他所有节点的最小代价路径,该算法会访问完图中所有节点,直至队列穷尽。此外,一致代价搜索与宽度优先搜索的不同之处就在于,在一致代价搜索中,从源节点到目前访问的节点的总代价值都会被储存起来。

    并且,队列中的顺序也不再是根据先进先出原则,而是基于目前的总代价值。也就是说,该算法会优先选择队列中未被访问、且当前代价值最低的节点进行访问。

    一起来看一下以下这组代码:

    UniformCostSrearch(G, s) s.costSoFar = 0; for all nodes w in G except s w.costSoFar = Int.maxInt Let Q be a priority queue ordered by cost_so_far Q.enqueue(s) while (Q is not empty) //Removing that vertex from queue v = Q.dequeue() If v is goal return “found the goal”  //processing all the neighbours of v  for all neighbours w of v in Graph G currentCost = dist[v,w] newCost = v.costSoFar + currentCost; If (newCost < w.costSoFar) w.costSoFar = newCost ; Q.enqueue(w)

    因此,基于最低代价原则,我们就能选出下一个继续访问的节点。

    但是,当前的最低代价需要不断更新,因为在继续遍历整个图的过程中,我们总是能找到更优的路径。因此,在访问某个节点时,需要了解一下它所有的邻接点,并且将它们目前的代价与新的代价进行比较,新的代价也就是目前所访问的节点的总代价和该节点与其邻接点间的距离。

    currentCost = dist[v,w]newCost = v.costSoFar + currentCost;If (newCost < w.costSoFar) { w.costSoFar = newCost ; Q.enqueue(w);}

    如果新的代价更低,那么这意味着我们找到了一条抵达目标节点更好的路径,所以需要继续更新当前的代价。进一步了解该算法的更多细节:https://dzone.com/articles/from-dijkstra-to-a-star-a,并且通过使用估价函数,也能将该算法转换为A星算法。

    aaf661c99f3edec64edd73b3f3c3fb83.png

    图搜索与人工智能的关系

    现在,我们再来总结一下人工智能到底是什么。正如上文所给出的定义,人工智能就是对理性主体的研究,此处的理性主体指任何能够作出决策的主体,可以是一个人、一个公司,也可以是机器或者软件”。在分析了过去和现在的感知经历和背景信息之后(即主体在某一特定环境中的感知输入),理性主体能够选择执行对自己有最佳结果的行为。

    但是通过图搜索算法,我们能获得什么呢?能获得一个函数、一个程序、一个理性主体。因此,如果给出一幅图,一个环境,以及一个源节点,那么通过使用图搜索算法,在分析了过去和当前对环境的感知经验之后,便能计算出一系列的行动以找到目标节点。

    以上我们可以看出,图搜索算法的功能是符合人工智能代理的定义的。因此,我们也完全可以将其视为一种初级的人工智能。所以说,人工智能也并不是什么高深莫测、不可企及的科学。人工智能的定义是非常宽泛的,甚至包括像图搜索这种简单算法。通过这些例子,我们也能大概了解一下人工智能的基本概念。

    了解了人工智能的概念之后,我们可以试着来构建一个人工智能代理来分析周围环境,并且计算出一系列行动以帮助我们达到某一特定目的(在这里本质上使用的还是图搜索算法,只是借助了人工智能的术语)。

    以下是一幅罗马尼亚(Romania)地图。

    8a3d65c1b2ba4fe9cdbf45c7fdfc14c0.png

    假设我们目前正处于Arad,想要走一条最近的路前往Bucharest。很明显,我们有很多条路线可以选择,比如可以从Arad先到Timisoara,然后经过Lugoj等城市最后到达Bucharest;或者,也可以选择经过Sibiu和Fagaras后直接到达目的地。但是,我们仍然不知道哪条路径的代价最低。

    罗马尼亚问题的定义

    该问题可以分解为几个部分:

    · 初始状态:位于Arad。

    · 函数行动(s):当我们处于某一状态,则会有一系列的可能行动。例如:我们位于Arad,则可能会前往Zerind、Sibiu,或者Timisoara。

    · 函数结果(s,a) -> s’:如果我们处于状态s,执行行动a就会到达s’。

    · 函数目标测试 (s) -> t/f:它能告诉我们是否已经到达目的地。

    · 步骤代价 (s,a,s’) -> 行动代价:当我们执行行动a,从s到s'时,它能告诉我们该过程中每一步的代价。

    · 代价 (S1 -> S2 -> … -> Sn) -> n (路径代价):该路径的总代价。

    现在,让我们来分析一下这幅罗马尼亚地图是如何在该路径问题中体现出来的。我们的初始状态是在Arad,当我们到达Bucharest,则目标测试函数回溯。该过程中,所有可能的状态叫做状态空间,并且我们必须通过执行行动来逐个搜索状态空间。初始状态于Arad并且执行函数行动 (“Arad”),会产生三种可能的行动,即去往Zerind,Timisoara,或者Sibiu。现在,记住这一点,接下来我们将把状态空间分为三部分:

    · 已扩展的状态:目前仅指Arad。

    · 前驱节点:目前已扩展的最远的状态(也就是Zerind、Timisoara,以及Sibiu)。

    · 尚未扩展的状态:剩下的所有城市。

    因此,当处于已扩展的状态时,我们就需要从前驱节点中选择一个新状态,执行一个行动,然后进入这个新状态,这样前驱节点也得以扩展。

    TreeSearch(G, s) s.costSoFar = 0; for all nodes w in G except s w.costSoFar = Int.maxInt Let frontier be a priority queue ordered by the cost_so_far frontier.enqueue(s) while (frontier is not empty) //Removing that vertex from frontier,whose neighbour will be visited now v = frontier.dequeue() If v is goal return “found the goal”  //processing all the neighbours of v  for all neighbours w of v in Graph G currentCost = dist[v,w] newCost = v.costSoFar + currentCost; If (newCost < w.costSoFar) { w.costSoFar = newCost ; frontier.enqueue(w)

    因此在初始阶段,前驱节点中只有一个源节点。在之后的每一次迭代过程中,我们从前驱节点中获取一个节点,然后进入下一个状态。一旦我们到达目标状态,就会发出信息“已找到目标”并随即结束搜索。我们也可以选择打印路径,或者将新状态添加到前驱节点中。

    因此,根据你从前驱节点中选择新状态的不同方式,相应地也会执行不同的算法,比如可以执行经典的宽度优先搜索、一致代价搜索,或者A星算法。

    想要更加清楚地了解这些算法之间的区别,并且找到最适合的算法来搜索从Arad到Bucharest的最短路径:https://dzone.com/articles/from-dijkstra-to-a-star-a

    aaf661c99f3edec64edd73b3f3c3fb83.png

    结语

    当然,人工智能代理也不只是应用于图搜索,相关的人工智能算法也广泛应用于面部识别、机器学习、神经网络和统计算法领域,但要理解这些需要一定的数学基础。实际上,也不必过多担心或者被它们的难度吓到,因为总的来说,它们的基本概念还是不难理解的。

    e5b50d01fda831822ff6c820c7db0a5d.png

    留言 点赞 关注

    我们一起分享AI学习与发展的干货

    如需转载,请后台留言,遵守转载规范

    展开全文
  • 举个栗子栗子转换 为临接矩阵可以转化为数据问题:矩阵表示根据深度优先搜索,我们这里默认按行进行遍历,对于第一行,起始节点就是第一行对应到那个元素0,遍历到第二个元素时发现不为0,则节点0可以到达节点1;...
  • 1.图的宽度优先搜索代码非常容易实现,如果你会二叉树的层序遍历,那么图的宽度优先搜索就是在层序遍历的基础之上,引入visited集合,每当入队时,首先考虑入队结点是否处于visited集合中,如果在,说明曾经入队,就...
  • ##【数据结构遍历】java实现广度优先和深度优先遍历 宽度优先搜索(BFS)遍历需要使用队列queue数据结构; 深度优先搜索(DFS, Depth First Search)的实现 需要使用到栈stack数据结构。java中虽然有Queue接口,单...
  • 用队列实现图的非递归BFS。首先把遍历起始顶点push进队列;然后每次从队列中pop一个顶点时,都遍历此顶点,并遍历边表,找出与此顶点相连接的顶点,若此连接顶点未被访问,则入队,若此顶点已被访问,则继续,直到...
  • 整个的宽度优先爬虫过程就是从一系列的种子节点开始,把这些网页中(种子结点网页)的“子节点” (也就是超链接)提取出来,放入队列中依次进行抓取。被处理过的链接需要放入一张表(通常称 为 Visited 表)中。每次新...
  • 这题没什么说的,就是给你一个图,给出这个图的深度复制结果 深度优先 对于深度优先算法,最重要的是使用一个哈希表来维持visited过的点,具体实现见代码: /* // Definition for a Node. class Node { public: .....
  • 数据结构遍历】java实现广度优先和深度优先遍历宽度优先搜索(BFS)遍历需要使用队列queue数据结构; 深度优先搜索(DFS, Depth First Search)的实现需要使用到栈stack数据结构。java中虽然有Queue接口,单java...
  • 一、BFS算法思路本算法以无向为例,存储...true表示已访问)3)从A未被访问邻接点出发,宽度优先遍历图,直到中所有和v有路径相通顶点都被访问到宽度优先遍历需要借助队列,思想与二叉树层序遍历类似...
  • //插入边函数、变量u是行号,v是列号,w是边权重 if ( u < 1 || v < 1 || u > mg - > n || v > mg - > n || u == v ) { cout "Not Exist!" endl ; return 0 ; } if ( mg - > a [ u - 1 ] [ v - ...
  • 关于Queue.h以及Queue.cpp原码请参考上一篇文章。 https://blog.csdn.net/weixin_41594045/article/details/90898792 #include <iostream> #include <stdio.h> #include <stdlib.h> #include ...
  • 一、算法思路本算法以无向为例,存储方式采用邻接...true表示已访问)3)从A未被访问邻接点出发,宽度优先遍历图,直到中所有和v有路径相通顶点都被访问到二、BFS测试用例 本算法测试用例为《大话数据...
  • 题目:以实验3.1所示邻接矩阵为存储结构,编写程序,实现图的深度、宽度优先遍历。 部分代码: 邻接矩阵的单一顶点DFS: //邻接矩阵的单一顶点DFS void DFS(int v,int visited[],mGraph g){ int j; printf(&...
  • 题目:以实验3.3所示邻接表为存储结构,编写程序,实现图的深度、宽度优先遍历。 部分代码: 邻接表的单一顶点DFS: //邻接表的单一顶点DFS void DFS(int v,int visited[],LGraph g){ ENode *w; printf("...
  • 数据结构遍历】java实现广度优先和深度优先遍历 宽度优先搜索(BFS)遍历需要使用队列queue数据结构; 深度优先搜索(DFS, Depth First Search)的实现 需要使用到栈stack数据结构。 java中虽然有Queue接口,...
  • 图的广度优先遍历

    千次阅读 2016-05-29 00:30:08
    图的广度优先遍历与树的宽度优先遍历类似,实现方法也类似。但是相对树,图存在一种特殊情况——环路,环路使得一个已经遍历过的结点,会在其后代结点的子结点中再次被遍历,从而产生多余的读取操作。为了解决这个...
  • 流程: 1,利用队列实现 2,从源节点开始依次按照宽度进队列,然后弹出 3,每弹出一个点,把该节点所有没有进过队列的邻接点放入队 列 4,直到队列变空图的表示和生成见:点击打开链接import java.util.HashSet;...
  • 这道题本来用广度递归来实现,编写完后发现AC不了,想想应该是 爆栈了,后来有改成用广度队列来写,可以AC啦! 思路是: 考虑到圈外点肯定会和边框相交,所以就先把四条边非0点入队, 入队一个点,就把这个...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 178
精华内容 71
关键字:

实现图的宽度优先遍历