Data Structure_Visualization概率模拟排序可视化走迷宫生成迷宫

西红柿炒鸡蛋

发布于 2018-12-28 12:16:51

8190

发布于 2018-12-28 12:16:51

文章被收录于专栏：自学笔记

概率模拟

随机模拟问题

概率问题对于人脑来说很多时候都是反直觉的，所以有时候得到的结果并不是这么完美。首先来看一个分钱问题。假设房间里面有100个人，每个人都有100元钱，他们在玩一个游戏，每一个人拿出一元钱随机给另一个人，最后这100人的财富分布是怎么样的。按照常规思维，其实无论怎么分应该大家都是差不多钱的。

https://cloud.tencent.com/developer/article/1386966 使用这篇文章的模板作为可视化的模板，只需要填写逻辑就好了。

过程很简单，其实就是遍历每一个人，随机一下给钱的人即可。

            AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Blue);
            int w = canvasWidth / money.length;
            for (int i = 0; i < money.length; i++) {
                AlgorithmHelper.fillRectangle(graphics2D, i * w + 1, canvasHeight - money[i], w - 1, money[i]);
            }

在paintComponent函数里面加上画矩形的函数，要注意y坐标的转换，因为这个坐标是屏幕坐标而不是我们常规的理解的坐标。

    private void run() {
        while (true){
            frame.render(money);
            AlgorithmHelper.pause(DELAY);
            for (int i = 0; i < money.length; i++) {
                if (money[i] > 0){
                    int j = (int) (Math.random() * money.length);
                    money[i] -= 1;
                    money[j] += 1;
                }
            }
        }
    }

接着更改run函数，也就是线程函数即可。结果其实并不是平均，而是有些比较突出：

这样就模拟了整个过程。其实这个过程还没有看到完全的分布，只是有这个趋势。加快只是使用delay的值，也就是提高线程的睡眠时间而已，是很有限制的。我们是每画一次就进行一次，可以每画k次才画一次，通过动画逻辑增加动画进行时间。

            for (int k = 0; k < 50; k++)
                for (int i = 0; i < money.length; i++) {
                    if (money[i] > 0) {
                        int j = (int) (Math.random() * money.length);
                        money[i] -= 1;
                        money[j] += 1;
                    }
                }

这样其实还是看不出来，可以使用排序看看效果。

蒙特卡洛方法

蒙特卡洛是一种统计学的方法，是一种模拟，通过大量的随机样本去了解一个系统，进而得到所需要计算的值。蒙特卡洛算法得到的并不是一个真值，而是一个近似值。蒙特卡洛方法求pi值，园的面积

，正方形的面积

，上除于下，就可以得到

，首先可以随机一个点，看看这个点是落在了园内还是园外，如果打的点多，那么就是可以知道这个园的大概形状。

那么面积的比值就可以是总点数/红点数。使用这样的方式就可以得到pi值。

    private void run() {
        for (int i = 0; i < N; i++) {
            //System.out.println("run");
            frame.render(circle, points);
            AlgorithmHelper.pause(DELAY);
            int x = (int)(Math.random() * frame.getCanvasWidth());
            int y = (int)(Math.random() * frame.getCanvasHeight());
            points.add(new Point(x, y));
        }
    }

核心方法，Frame中的画图方法：

            AlgorithmHelper.setStrokeWidth(graphics2D, 3);
            AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Blue);
            AlgorithmHelper.strokeCircle(graphics2D, circle.getX(), circle.getY(), circle.getR());
            for (int i = 0; i < points.size(); i++) {
                Point p = points.get(i);
                if (circle.contain(p)) {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red);
                } else {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Blue);
                }
                AlgorithmHelper.fillCircle(graphics2D, p.x, p.y, 3);
                //System.out.println("draw");
            }

排序可视化

SelectionSort

选择排序很简单，所有的排序算法在前面的博客都有讲解：

https://cloud.tencent.com/developer/article/1386945

选择排序很简单，遍历所有元素，查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程，可以用不同颜色代表排好序和未排好序的。

            int w = canvasWidth / data.N();
            AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
            for (int i = 0; i < data.N(); i++) {
                if (i < data.orderIndex) {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red);
                } else {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Grey);
                }
                if (i == data.currentIndex) {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Indigo);
                }
                if (i == data.currentComperent) {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
                }
                AlgorithmHelper.fillRectangle(graphics2D, i * w, canvasHeight - data.get(i), w - 1, data.get(i));
            }

        }

Frame的画图函数主要构成部分，其余的都是模板，为了抽象性，所以把selection的数据集中起来形成一个新的类，包括了生成数据等等。

public class SelectionSortData {
    private int[] numbers;
    public int orderIndex = -1;
    public int currentIndex = -1;
    public int currentComperent = -1;

    public SelectionSortData(int N, int randomBound) {
        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = (int) (Math.random() * randomBound) + 1;
            //System.out.println(numbers[i]);
        }
    }

    public void setData(int orderIndex, int currentComperent, int currentIndex){
        this.currentIndex = currentIndex;
        this.currentComperent = currentComperent;
        this.orderIndex = orderIndex;
    }

    public int N(){
        return numbers.length;
    }

    public int get(int index){
        if (index < 0 || index >= numbers.length){
            throw new IllegalArgumentException("index is illgel!");
        }
        return numbers[index];
    }

    public void swap(int i, int j){
        int t = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = t;
    }


}

在这个数据类里面有三个属性，分别是已经排好序的索引，当前最小值，当前正在比较的索引。在渲染过程中需要改变就是这几个颜色了。所以动态的效果主要来源就是通过改变着几个值即可。

    private void run() {
        data.setData(0,-1,-1);
        frame.render(data);
        AlgorithmHelper.pause(DELAY);

        for (int i = 0; i < data.N(); i++) {
            int midIndex = i;
            data.setData(i, -1, midIndex);
            frame.render(data);
            AlgorithmHelper.pause(DELAY);

            for (int j = i+1; j < data.N(); j++) {
                data.setData(i, j, midIndex);
                frame.render(data);
                AlgorithmHelper.pause(DELAY);

                if (data.get(j) < data.get(midIndex)){
                    midIndex = j;
                    data.setData(i, j, midIndex);
                    frame.render(data);
                    AlgorithmHelper.pause(DELAY);

                }
            }
            data.swap(i, midIndex);
            data.setData(i+1, -1, -1);
            frame.render(data);
            AlgorithmHelper.pause(DELAY);
        }
        data.setData(data.N(), -1,-1);
        frame.render(data);
        AlgorithmHelper.pause(DELAY);

    }

查看一下效果：

InsertionSort

插入排序也很简单，没有涉及到递归操作等等。每遍历一个元素，看看这个元素和之前比较过的位置是在那里，像打牌的时候插排一样。和之前的查找一样，已经排好序的位置就直接用红色表示，当前对比位置用蓝色表示。首先是画图paintComponent：

            int w = canvasWidth / data.N();
            for (int i = 0; i < data.N(); i++) {
                if (i < data.orderIndex){
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red );
                }else {
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Grey);
                }
                if (i == data.currentIndex){
                    AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
                }
                AlgorithmHelper.fillRectangle(graphics2D, i * w, canvasHeight - data.get(i), w - 1, data.get(i));
            }
        }

和上面的选择排序差不多。

    private void run() {
        setData(-1, -1);
        for (int i = 0; i < data.N(); i++) {
            setData(i, i);
            for (int j = i; j > 0 && data.get(j) < data.get(j - 1); j--) {
                data.swap(j, j - 1);
                setData(i+1, j-1);
            }
            setData(i, -1);
        }
        setData(data.N(), -1);
    }

    private void setData(int orderIndex, int currentIndex){
        data.orderIndex = orderIndex;
        data.currentIndex = currentIndex;
        frame.render(data);
        AlgorithmHelper.pause(DELAY);
    }

都是常规操作。

MergeSort

归并排序本身的思路，面对一个数组想要让他排序，首先把数组分成两部分，用同样的算法把两边排序，最后归并两边。在划分的时候，划分到不能再划分为止。首先同样要有一个归并的数据类：

public class MergeData {
    private int[] numbers;
    public int l, r;
    public int mergeIndex;

    public MergeData(int N, int randomBound) {
        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = (int) (Math.random() * randomBound) + 1;
            //System.out.println(numbers[i]);
        }
    }


    public int N(){
        return numbers.length;
    }

    public int get(int index){
        if (index < 0 || index >= numbers.length){
            throw new IllegalArgumentException("index is illgel!");
        }
        return numbers[index];
    }

    public void set(int index, int num){
        if (index < 0 || index >= numbers.length){
            throw new IllegalArgumentException("index is illgel!");
        }
        numbers[index] = num;
    }

    public void swap(int i, int j){
        int t = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = t;
    }

}

用l和r来表示正在归并的数组范围，mergeIndex表示已经进行归并了的集合。归并整个过程前面的博客有写，不再复述了。

    private void run() {
        setData(-1, -1, -1 );
        Merge(0, data.N()-1);
        setData(0, data.N()-1, -1);
    }

    private void Merge(int l, int r) {
        if (l >= r) {
            return;
        }
        setData(l, r, -1);
        int mid = (l + r) / 2;
        Merge(l, mid);
        Merge(mid + 1, r);
        merge(l, r, mid);
    }

    private void merge(int l, int r, int mid) {
        int[] array = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            array[i - l] = data.get(i);
        }
        int i = l, j = mid + 1;
        int index = l;
        while (i <= mid && j <= r) {
            if (array[i - l] < array[j - l]) {
                data.set(index, array[i - l]);
                i++;
                index++;
            } else {
                data.set(index, array[j - l]);
                j++;
                index++;
            }
            setData(l, r, index);
        }
        if (i <= mid) {
            for (int k = i; k <= mid; k++) {
                data.set(index, array[k - l]);
                index++;
                setData(l, r, index);
            }
        } else if (j <= r) {
            for (int k = j; k <= r; k++) {
                data.set(index, array[k - l]);
                index++;
                setData(l, r, index);
            }
        }
    }

效果：

QuickSort

快速排序，快速排序是在平均情况下比较快的算法了。每一次把第一个元素作为标定的位置，把这个位置放到合适的位置即可。首先还是需要一个快拍数据类：

public class QuickSortData {
    private int[] numbers;
    public int l, r;
    public int Index;

    public QuickSortData(int N, int randomBound) {
        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = (int) (Math.random() * randomBound) + 1;
            //System.out.println(numbers[i]);
        }
    }


    public int N(){
        return numbers.length;
    }

    public int get(int index){
        if (index < 0 || index >= numbers.length){
            throw new IllegalArgumentException(index + "index is illgel!");
        }
        return numbers[index];
    }

    public void set(int index, int num){
        if (index < 0 || index >= numbers.length){
            throw new IllegalArgumentException("index is illgel!");
        }
        numbers[index] = num;
    }

    public void swap(int i, int j){
        int t = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = t;
    }

}

和前面的归并排序一样，l和r用不同的颜色。

    private void run() {
        setData(-1, -1, -1);
        QuickSort(0, data.N() - 1);
        setData(0, data.N() - 1, -1);
    }

    private void QuickSort(int l, int r) {
        if (l >= r) {
            return;
        }
        setData(l, r, -1);
        int mid = partition(l, r);
        QuickSort(l, mid - 1);
        QuickSort(mid + 1, r);
        frame.render(data);
        AlgorithmHelper.pause(DELAY);
    }

    private int partition(int l, int r) {
        int v = data.get(l);
        int i = l + 1;
        int j = r;
        setData(l, r, l);
        while (true) {
            while (i <= r && data.get(i) < v) {
                i++;
            }
            while (j >= l + 1 && data.get(j) > v) {
                j--;
            }
            if (i > j) {
                break;
            }
            data.swap(i, j);
            setData(l, r, l);
            i++;
            j--;
        }
        data.swap(j, l);
        setData(l, r, j);
        return j;
    }

和前面基本一致。

走迷宫

显示迷宫

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

第一行是行数和列数，代表有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 < N; i++) {
                String line = scanner.nextLine();
                if (line.length() != M) {
                    throw new IllegalArgumentException("Message of file is not completed!");
                }
                for (int j = 0; j < M; 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 < N && y >= 0 && y < M;
    }

    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即可。

迷宫问题

白色方块是可以走的路径，红色的就是墙。迷宫的本质就是一个图结构。可以把整个迷宫当成是一个图，而走迷宫的过程就可以等价成是图的遍历。从起始点开始遍历，直到遍历到了某一个终止点即可。如果遍历了所有点都没有得到结果，那么就可以确认无解了。

图的遍历可以分成两种遍历。深度优先遍历和广度优先遍历，一种遍历是按照深度，先往一个方向深了走，没有路了再回头，而广度是先广度走一遍再一层一层下去。首先固定了每一个迷宫的出口和入口位置，从一开始，就需要从相邻的四个方向走迷宫，如果可以就继续，不能就回头，其实就是递归实现。

深度优先

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

    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;
        }
    }

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

这就是生成的结果了。

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

    private boolean go_iteration() {
        Stack<Position> 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;
    }

广度优先

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

    private boolean go_level() {
        Queue<Position> 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;
    }

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

生成迷宫

刚刚是走迷宫，刚刚生成的那个用例其实就是生成的迷宫。对于一个迷宫，只有一个入口一个出口，为了简单化，入口就是第二行的第一个口，出口是倒数第二行的第一个口。而且只有一个解，并且路径是连续的，有些游戏里面的迷宫是有传送点的，改变起来也很简单。

首先迷宫其实就是一棵树，每一个点都会有分支，任何一个叶子或者是节点都可以作为是一个入口，生成一个迷宫其实就是一个生成树的过程。之前在数据结构有提到过一个最小生成树，但是由于是一个随机的迷宫，所以应该是随机生成树。无论是什么树，都是基于树的。而图的遍历结果就是一颗树，每一个节点只是访问一次，且没有环，深度优先遍历的结果是一颗深度优先树，广度优先的结果是广度优先树。可以先把一张画布分成很多很多小格子，然后每隔一个格子就挖空一个点，没有挖空点的都是墙，用一种遍历方法来遍历这些点所生成的树就是一个迷宫了。但是这样的迷宫其实带有偏见的，随机性不高，所以可以在选择点的进行遍历的时候进行随机选择。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.12.24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据结构

登录后参与评论

0 条评论

热度