国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

用并查集(find-union)實(shí)現(xiàn)迷宮算法以及最短路徑求解

xiangchaobin / 2627人閱讀

摘要:本人郵箱歡迎轉(zhuǎn)載轉(zhuǎn)載請(qǐng)注明網(wǎng)址代碼已經(jīng)全部托管有需要的同學(xué)自行下載引言迷宮對(duì)于大家都不會(huì)陌生那么迷宮是怎么生成已經(jīng)迷宮要如何找到正確的路徑呢用代碼又怎么實(shí)現(xiàn)帶著這些問(wèn)題我們繼續(xù)往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現(xiàn)在有零

本人郵箱:
歡迎轉(zhuǎn)載,轉(zhuǎn)載請(qǐng)注明網(wǎng)址 http://blog.csdn.net/tianshi_kco
github: https://github.com/kco1989/kco
代碼已經(jīng)全部托管github有需要的同學(xué)自行下載

引言

迷宮對(duì)于大家都不會(huì)陌生.那么迷宮是怎么生成,已經(jīng)迷宮要如何找到正確的路徑呢?用java代碼又怎么實(shí)現(xiàn)?帶著這些問(wèn)題.我們繼續(xù)往下看.

并查集(find-union) 朋友圈

有一種算法就做并查集(find-union).什么意思呢?比如現(xiàn)在有零散的甲乙丙丁戊五個(gè)人.他們之間剛開(kāi)始互相不認(rèn)識(shí).用代碼解釋就是find(person1, person2) == false,之后在某一次聚合中,認(rèn)識(shí)了,認(rèn)識(shí)了,認(rèn)識(shí)了等等,那么就可以用代碼解釋如下.

    union("甲", "乙");
    union("乙", "丙");
    union("丙", "戊");
    union("丙", "丁");

那么這個(gè)時(shí)候就可以通過(guò)認(rèn)識(shí)到了在通過(guò)認(rèn)識(shí)到.
這是甲乙丙丁戊通過(guò)朋友或者朋友的朋友最終都互相認(rèn)識(shí).換另一種說(shuō)法就是如果要認(rèn)識(shí),那么必須先通過(guò)認(rèn)識(shí),再通過(guò)去認(rèn)識(shí)就行了.

迷宮

對(duì)于迷宮生成,其實(shí)更上面朋友圈有點(diǎn)類似.生成步驟如下

首先,先創(chuàng)建一個(gè)n*m的二維密室.每個(gè)單元格四方都是墻.

隨機(jī)選擇密室中的一個(gè)單元格.之后在隨機(jī)選擇一面要打通的墻壁.

判斷要打通的墻壁是否為邊界.是則返回步驟3,不是則繼續(xù)

判斷步驟的單元個(gè)和要打通的墻壁的對(duì)面是否聯(lián)通(用find算法)

如果兩個(gè)單元格不聯(lián)通,則把步驟2選中的墻壁打通(用union算法).否則返回步驟2.

判斷迷宮起點(diǎn)和終點(diǎn)是否已經(jīng)聯(lián)通,是則迷宮生成結(jié)束,否則返回步驟2.

對(duì)于并查集(find-union)的實(shí)現(xiàn),網(wǎng)絡(luò)上有不少實(shí)現(xiàn),這里不展開(kāi)說(shuō)明了.

實(shí)現(xiàn)代碼 墻壁
public enum Wall {
    /**
     * 墻壁
     */
    BLOCK,
    /**
     * 通道
     */
    ACCESS
}

墻壁,是一個(gè)枚舉變量,用于判斷當(dāng)前的墻壁是否可以通行.

單元格
public class Box {
    private Wall[] walls;

    public Box(){
        walls = new Wall[4];
        for (int i = 0; i < walls.length; i ++){
            walls[i] = Wall.BLOCK;
        }
    }

    public void set(Position position, Wall wall){
        walls[position.getIndex()] = wall;
    }

    public Wall get(Position position){
        return walls[position.getIndex()];
    }
}

一個(gè)單元格(小房間)是有四面墻組成的,剛開(kāi)始四面墻都是墻壁.

方向
public enum Position {
    TOP(0), RIGHT(1), DOWN(2), LEFT(3);

    public int index;

    Position(int index) {
        this.index = index;
    }

    public static Position indexOf(int index){
        int pos = index % Position.values().length;
        switch (pos){
            case 0:
                return TOP;
            case 1:
                return RIGHT;
            case 2:
                return DOWN;
            case 3:
            default:
                return LEFT;
        }
    }

    public Position anotherSide(){
        switch (this){
            case TOP:
                return DOWN;
            case RIGHT:
                return LEFT;
            case DOWN:
                return TOP;
            case LEFT:
            default:
                return RIGHT;
        }
    }

    public int getIndex() {
        return index;
    }
}

方向,枚舉類,用于判斷單元格的那一面墻壁需要打通.

迷宮生成類

這里我使用find-union的兩種實(shí)現(xiàn)方式實(shí)現(xiàn),

一種是用數(shù)組的方式MazeArrayBuilder

一種使用map的方式實(shí)現(xiàn)MazeMapBuilder
所以我把迷宮生成的一些共同方法和屬性抽取出現(xiàn),編寫了一個(gè)抽象類AbstractMazeBuilder.然后再在MazeArrayBuilderMazeMapBuilder做具體的實(shí)現(xiàn).

現(xiàn)在我們來(lái)看看AbstractMazeBuilder這個(gè)類

public abstract class AbstractMazeBuilder {
    /**
     * 迷宮行列最大值
     */
    public static final int MAX_ROW_LINE = 200;
    /**
     * 行
     */
    protected int row;
    /**
     * 列
     */
    protected int line;
    /**
     * 迷宮格子集合,每個(gè)格子有四面墻
     */
    protected Box[][] boxes;
    /**
     * 求解迷宮中間變量
     */
    protected int[][] solverPath;
    /**
     * 迷宮時(shí)候已經(jīng)算出最佳路徑
     */
    protected boolean isSolver;
    /**
     * 使用貪婪算法,算出最佳路徑集合
     */
    protected List bestPath;
    protected Random random;

    public AbstractMazeBuilder(int row, int line){
        if (row < 3 || row > MAX_ROW_LINE || line < 3 || line > MAX_ROW_LINE){
            throw new IllegalArgumentException("row/line 必須大于3,小于" + MAX_ROW_LINE);
        }
        this.row = row;
        this.line = line;

        isSolver = false;
        boxes = new Box[row][line];
        solverPath = new int[row][line];
        bestPath = new ArrayList();
        random = new Random();

        for (int i = 0; i < row; i ++){
            for (int j = 0; j < line; j ++){
                boxes[i][j] = new Box();
                solverPath[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    /**
     * 查詢與point點(diǎn)聯(lián)通的最大格子的值
     * @param point point
     * @return 查詢與point點(diǎn)聯(lián)通的最大格子的值
     */
    protected abstract int find(MazePoint point);

    /**
     * 聯(lián)通point1和point2點(diǎn)
     * @param point1 point1
     * @param point2 point2
     */
    protected abstract void union(MazePoint point1, MazePoint point2);

    /**
     * 判斷時(shí)候已經(jīng)生成迷宮路徑
     * @return 判斷時(shí)候已經(jīng)生成迷宮路徑
     */
    protected abstract boolean hasPath();

    /**
     * 生成迷宮
     */
    public void makeMaze(){

        while (hasPath()){
            // 生成 當(dāng)前點(diǎn), 當(dāng)前點(diǎn)聯(lián)通的方向, 當(dāng)前點(diǎn)聯(lián)通的方向?qū)?yīng)的點(diǎn)
            ThreeTuple tuple = findNextPoint();
            if (tuple == null){
                continue;
            }
            union(tuple.one, tuple.three);
            breakWall(tuple.one, tuple.two);
            breakWall(tuple.three, tuple.two.anotherSide());
        }
        breakWall(new MazePoint(0,0), Position.LEFT);
        breakWall(new MazePoint(row - 1, line - 1), Position.RIGHT);
    }

    /**
     * 生成 當(dāng)前點(diǎn), 當(dāng)前點(diǎn)聯(lián)通的方向, 當(dāng)前點(diǎn)聯(lián)通的方向?qū)?yīng)的點(diǎn)
     * @return
     * ThreeTuple.one 當(dāng)前點(diǎn)
     * ThreeTuple.two 當(dāng)前點(diǎn)聯(lián)通的方向
     * ThreeTuple.three 當(dāng)前點(diǎn)聯(lián)通的方向?qū)?yīng)的點(diǎn)
     */
    private ThreeTuple findNextPoint() {
        MazePoint currentPoint = new MazePoint(random.nextInt(row), random.nextInt(line));
        Position position = Position.indexOf(random.nextInt(Position.values().length));
        MazePoint nextPoint = findNext(currentPoint, position);
        if (nextPoint == null || find(currentPoint) == find(nextPoint)){
            return null;
        }
        return new ThreeTuple(currentPoint, position, nextPoint);
    }

    /**
     * 打通墻
     * @param point   當(dāng)前點(diǎn)
     * @param position 當(dāng)前點(diǎn)的方向
     */
    private void breakWall(MazePoint point, Position position) {
        boxes[point.x][point.y].set(position, Wall.ACCESS);
    }

    /**
     * 通過(guò)當(dāng)前點(diǎn)以及對(duì)應(yīng)當(dāng)前點(diǎn)的方向找到下一個(gè)點(diǎn)
     * @param currentPoint 當(dāng)前點(diǎn)
     * @param position 方向
     * @return 下個(gè)點(diǎn),若該點(diǎn)在迷宮內(nèi),這返回,否則返回null
     */
    private MazePoint findNext(MazePoint currentPoint, Position position) {
        MazePoint nextPoint;
        switch (position){
            case TOP:
                nextPoint = new MazePoint(currentPoint.x - 1, currentPoint.y);
                break;
            case RIGHT:
                nextPoint = new MazePoint(currentPoint.x, currentPoint.y + 1);
                break;
            case DOWN:
                nextPoint = new MazePoint(currentPoint.x + 1, currentPoint.y);
                break;
            case LEFT:
            default:
                nextPoint = new MazePoint(currentPoint.x, currentPoint.y - 1);
                break;
        }
        if (nextPoint.x < 0 || nextPoint.x >= row || nextPoint.y < 0 || nextPoint.y >= line){
            return null;
        }
        return nextPoint;
    }

    public Box getBoxes(int x, int y) {
        return boxes[x][y];
    }

    public int getRow() {
        return row;
    }

    public int getLine() {
        return line;
    }

    /**
     * 求解迷宮路徑
     * @return 迷宮路徑
     */
    public List solvePath(){
        // 1 迷宮時(shí)候已經(jīng)求解完成,是的話,則直接返回,不必再次計(jì)算
        if (isSolver){
            return bestPath;
        }
        // 2 否則計(jì)算迷宮最佳路徑
        bestPath = new ArrayList();
        solverPath(new MazePoint(0, 0), 0);
        addPath(new MazePoint(row - 1, line - 1));
        Collections.reverse(bestPath);
        isSolver = true;
        return bestPath;
    }

    /**
     * 從終點(diǎn)逆推,添加最佳路徑
     * @param point 當(dāng)前點(diǎn)
     */
    private void addPath(MazePoint point) {
        bestPath.add(point);
        // 遍歷當(dāng)前點(diǎn)的每個(gè)方向,如果該方向能聯(lián)通,這步數(shù)跟當(dāng)前點(diǎn)的步數(shù)相差1步,這添加改點(diǎn),遞歸計(jì)算下去
        for (Position position :Position.values()){
            MazePoint next = findNext(point, position);
            if (next == null || getBoxes(point.x, point.y).get(position) == Wall.BLOCK){
                continue;
            }
            if (solverPath[point.x][point.y] - 1 == solverPath[next.x][next.y]){
                addPath(next);
                return;
            }
        }
    }

    /**
     * 遞歸求解迷宮最佳路徑
     * @param point 當(dāng)前點(diǎn)
     * @param count 從開(kāi)始走到當(dāng)前點(diǎn)所需要的步數(shù)
     */
    private void solverPath(MazePoint point, int count) {
        // 判斷當(dāng)前點(diǎn)的步數(shù)時(shí)候小于現(xiàn)在走到這個(gè)點(diǎn)的步數(shù),
        // 如果當(dāng)前點(diǎn)的步數(shù)比較小,則直接返回
        if (solverPath[point.x][point.y] <= count){
            return;
        }
        // 否則表示當(dāng)前點(diǎn),有更短的路徑
        solverPath[point.x][point.y] = count;
        // 再遍歷當(dāng)前點(diǎn)的每個(gè)方向
        for (Position position : Position.values()){
            MazePoint next = findNext(point, position);
            // 如果下一個(gè)點(diǎn)不在迷宮內(nèi),或當(dāng)前點(diǎn)對(duì)應(yīng)的方向是一面墻壁,則跳過(guò)繼續(xù)編寫下一個(gè)方向
            if (next == null || getBoxes(point.x, point.y).get(position) == Wall.BLOCK){
                continue;
            }
            // 否則,步數(shù)加1, 遞歸計(jì)算
            solverPath(next, count + 1);
        }
    }

    public static class MazePoint{
        public final int x;
        public final int y;

        public MazePoint(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "MazePoint{" +
                    "x=" + x +
                    ", y=" + y +
                    "}";
        }
    }
}

代碼上有注釋,理解起來(lái)還是比較容易.MazeArrayBuilderMazeMapBuilder的實(shí)現(xiàn)就參考github了.

AbstractMazeBuilder 中還包括了迷宮的求解.

迷宮的求解

迷宮的求解,一般我會(huì)使用以下兩種方法

右手規(guī)則,從起點(diǎn)出發(fā),遇到墻壁,則向右手邊轉(zhuǎn),按照這個(gè)規(guī)則.一般是可以找到出口的.不過(guò)如果迷宮有閉環(huán),則無(wú)法求解,而且解出來(lái)的路徑也不是最短路徑.

迷宮最短路徑算法.

從起點(diǎn)出發(fā),計(jì)數(shù)count=0

遍歷該點(diǎn)的任意方向,如果是墻壁,則忽略,不然count++,進(jìn)入下一個(gè)聯(lián)通的格子

判斷當(dāng)前格子的的count(默認(rèn)值一般是比較大的數(shù))是否比傳入的參數(shù)大,是說(shuō)明該格子是一條捷徑,將當(dāng)前各自的count=入?yún)?繼續(xù)第2步;否則,說(shuō)明該點(diǎn)已經(jīng)被探索過(guò)且不是一條捷徑,忽略

如果反復(fù),暴力遍歷所有單元格,即可以求出最短路徑

遍歷完之后,從出口開(kāi)始找,此時(shí)出口的數(shù)字,表示從入口走到出口需要的最小步數(shù).依次減1,找到下一個(gè)格子,直到找打入口.則最短路徑就生成了.

附加運(yùn)行結(jié)果

打賞

如果覺(jué)得我的文章寫的還過(guò)得去的話,有錢就捧個(gè)錢場(chǎng),沒(méi)錢給我捧個(gè)人場(chǎng)(幫我點(diǎn)贊或推薦一下)

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/69918.html

相關(guān)文章

  • 用隊(duì)列求解迷宮短路及其應(yīng)用(圍住神經(jīng)貓)

    摘要:對(duì)應(yīng)迷宮數(shù)組為實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn)求解方塊類型方塊行號(hào)方塊列號(hào)上一個(gè)方塊在隊(duì)列中位置順序隊(duì)進(jìn)隊(duì)順時(shí)針迷宮路徑如下運(yùn)行結(jié)果應(yīng)用圍住神經(jīng)貓游戲使用寫的項(xiàng)目源碼下載體驗(yàn)最后附上我喜歡的歌的英文翻譯心做 問(wèn)題 給定一個(gè)M×N的迷宮圖,求一條從指定入口到出口的最短路徑.假設(shè)迷宮圖如圖所示(M=8, N=8) showImg(https://segmentfault.com/img/bVRjIk?w=26...

    Achilles 評(píng)論0 收藏0
  • [Leetcode] Graph Valid Tree 判斷一個(gè)圖是否為樹(shù)

    摘要:只有一個(gè)連通分量還沒(méi)有環(huán),就是樹(shù),無(wú)根樹(shù)。無(wú)向圖邊的兩端是對(duì)稱的,無(wú)向圖講究連通這個(gè)概念,沒(méi)有方向,沒(méi)有拓?fù)洌芟窦希苑浅_m合用并查集來(lái)解決。并查集寫法參考注意方法用找的老大哥,合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

    xbynet 評(píng)論0 收藏0
  • 王者編程大賽之五 — 短路

    摘要:由于是從頂點(diǎn)到的最短路徑,則有。算法流程根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì),提出了以最短路徑長(zhǎng)度遞增,逐次生成最短路徑的算法。相關(guān)文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環(huán) 首發(fā)于 樊浩柏科學(xué)院 自如年底就會(huì)擁有 50W 間房子,大家知道每間房房子都是需要配置完才能出租給自如客的,整個(gè)房租的配置過(guò)程是很復(fù)雜的,每天都需要大量的物流師傅將家電、家具...

    yuanzhanghu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<