专栏首页自学笔记Data Structure_Visualization概率模拟排序可视化走迷宫生成迷宫

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

概率模拟

随机模拟问题

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

https://www.jianshu.com/p/788ac5f312ff 使用这篇文章的模板作为可视化的模板,只需要填写逻辑就好了。

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

            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://www.jianshu.com/p/7fbf8671c742

选择排序很简单,遍历所有元素,查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的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;
    }

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

生成迷宫

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Data Structure_Visualization排序可视化走迷宫生成迷宫扫雷

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

    西红柿炒鸡蛋
  • Data Structure_Visualization

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

    西红柿炒鸡蛋
  • Data Structure_图图论带权图

    交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

    西红柿炒鸡蛋
  • 小根堆的Java实现

    堆是完全二叉树的数组形式,由于堆没有指针指向,所以可以利用下标来模拟指向,假设 i 为父节点,那么 2i+1 为左孩子,2i+2 为右孩子。假设 i 为当前节点...

    晚上没宵夜
  • 《一文说透数据结构》系列之什么是堆?看这一篇就够了

    本文将首先介绍什么是堆,然后介绍了堆的插入和删除操作,最后给出了堆的代码实现,并进行了测试。

    乔戈里
  • 计算机视觉 OpenCV Android | Mat像素操作

    下面演示对Mat对象中的每个像素点的值都进行取反操作,并且分别用这三种方法实现像素操作。

    凌川江雪
  • 浅谈我对动态规划的一点理解---大家准备好小板凳,我要开始吹牛皮了~~~

    前言 作为一个退役狗跟大家扯这些东西,感觉确实有点。。。但是,针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚,我决定还是拿出我的全部家当,来跟大家分...

    Angel_Kitty
  • Leetcode 132 Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a p...

    triplebee
  • 【自然框架】元数据的数据库结构的详细说明和示例(一):项目描述部分

    1、 Manage_Function(节点信息) 字段名 中文名 类型 大小 默认值 说明 FunctionID 节点ID int 4 1 主键 Pa...

    用户1174620
  • cf914D. Bash and a Tough Math Puzzle(线段树)

    可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

    attack

扫码关注云+社区

领取腾讯云代金券