主頁 > 軟體設計 > 淺談路徑搜索問題

淺談路徑搜索問題

2020-12-24 10:12:57 軟體設計

對簡單路徑問題的分析

問題：假設有這么一個二維陣列，1代表墻不可以通過，0代表通路可以通過，試問給出起點(1, 1)和終點(7,7)可不可以給出一條通路、最短通路、以及所有通路(假設每個點都可以找八個方向)，（這些問題有人可能叫迷宮問題等，但是我理解的迷宮你只能知道起點的坐標，不能知道終點，所以對于知道起點和終點的問題我更愿意叫做路徑搜索問題）

1 1 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1
1 1 0 0 0 0 0 0 1
1 0 1 0 0 1 1 1 1
1 0 1 1 1 0 0 1 1
1 1 0 0 1 0 0 0 1
1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1

分析：對于這個問題，我們可以聯想到有最基本的廣度優先策略和深度優先策略，

1.深度優先就是一條道走到底，走不去了就"回溯"(回溯的實作就是利用遞回的堆疊來實作,堆疊頂函式彈出堆疊，就可以達到回溯的目的)知道找到終點為止，
這個演算法就是遞回，用到了系統的函式堆疊，
2.廣度優先優先，就是從起點開始，假設你可以分身你可以從該點開始同時對這八個方向進行探索，然后對每個可以走的點繼續利用"分身"來對每個點
來進行上面所述的對八個方向同時進行探索知道找到終點為止，這個演算法主要用到了佇列，這時最先找到的就是最短的路徑，

對上述問題的解決

我們已經知道最短路徑的探索方法，那么一條普通的路徑就可以解決，那么對于探索上述迷宮的所有路徑，我們只需要利用一下深度優先的"回溯"原理就好，我們對于找到一條通路時，不要直接輸出路徑后就return程式，而應該和遇到障礙時一樣，來進行回溯，直到回溯完起點的八個為止為止，這個有點像求八皇后問題的回溯法一樣，

代碼實作

廣度優先求最短路徑

public class Point {             //首先定義了一個位置類， (x, y)代表坐標
    public final int x;
    public final int y;
    public Point(int x, int y){  //構造器，用于初始化位置 
        this.x = x;
        this.y = y;
    }
}


import java.util.Date;
import java.util.LinkedList;
import java.util.Scanner;

public class BfsShort {
    private final int[][] maze;          //定于一個二維陣列來表示迷宮
    private final Point s;        //定義了起始點
    private final Point e;       //定義了終點
    private Point[][] patTo;   //用于保存路徑                                     //定義了八個方向
    private final int[][] directory = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    private LinkedList<Point> stack = new LinkedList<>();  //沒有用雙向鏈表來模擬佇列(佇列的名字寫成了堆疊的英語單詞，忘記改了，手動狗頭)
    private BfsShort(int[][] maze, Point s, Point e){                       //構造器讀入地圖，起點和                      終點
        this.maze = maze;
        this.s = s;
        this.e = e;
        patTo = new Point[maze.length][maze[0].length];
        bfs();                             //呼叫了廣度優先函式
        print();                           //列印出最段路徑
    }
    private void bfs(){
        stack.addLast(this.s);                                                       //首先將起點加入佇列
        this.maze[s.x][s.y] = 2;                                                    //將走過的點標記為2，表示走 過了
        while (!stack.isEmpty()){                                      //當佇列為空時程式結束，此時沒有找到路徑，直接將用于patTo保存路徑的陣列賦值為null，列印出一行話"該路徑沒有路徑"
            Point p = stack.removeFirst();
            int x = p.x;
            int y = p.y;
            for (int i = 0; i < 8; i++) {            //開始分身，對八個方將進行探索
                int t = x + directory[i][0];        //下一個位置
                int v = y + directory[i][1];
                if (judge(t , v)){                   //判斷下一個位置是不是可以走，如果可以走judge函式回傳ture；
                    patTo[t][v] = p;             //將當前位置指向父位置，這樣便于最后列印出路徑
                     this.maze[t][v] = 2;    //將走過的路標記為2
                    stack.addLast(new Point(t, v));   //將該位置入佇列
                    if (t == this.e.x && v == this.e.y)          //當找到終點時，直接找到路徑程式結束，如果沒有找到終點繼續while回圈
                        return;
                }
            }
        }
        patTo = null;
        System.out.println("該迷宮沒有路徑");
    }
    private void print(){
        if (patTo == null)             //如果沒有找到路徑，直接結束程式，不列印
            return;
        Point temp = this.e;         //如果有路徑，則以終點為起始點開始，來繼續對路徑的列印
        while (temp.x != this.s.x || temp.y != this.s.y){   //直到找到起點回圈結束
            System.out.print("[" + temp.x + " " + temp.y + "]");
            temp = patTo[temp.x][temp.y];              //列印了temp位置后，然后找到它的父位置
        }
        System.out.println("[" + this.s.x + " " + this.s.y + "]");   //最后列印出起點位置
    }
    private boolean judge(int x, int y){
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length)   //如果越界，直接回傳false
            return false;
        if (maze[x][y] == 1 || maze[x][y] == 2)    //如果是障礙或者已經走過了直接回傳false
            return false;
        else return true;    //如果上述條件都不滿足，那么就可以走，回傳ture
    }
    public BfsShort(int[][] maze, int x, int y, int g, int h){           //對于用戶只提供該方法其他方法全部為私有方法，
        this(maze, new Point(x, y), new Point(g, h));
    }
}

上述代碼只對用于提供介面 public BfsShort(int[][] maze, int x, int y, int g, int h)，列印出該迷宮的最短路徑
測驗上述迷宮：

   public static void main(String[] args) {
        int[][] maze = new int[9][9];
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[0].length; j++)
                maze[i][j] = in.nextInt();
        BfsShort f = new BfsShort(maze, 1, 1, 7, 7);
    }

結果如下
在這里插入圖片描述

深度優先列印出所有路徑

這個代碼也會利用到上述的Point類,和上述代碼相同含義的遍歷已經判斷我就不在解釋第二遍了
具體的代碼實作

import java.util.LinkedList;
import java.util.Scanner;

public class DfsAll {
    //深度優先列印出迷宮所有可行的路徑
    private int count = 0;
    private int[][] maze;
    private final Point s;
    private final Point e;
    private LinkedList<Point> patTo = new LinkedList<>();  //利用鏈表，來儲存當前探索的路徑
    private final int[][] directory = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    private DfsAll(int[][] maze, Point s, Point e){
        this.maze = maze;
        this.s = s;
        this.e = e;
        dfs(this.s);           //呼叫深度優先列印列印出所有的路徑
    }
    private boolean judge(int x, int y){         
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length)
            return false;
        if (maze[x][y] == 1 || maze[x][y] == 2)
            return false;
        else return true;
    }
    private void dfs(Point s){
        this.patTo.addLast(s);              //將s加入路徑鏈表中
        if (maze[this.e.x][this.e.y] == 2)   //如果該點s為終點
            printPat();                               //列印出一條路徑
        else {                                          //如果不是的話，找到可以深入的點深入遞回下去
            int x = s.x;
            int y = s.y;
            for (int i = 0; i < 8; i++)
                if (judge(x + directory[i][0], y + directory[i][1])){    //如果該點可以走的話
                    this.maze[x + directory[i][0]][y + directory[i][1]] = 2;   //標記該點已經走過
                    dfs(new Point(x + directory[i][0], y + directory[i][1]));   //以該點為s繼續遞回
                }
        }
        this.patTo.removeLast();      
        this.maze[s.x][s.y] = 0;
       //以上兩行是重點： 當走不去了，或者該點已經是終點了，將該點從路徑陣列中除出，回到上一步的for回圈中，對其他剩下的方向進行探索，不過沒有路徑繼續向上回溯，如果有繼續向下走，該程式直達把其他的八個方向依次探索完為止，這里有點八皇后問題的味道，可以對比著看， 
         }
    private void printPat(){   //列印出一條路徑
        if (this.patTo.isEmpty())
            return;
        System.out.print(++count + ":");    //count用于記錄路徑的數量
        for (Point to : this.patTo)
            System.out.print("[" + to.x + " " + to.y + "]");
        System.out.println();
    }
    public DfsAll(int[][] maze, int x, int y, int g, int h){
        this(maze, new Point(x, y), new Point(g, h));
    }
}

測驗如下：

public static void main(String[] args) {
        int[][] maze = new int[9][9];
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[0].length; j++)
                maze[i][j] = in.nextInt();
        DfsAll f = new DfsAll(maze, 1, 1, 7, 7);
    }

在這里插入圖片描述
在這里插入圖片描述
上述代碼只給用于提供 public DfsAll(int[][] maze, int x, int y, int g, int h)函式介面，其他實作細節進行封裝，

對于上述問題，我們來繼續討論如果迷宮盡量大的話，如果求最短路還利用廣度優先顯然是不合適的，因為此時需要探索的點數太多，如果該迷宮的起點為maze[0][0],終點為maze[len-1][len-1]時，廣度優先這時需要對迷宮中的每個點進行探查，這顯然是不可以接受的(后面有有資料的對比)，

這時我們需要利用比較智能的A演算法來進行對最短路的探索了，這樣可以大大減少探索路徑所需要的時間，我們將走路的方式定義進行稍微的改變，上述演算法對于迷宮的八個方向探索的代價默認是等價的，這個演算法我們另對于上下左右四個方向的代價設定為10，那么可以根據數學知識可知其他四個方向為14(其實也可以不用這樣設定，也可以將八個方向的代價都設定為10，這樣就和上述演算法的八個方向的代價相同保持一致了，但是10，14這樣的代碼更符合實際，我們采用10， 14的表示法不管是那種定于在該定義下出來的結果都是正確的)，后面我們會對A和上述的廣度優先求最段路徑的時間進行對比，

A*演算法的原理

在這里插入圖片描述
假設綠色為我們的起始位置，紅色為終點，藍色為障礙物的話，該演算法也會對自己所處的八個方向進行計算如圖：
在這里插入圖片描述
對于可以走的路分別計算該點的代價，并將這些可以走的點放在一個容器中，每次找出代價最小的位置開始走，然后再以該點為中心對這八個方向的其他點進行計算代價，并加入到容器中，繼續找出代價最小的點作為下一個點，重復這一個回圈直到找出了一條路徑，或者該容器為空，此時就沒有路徑，
如圖：
在這里插入圖片描述
這樣就找出了路徑，這里重點解釋一下代價的概念：代價分為兩部分，一部分叫預估代價另外一部分叫做實際代價，兩者的加和就是總代價，這就是為啥我們要給每個方向設定代價的原因了，就算定義八個方向的代價是相同的也需要設定代價，原來是為了算總代價呀！
實際代價為：當前位置到起點所走的實際距離，例如上圖綠色起點的實際距離就為0，因為還沒有開始走，從他開始的第一個紅色點的實際代價就為0+14 = 14，下一個點的實際代價就為14 + 10 = 24；
這樣我們就可以知道下一個位置的實際距離就等于該點的父節點的實際距離加上從父節點到該節點的代價(10或者14)；
預估代價：就是當前節點到終點的距離，這個不能準確的計算出數值(如果可以計算出來，那么就已經知道最段路了，那么就不用A*跑迷宮了，哈哈哈，)
那么咋用求這個估計的代價呢？這里我們引入曼哈頓距離，
一般情況下計算預估代價的方法很多，我們這里就選擇曼哈頓距離來代表預估代價，
在這里插入圖片描述

如圖由于A到B的路徑有很多條，我們的曼哈頓距離就是紅色路徑，即兩點x方向的位移加上y方向上的位移，這下我們已經大致了解A*演算法的操作了，我們下面來進行代碼實作：

public class Position implements Comparable<Position> {
    public final int x;       //x方向的位置
    public final int y;      //y方向的位置
    public int g;      //實際代價
    public int f;       //總代價 f = g + p（預估代價）   我們這里沒有給預估代價分配變數，因為A*演算法只是比較總代價，而每一步的實際代價的計算依賴于上一步的實際代價，而預估代價沒有這個影響
    public Position(int x, int y){   //初始化位置
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Position o) { //我們重寫了Comparable介面中的compareTo方法來對總代價進行比較
        if (o == null)
            return -1;
        if (this.f > o.f)
            return 1;
        else return -1;
    }
    private int H(Position e){                 //曼哈頓距離的計算，這個e就是代表終點，他不依賴于上一步位置的預估代價
        return 10 * (Math.abs(this.x - e.x) + Math.abs(this.y - e.y));
    } 
    public int F(Position e){                 //實際代價和中代價相加即為總代價
        return this.g + this.H(e);
    }
}

以上就是對每一個位置資料型別的抽象，下面開始實作A*演算法


import java.util.*;
public class Aster {
    private  Position s;     //需要傳入起點
    private  Position e;    //需要傳入終點
    private int[][] maze;    //傳入地圖
    private Position[][] patTo; //該陣列用于對路徑的拼接
    private final int[][] directory = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    //定義了走迷宮的八個方向,從東開始
    PriorityQueue<Position> openList = new PriorityQueue<>();//對每個可以走的位置都使得進入優先佇列中，優先佇列每次呼叫remove函式時，都會洗掉并回傳總權值最小的位置(即他會按照compareTo方法的規則來進行比較)
    private Aster(int[][] maze, Position s, Position e){
        patTo = new Position[maze.length][maze[0].length];
        this.maze = maze;
        this.s = s;
        this.e = e;    //以上為初始化地圖，起點和終點
        trlMaze(maze, this.s, this.e);   //呼叫實作好的A*演算法
        printPatTo(s, e);                     //列印出路徑
    }
    private void printPatTo(Position s, Position e){
        if (patTo == null)
            return;
        Position temp = e;
        while (s.x != temp.x || s.y != temp.y){
            System.out.print("[" + temp.x + " " + temp.y + "]");
            temp = patTo[temp.x][temp.y];
        }
        System.out.println("[" + s.x + " " + s.y + "]");
    }
    private void trlMaze(int[][] maze, Position s, Position e){   //A*演算法的具體實作
        s.g = 0;           //將起點的實際代價設定為0
        s.f = s.F(e);   //呼叫函式計算起點的預估代價
        openList.add(s);  //將這個點加入到優先佇列的容器中
        while (!openList.isEmpty()){     //如果該優先佇列為空了，就退出該回圈這表明該迷宮沒有路徑
            Position p = openList.remove();// 從優先佇列中remove出權值最小的點
            maze[p.x][p.y] = 2；             //將他標記為2代表已經走過了
            add(p);                                  //以該點為父節點，對于八個方向進行探索，計算總代價并加入到優先佇列中去
            if (p.x == e.x && p.y == e.y)   //如果找到了終點，程式直接結束，如果不是的話繼續該回圈
                return;
        }
        patTo = null;           //如果沒有路徑將用于路徑拼接的陣列設定為空
        System.out.println("沒有路徑");  //列印出一句話沒有路徑
    }
    private boolean judge(int x, int y){       //判斷該點是不是可以走的點
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length)  //如果越界不可以走
            return false;
        if (maze[x][y] == 1)               //如果是障礙物不可以走
            return false;
        if (maze[x][y] == 2)              //已經走過了不可以走
            return false;
        return true;                        //以上條件都不滿足則可以走，回傳ture
    }
    private void add(Position father){    //A*演算法的輔助函式，就是上述的對以father為中心的八個節點來分別探索
        int x = father.x;
        int y = father.y;
        add(father, x + directory[0][0], y + directory[0][1], 10);  //然后用下面的add函式對該點繼續判斷，如果滿足條件加入到優先佇列中去，以下八個函式的呼叫就是從東開始順時針的方向
        add(father, x + directory[1][0], y + directory[1][1], 14);
        add(father, x + directory[2][0], y + directory[2][1], 10);
        add(father, x + directory[3][0], y + directory[3][1], 14);
        add(father, x + directory[4][0], y + directory[4][1], 10);
        add(father, x + directory[5][0], y + directory[5][1], 14);
        add(father, x + directory[6][0], y + directory[6][1], 10);
        add(father, x + directory[7][0], y + directory[7][1], 14);
    }
    private void add(Position father, int x, int y, int val){             //上述add函式的輔助函式
        if (judge(x, y)) {    //判斷該點是不是可以走
            this.maze[x][y] = 2;   //如果可以走，將他加入到優先佇列中，并標記為2
            Position p = new Position(x, y);    //見它實體化為物件
            p.g = father.g + val;                    //計算實際代價
            p.f = p.F(this.e);                        //計算總代價
            this.patTo[x][y] = father;            //這一步很重要，類似于廣度優先的路徑拼接，用子位置指向父位置，用于最后的路徑列印，不能用一個容器來直接存放走過的點，最后直接遍歷輸出這個陣列，這樣是錯誤的，等下會詳細說明
            openList.add(p);   將該點加入優先佇列中去
        }
    }
    public Aster(int[][] maze, int x, int y, int g, int h){              //以上實作細節都對用戶進行隱藏，只提供這個構造方法對用戶使用
        this(maze, new Position(x, y), new Position(g, h));
    }
}

測驗該演算法的正確性(還是以上圖的迷宮為例)
測驗代碼

 public static void main(String[] args) {
        int[][] maze = new int[9][9];
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[0].length; j++)
                maze[i][j] = in.nextInt();
        Aster f = new Aster(maze, 1, 1, 7, 7);
    }

在這里插入圖片描述
這個演算法可以在很快的速度內解決最短路徑，我來給大家測驗一下，我們會用亂數來生成0,1組成的二維陣列來進行測驗，規格分別是100乘100， 1000乘1000，5000乘5000以及10000乘10000的陣列來進行測驗，測驗結果如下

迷宮規格A*時間廣度時間
100 * 10028毫秒28毫秒
100 * 10027毫秒31毫秒
100 *10025毫秒27毫秒
1000*100052毫秒131毫秒
1000*100051毫秒130毫秒
1000*100049毫秒120毫秒
5000*5000149毫秒2469毫秒
5000*5000188毫秒2521毫秒
5000*5000165毫秒2461毫秒
10000*10000313毫秒14397毫秒
10000*10000239毫秒14036毫秒
10000*10000286毫秒14001毫秒

在這里插入圖片描述

這些資料都是本人測驗所得沒有虛構，由于后來的迷宮越來越大所以我全部是隨機生成的方式進行構造代碼的，由于是隨機的一部分都是沒有回路的，這些是反復運行后可以走通的迷宮的實驗資料，
測驗代碼如下：

import Astar.Aster;
import BFS.BfsShort;
import DFS.DfsAll;

import java.util.Date;
//A*演算法與廣度優先求最短路時間的對比  100*100 / 1000*1000 / 5000*5000 / 10000*10000
public class test1 {
    public static void main(String[] args) {
        int[][] maze = new int[10000][10000];
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[0].length; j++)
                maze[i][j] = (int)(Math.random() * 2);
            maze[0][0] = 0;
            maze[maze.length-1][maze[0].length-1] = 0;
        Date date1 = new Date();
       // Aster f = new Aster(maze, 0, 0, maze.length-1, maze[0].length-1);
        BfsShort f = new BfsShort(maze, 0, 0, maze.length-1, maze[0].length-1);
        Date date2 = new Date();
        System.out.println(date2.getTime() - date1.getTime() + "毫秒");
    }
}

從上面這些測驗代碼來看，可知我把入口設定為00點而終點就是該迷宮的最大橫坐標和縱坐標的位置，這樣我們就可以分析出上述表格資料的原因了，
對廣度優先演算法的分析：由于我上面已經講了廣度優先策略的原理了，那么我們就可以知道這樣設定起點和終點的話，如果迷宮有通路的話，該演算法一定回遍歷這個整張圖，所以對于大小相同的迷宮來說，只要有通路時間都是大致相同的，有上面的分析，可以輕易的分析出迷宮沒有出口的情況，如果最開始迷宮就探索到了死路時，這時候佇列元素不多很快就會佇列空從而結束程式列印出沒有找到路徑，這時需要的時間會很少，但是當探索快到了終點是這是突然是個死路是，那么沒有路徑這時的時間就會和遍歷整張圖的時間幾乎是一樣的(下面會進行代碼驗證)
對A演算法的分析：我們可以看出當迷宮較大時，這時如果有通路，這時A演算法的時間相較于廣度優先時間上會有較大的波動，這是為什么呢？
看下面這個簡單的迷宮

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 0 0 1 0
1 1 1 1 1 1 1

對于該迷宮A假設起點為(2, 0)終點為(2, 6)時，這時A演算法就回先走入死胡同，
實際路徑為:
[2 1][1 0][0 1][0 2][0 3][0 4][0 5][1 6][2 6]
但是實際上A演算法從[1 0]點開始探索到終點的實際探索順序為：
[2 1][2 2][2 3][2 4][2 0][1 0][0 1][0 2][0 3][0 4][0 5][1 6][2 6]
這是為什么呢？原因在于這個估價函式的問題從[2 1]開始他并不會走到[1 0]這個點因為對他來說這個總價值不是最小的，他會走到[2 2][2 3][2 4]這些才是代價最小的位置，但是這樣走進了死胡同！！！這是從優先佇列里面再找出代價最小的就是[2 0]這個位置了，然后依次最小的就是[1 0][0 1][0 2][0 3][0 4][0 5][1 6][2 6]這樣就找到了路徑，但是這個迷宮這個估價函式的導航第一次會進行失效走進死胡同，這也是為什么要用子位置指向父位置來進行路徑的輸出的原因了，顯然探索過的路徑[2 1][2 2][2 3][2 4][2 0][1 0][0 1][0 2][0 3][0 4][0 5][1 6][2 6]并不是真正的路徑，一部分是不會包含在真實的路徑上的，這些就是A演算法不穩定的原因了，當這種導航失靈的情況多的時候A演算法需要探索和走的位置就會變多，這時就會導致A演算法的變慢，
這個是對有通路時A演算法為何不穩定的一個分析，
下面還有一個有趣的點，就是A演算法可能會比廣度優先還慢！！！
這個是為什么呢？我們知道A演算法找不到路徑的話就是當優先佇列為空時，那么我們可以構造一個比較極端的情況(其實在構造隨機迷宮時，如果沒有路徑的話，A演算法有比較大的可能比廣度優先慢)，這是A演算法優先佇列為空的條件就是遍歷整張地圖，這時他的遍歷次數就和廣度優先的遍歷次數相同，又因為他的計算估計函式和出入優先佇列這就導致了A演算法每一步所要花費的時間比廣度優先所花費的時間要多，所以當A*遍歷整張地圖時，這時他所花費的時間肯定是要大于廣度優先的時間的，我們可以用代碼驗證以下：

00000000
00000000
00000000
00000011
00000010

類似于這樣的迷宮全迷宮基本上都是可以走的，但是只要三個位置為1這個是不可以走的，令[0 0 ]為入口，被一包圍的點為終點，這時可知該迷宮一點沒有路徑，但是這時廣度優先和A探索出這個迷宮沒有路徑的條件分別是佇列空和優先佇列空，這時都是遍歷整個地圖！！！
這時A就會比廣度優先慢！！！
測驗代碼如下：(我們把這個迷宮構造為10000 * 10000)
有圖有真相
在這里插入圖片描述
在這里插入圖片描述
和我們的猜測是相同的！！！A這時就會比廣度優先慢！！！
這一些知識解決了簡單的迷宮問題，那么對于多權值迷宮呢？
(下面就不會比A這么詳細了，我能力不太行手動狗頭)

對于多權值迷宮的探究

問題描述：
對于該迷宮

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  2  1  1  1  1  1  5  1 -1
-1  1  9  9  9  1  1 -1  1 -1
-1  1  1  1  1  1  1 -1  1 -1
-1  1 -1 -1 -1 -1 -1 -1  1 -1
-1  1  9  9  9  1  1  1  1 -1
-1  1  1  1  1  1  1  1  1 -1
-1  1  1  1  1  1  1  1  1 -1
-1  1  1  1  1  1  1  1  2 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

-1代表墻其他陣列代表權值，這個問題該咋樣做呢？
我當初是想利用對該迷宮進行建圖，來運用迪杰斯特拉演算法來進行對最段路徑的求解，但是我感覺建圖太慢了，
這是我們可以把這個迷宮的每個非-1的點都看作一個頂點，而每個頂點最多可以連到8條邊(因為可以探索八個方向)，我們從起點開始探索周圍的八條邊，對真實的點進行邊的松弛技術然后將這些松弛的邊加入到優先佇列中，然后找出距離最小的邊繼續進行松弛，知道優先佇列為空為止，
代碼如下：

public class Point implements Comparable<Point>{
    public int x;
    public int y;
    public int distTo = Integer.MAX_VALUE;   //該頂點到起點的距離
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + this.x + " " + this.y + "]";
    }

    @Override
    public int compareTo(Point o) {   //對于頂點o到起點的距離進行排序 
    if (o == null)
            return -1;
        if (this.distTo > o.distTo)
            return 1;
        return -1;
    }
}


public class Dijkstra {
    private int[][] maze;             //地圖
    private final Point s;           //起點
    private int[][] distTo;          //該點到起點的距離
    private Point[][] pointTo;  //用于路徑的拼接
    private PriorityQueue<Point> pq = new PriorityQueue<Point>(); //優先佇列
    private final int[][] directory = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}}; //八個方向
    private Dijkstra(int[][] maze, Point s){
        this.maze = maze;
        this.s = s;
        this.distTo = new int[maze.length][maze[0].length];    
        this.pointTo = new Point[maze.length][maze[0].length];
        for (int i = 0; i < distTo.length; i++)
            for (int j = 0; j < distTo[0].length; j++)
                distTo[i][j] = Integer.MAX_VALUE;    //初始化為最大值
        distTo[s.x][s.y] = 0;                                 //起點到他自己的距離為0
        s.distTo = 0;                                           // 起點到他自己的距離為0
        pq.add(s);                                             //添加到優先佇列中
        while (!pq.isEmpty())                            //優先佇列為空程式結束
            relax(pq.remove());                        //對距離最小的進行邊的放松技術
    }
    private void relax(Point p){              //邊的松弛技術
        for(int i = 0; i < 8; i++){
            int w = p.x + directory[i][0];
            int v = p.y + directory[i][1];
            if (judge(w, v))
                if (distTo[w][v] > p.distTo + maze[w][v]){
                    distTo[w][v] = p.distTo + maze[w][v];
                    pointTo[w][v] = p;
                    Point np = new Point(w, v);
                    np.distTo = p.distTo + maze[w][v];
                    pq.add(np);
                }
        }
    }
    private boolean judge(int x, int y){
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length)
            return false;
        if (maze[x][y] == -1)
            return false;
        return true;
    }
    private void printRoute(Point p){   //對路徑進行輸出  
            if (!hasPathTo(p)){
            System.out.println("該回路沒有路徑");
            return;
        }
        Point temp = p;
        while (temp.x != this.s.x || temp.y != this.s.y){
            System.out.print(temp);
            temp = pointTo[temp.x][temp.y];
        }
        System.out.println(this.s);
    }
    private boolean hasPathTo(Point p){    //判斷該點到起點是不是有路徑
        return distTo[p.x][p.y] != Integer.MAX_VALUE;
    }
    private int distTo(Point p){ return distTo[p.x][p.y]; } //判斷起點到終點的距離
//以上實作對用戶隱藏只保留以下介面供用戶使用
    public Dijkstra(int[][] maze, int x, int y){          
        this(maze, new Point(x, y));
    }
    public int distTo(int x, int y){
        return distTo(new Point(x, y));
    }
    public boolean hasPathTo(int x, int y){
        return hasPathTo(new Point(x, y));
    }
    public void printRoute(int x, int y){
        printRoute(new Point(x, y));
    }
}

需要注意的是，只需要對該程式提供迷宮和起點，他會生成以起點為根的最短路徑樹，對其他點的查詢的時間復雜度都為O(1)， 建立最短路徑樹的時間復雜度為O（nlongn）.
下面對以上的迷宮進行測驗


import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        int[][] maze = new int[10][10];
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[0].length; j++)
                maze[i][j] = in.nextInt();
    Dijkstra f = new Dijkstra(maze, 3, 6);
        while (true){
            System.out.println("請輸入需要查找的位置");
            int x = in.nextInt();
            int y = in.nextInt();
            f.printRoute(x, y);
       }
    }
}

結果如下：
在這里插入圖片描述
我們可以測驗以下比較大的迷宮(10000*10000)
測驗代碼如下

import java.util.Date;
import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        int[][] maze = new int[10000][10000];
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[0].length; j++)
                maze[i][j] = (int)(Math.random() * 11) -1;
        Date date = new Date();
    Dijkstra f = new Dijkstra(maze, 3, 6);
        Date date1 = new Date();
        System.out.print("所需時間為  ");
        System.out.println(date1.getTime() -date.getTime());
        while (true){
            System.out.println("請輸入需要查找的位置");
            int x = in.nextInt();
            int y = in.nextInt();
            f.printRoute(x, y);
       }
    }
}

在這里插入圖片描述
迪杰斯特拉演算法可以解決這種加權又向有環圖的演算法，他的時間復雜度是ElogV，但是他的不可以處理負權值，
下面來說一種可以處理負權值的演算法，但是它不能有環，這個是目前最快的最短路演算法，時間復雜度中有O（E+V），
它的步驟就是對圖進行拓撲排序，然后按照拓撲排序的順序來進行邊的放松即可，我們可以將代碼進行小小的改變就可以變成最長路徑的求解，
代碼如下：

public class DirectedEdge {   //有向邊的資料結構
    private int v;                       //有向邊的起點
    private int w;                      //有向邊的終點
    private double weight;        //權值
    public DirectedEdge(int v, int w, double weight){   //初始化邊
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    public int form(){             //回傳起點
        return this.v;
    }
    public int to(){              //反正終點
        return this.w;
    }
    public double getWeight(){  //回傳權值
        return this.weight;
    }
}



public class EdgeWeightedDigraph {  //又向圖的資料結構
    private final int V;                      //頂點數
    private int E;                            //邊數
    private ArrayList<DirectedEdge>[] adj;   //鄰接表
    public EdgeWeightedDigraph(int V){    //初始化
        this.V = V;
        adj = (ArrayList<DirectedEdge>[]) new ArrayList[V];
        for (int i = 0; i < adj.length; i++)
            adj[i] = new ArrayList<>();
    }
    private void add(DirectedEdge e){    //添加邊
        this.adj[e.form()].add(e);
        this.E++;
    }
    public int getV(){                    //回傳頂點
        return this.V;
    }
    public int getE(){               //回傳邊
        return this.E;
    }
    public Iterable<DirectedEdge> edges(int v){   //回傳出以v為起點的所有邊的迭代器
        return adj[v];
    }
    public Iterable<DirectedEdge> edgeAll(){     //回傳全部邊的迭代器
        ArrayList<DirectedEdge> p = new ArrayList<>();
        for (int i = 0; i < this.V; i++)
            for (DirectedEdge e : this.edges(i))
                p.add(e);
        return p;
    }
    public void add(int form, int to, double weight){       //添加邊的函式
        this.add(new DirectedEdge(form, to, weight));
    }


public class DirectedCycle {        //用于找該圖是不是有環
    private boolean[] marked;       //用于標記訪問過的點
    private int[] edgTo;                  //用于拼接可能出現環上的點
    private LinkedList<Integer> stack;   //如果stack == null則沒有環，反正則有
    private boolean[] isStack;            //用于標記該頂點是不是還在本次遞回中，如果在就標記為ture負責標記為false
    public DirectedCycle(EdgeWeightedDigraph G){
        marked = new boolean[G.getV()];
        edgTo = new int[G.getV()];
        isStack = new boolean[G.getV()];
        for (int i = 0; i < G.getV(); i++)
            if (!marked[i])
                dfs(G, i);
    }
    private void dfs(EdgeWeightedDigraph G, int v){  //基于深度優先找有向圖的環
        this.isStack[v] = true;                                      // 節點v在本次遞回中，將它標記為ture
        this.marked[v] = true;                                     //訪問了該點將它標記為ture
        if (this.stack != null)                                      //如果找到了環就結束程式，如果沒有就繼續找
            return;
        for (DirectedEdge e : G.edges(v)) {    //開始找到符合條件的點
            if (!this.marked[e.to()]){                   //如果該點沒有被訪問就從它開始遞回
                edgTo[e.to()] = v;
                dfs(G, e.to());
            }
            else if (this.isStack[e.to()]){       //如果該點已經訪問了，而且它還在本次遞回中，那么就找到了環
                stack = new LinkedList<>();    //那么就給他賦值
                for (int i = v; i != e.to(); i = edgTo[i])
                    stack.addFirst(i);              //然后拼接環上的點
                stack.addFirst(e.to());         
            }
        }
        this.isStack[v] = false;                //v點已經退出了堆疊，將它標記為false
    }
    public boolean hasCycle(){           //如果有環回傳ture如果沒有回傳false
        return this.stack != null;
    }
    public Iterable<Integer> cycle(){   //回傳環上點的迭代器
        return this.stack;
    }
}



import java.util.LinkedList;          

public class Topological {           //拓撲排序，如果該圖有環直接結束程式，不能進行拓撲排序， 如果沒有環就深度遍歷一遍圖，它遍歷的逆后序就是它的拓撲排序結果
    private boolean[] marked;
    private LinkedList<Integer> reversePost;
    public Topological(EdgeWeightedDigraph G){
        DirectedCycle f = new DirectedCycle(G);
        if (f.hasCycle())
            return;
        marked = new boolean[G.getV()];
        reversePost = new LinkedList<>();
        for (int i = 0; i < G.getV(); i++)
            if (!this.marked[i])
                dfs(G, i);
    }
    private void dfs(EdgeWeightedDigraph G, int v){   深度優先
        this.marked[v] = true;
        for (DirectedEdge e : G.edges(v))
            if (!marked[e.to()])
                dfs(G, e.to());
        reversePost.addFirst(v);                //收集它頂點的逆后序，即為拓撲排序
    }
    public boolean hasTopological(){    //該圖能不能進行拓撲排序，不能回傳false能回傳ture 
            return this.reversePost != null;
    }
    public Iterable<Integer> order(){    //回傳拓撲排序的迭代器
        return this.reversePost;
    }
}



public class AcyclicSP {     //如果它沒有環，就根據它的拓撲排序進行邊的松弛
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private EdgeWeightedDigraph G;
    private int s;
    public AcyclicSP(EdgeWeightedDigraph G, int s){
        Topological f = new Topological(G);
        if (!f.hasTopological())    //不能進行拓撲排序，直接拋出例外，程式結束
            throw new RuntimeException("有向環例外");
        this.s = s;
        this.G = G;
        edgeTo = new DirectedEdge[G.getV() * 2];
        distTo = new double[G.getV()];
        for (int i = 0; i < distTo.length; i++)
            distTo[i] = Double.POSITIVE_INFINITY;                   //最短路徑
           //   distTo[i] = Double.NEGATIVE_INFINITY;                  //最長路徑
        distTo[s] = 0.0;
        for (Integer i : f.order())           //有拓撲排序直接根據它的拓撲排序進行邊的松弛操作     
            relax(this.G, i);
    }
    private void relax(EdgeWeightedDigraph G, int v){   //邊的松弛操作
            for (DirectedEdge e : G.edges(v))
            if (distTo[e.to()] > distTo[e.form()] + e.getWeight()){         //最短路徑
          // if (distTo[e.to()] < distTo[e.form()] + e.getWeight()){           //最長路徑
                distTo[e.to()] = distTo[e.form()] + e.getWeight();
                edgeTo[e.to()] = e;
            }
    }
    public double dist(int to){            //回傳起點到to的距離
        return this.distTo[to];
    }
    public boolean hasRoute(int to){   //判斷是不是有路徑
        return this.distTo[to] != Double.POSITIVE_INFINITY;
    }
    public void printRoute(int to){     //回傳起點到to的路徑
        if (distTo[to] == Double.POSITIVE_INFINITY)
            return;
        for (DirectedEdge e = edgeTo[to]; e != null; e = edgeTo[e.form()])
            System.out.print(e.to() + " <- ");
        System.out.println(this.s);
    }
}

這個代碼可以將最短路改為最長路徑，只需要改變兩處即可，上面我已經進行注釋了，
測驗：
給出一個測驗案例

V = 8
E = 13
5 4 0.35
4 7 0.37
5 7 0.28
5 1 0.32
4 0 0.38
0 2 0.26
3 7 0.39
1 3 0.29
7 2 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

 //對有向加權無環圖的最快演算法(權值可以為負值)
    public static void main(String[] args) {
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(8);
        G.add(5, 4, 0.35);
        G.add(4, 7, 0.37);
        G.add(5, 7, 0.28);
        G.add(5, 1, 0.32);
        G.add(4, 0, 0.38);
        G.add(0, 2, 0.26);
        G.add(3, 7, 0.39);
        G.add(1, 3, 0.29);
        G.add(7, 2, 0.34);
        G.add(6, 2, 0.40);
        G.add(3, 6, 0.52);
        G.add(6, 0, 0.58);
        G.add(6, 4, 0.93);
        Scanner in = new Scanner(System.in);
        AcyclicSP f = new AcyclicSP(G, 5);
        while (true){
            System.out.println("請輸入需要查詢的終點");
            f.printRoute(in.nextInt());
        }
    }

在這里插入圖片描述

如果向這個測驗代碼中加入2 ->3這條邊就會出現有向環例外
在這里插入圖片描述

本來也想讓這個最快的最短路演算法O（E+V）和迪杰斯特拉演算法（O（ElogV））來對相同的圖進行速度上的比較讓大家直觀的看下速度的差距，就和上述的表格一樣，但是該演算法只能用于有向圖，但是用亂數夠造的話，圖大的話必然就可能是有環圖，沒有辦法進行比較，但是我可以給大家
找出一個案例讓大家看看這個演算法的用處，
上面我們說過這個演算法只需要改一下就可以求出最長路徑，那么這個就可以解決任務的并行問題，
問題描述：給定一組任務的優先級和每項任務所需要的時間，在滿足優先級的情況下，應該在若干處理器上(數量不限)安排任務的并行在最短的時間內完成任務？
例如

任務時耗必須在以下任務之前完成
041.01 7 9
151.02
250.0
336.0
438.0
545.0
621.03 8
732.03 8
832.02
929.04 6

對于這個問題我們只需要建立如下的圖，并求出他的最長路徑即可，起點s到終點t的最長路徑就是完成所有任務的總時間，而起點s到任務x的起點的最長路徑就是這項任務x開始的時間
在這里插入圖片描述

輸入資料

10
41.0 1 7 9
51.0 2
50.0
36.0
38.0
45.0
21.0 3 8
32.0 3 8
32.0 2
29.0 4 6

代碼實作（需要把上述最短路的代碼改成最長路徑）

package AcyclicSP;

import java.util.Scanner;

public class CPM {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Scanner inl = new Scanner(System.in);
        int n = in.nextInt();
        EdgeWeightedDigraph G  = new EdgeWeightedDigraph(2 * (n + 1));
        String s;
        int S = 2 * n;
        int E = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            s = inl.nextLine();
            String[] ss = s.split(" ");
            double time = Double.parseDouble(ss[0]);
            G.add(S, i, 0.0);
            G.add(i, i+n, time);
            G.add(i+n, E, 0.0);
            for (int j = 1; j < ss.length; j++){
                int next = Integer.parseInt(ss[j]);
                G.add(i+n, next, 0.0);
            }
        }
        AcyclicSP f = new AcyclicSP(G, S);
        for (int i = 0; i < n; i++)
            System.out.println(i + ":  " + f.dist(i));
        System.out.println(f.dist(E));
    }
}

在這里插入圖片描述

從輸出結果可知這些任務最快需要173才能完成，上面分別是各個任務開始作業的時間點
下面就是最后一個路徑問題了就是對于加權有向有環圖(可以包含負權值)這類問題咋樣求最短路徑問題，
這里我給你一種演算法spfa演算法
代碼如下


import java.util.LinkedList;

public class SPFA {
    private boolean[] marked;
    private double[] distTo;
    private int[] count;
    private DirectedEdge[] edgeTo;
    private int s;
    private LinkedList<Integer> queue = new LinkedList<>();
    public SPFA(EdgeWeightedDigraph G, int s) {
        this.s = s;
        this.marked = new boolean[G.getV()];
        this.distTo = new double[G.getV()];
        this.count = new int[G.getV()];
        this.edgeTo = new DirectedEdge[G.getV() * 2];
        for (int i = 0; i < this.distTo.length; i++)
            this.distTo[i] = Double.POSITIVE_INFINITY;
        this.distTo[s] = 0.0;
        this.queue.addLast(s);
        this.count[s]++;
        this.marked[s] = true;
        while (!queue.isEmpty()) {
            int w = this.queue.removeFirst();
            this.marked[w] = false;
            for (DirectedEdge e : G.edges(w)) {
                if (this.distTo[e.to()] > this.distTo[e.form()] + e.getWeight()) {
                    this.distTo[e.to()] = this.distTo[e.form()] + e.getWeight();
                    this.edgeTo[e.to()] = e;
                    if (!this.marked[e.to()]) {
                        this.queue.addLast(e.to());
                        this.count[e.to()]++;
                        if (this.count[e.to()] > G.getV()){
                            throw new RuntimeException("該圖有負環不能判斷");
                        }
                        this.marked[e.to()] = true;
                    }
                }
            }
        }
    }
    public void printRoute(int to){
        for (DirectedEdge e = edgeTo[to]; e != null; e = edgeTo[e.form()])
            System.out.print(e.to() + " <- ");
        System.out.println(this.s);
    }
}

改代碼允許有負權值的邊，但是不允許有帶有負權值的環，如果發下直接拋出例外，這一段代碼我就不解釋了，好奇的同學可以自己查資料，上面代碼用于參考，

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/239548.html

標籤：其他

上一篇：uniapp+nodejs實作小程式登錄流程，獲取openID,附uniapp請求封裝

下一篇：Sum of Log(icpc上海站2020) 數位dp

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 面試突擊第一季，第二季，第三季

    第一季必考 https://www.bilibili.com/video/BV1FE411y79Y?from=search&seid=15921726601957489746 第二季分布式 https://www.bilibili.com/video/BV13f4y127ee/?spm_id_fro ......

    uj5u.com 2020-09-10 05:35:24 more
  • 第三單元作業總結

    1.前言 這應該是本學期最后一次寫作業總結了吧。總體來說，對作業的節奏也差不多掌握了，作業做起來的效率也更高了。雖然和之前的作業一樣，作業中都要用到新的知識，但是相比之前，更加懂得了如何利用工具以及資料。雖然之間卡過殼，但總體而言，這幾次作業還算完成的比較好。 2.作業程序總結 相比前兩個單元，此單 ......

    uj5u.com 2020-09-10 05:35:41 more
  • 北航OO（2020）第四單元博客作業暨課程總結博客

    北航OO（2020）第四單元博客作業暨課程總結博客 本單元作業的架構設計 在本單元中，由于UML圖具有比較清晰的樹形結構，因此我對其中需要進行查詢操作的元素進行了包裝，在樹的父節點中存盤所有孩子的參考。考慮到性能問題，我采用了快取機制，一次查詢后盡可能快取已經遍歷過的資訊，以減少遍歷次數。 本單元我 ......

    uj5u.com 2020-09-10 05:35:48 more
  • BUAA_OO_第四單元

    一、UML決議器設計 ? 先看下題目：第四單元實作一個基于JDK 8帶有效性檢查的UML(Unified Modeling Language)類圖，順序圖，狀態圖分析器 MyUmlInteraction，實際上我們要建立一個有向圖模型，UML中的物件（元素）可能與同級元素連接，也可與低級元素相連形成 ......

    uj5u.com 2020-09-10 05:35:54 more
  • 6.1邏輯運算子

    邏輯運算子 1. && 短路與 運算式1 && 運算式2 01.運算式1為true并且運算式2也為true 整體回傳為true 02.運算式1為false，將不會執行運算式2 整體回傳為false 03.只要有一個運算式為false 整體回傳為false 2. || 短路或 運算式1 || 運算式2 ......

    uj5u.com 2020-09-10 05:35:56 more
  • BUAAOO 第四單元 & 課程總結

    1. 第四單元：StarUml檔案決議 本單元采用了圖模型決議UML。 UML檔案可以抽象為圖、子圖、邊的邏輯結構。 在實作中，圖的節點包括類、介面、屬性，子圖包括狀態圖、順序圖等。 采用了三次遍歷UML元素的方法建圖，第一遍遍歷建點，第二、三次遍歷設定屬性、連邊，實作圖物件的初始化。這里借鑒了一些 ......

    uj5u.com 2020-09-10 05:36:06 more
  • 談談我對C# 多型的理解

    面向物件三要素：封裝、繼承、多型。 封裝和繼承，這兩個比較好理解，但要理解多型的話，可就稍微有點難度了。今天，我們就來講講多型的理解。 我們應該經常會看到面試題目：請談談對多型的理解。 其實呢，多型非常簡單，就一句話：呼叫同一種方法產生了不同的結果。 具體實作方式有三種。 一、多載 多載很簡單。 p ......

    uj5u.com 2020-09-10 05:36:09 more
  • Python 資料驅動工具：DDT

    背景 python 的unittest 沒有自帶資料驅動功能。 所以如果使用unittest，同時又想使用資料驅動，那么就可以使用DDT來完成。 DDT是 “Data-Driven Tests”的縮寫。 資料：http://ddt.readthedocs.io/en/latest/ 使用方法 dd. ......

    uj5u.com 2020-09-10 05:36:13 more
  • Python里面的xlrd模塊詳解

    那我就一下面積個問題對xlrd模塊進行學習一下： 1.什么是xlrd模塊？ 2.為什么使用xlrd模塊？ 3.怎樣使用xlrd模塊？ 1.什么是xlrd模塊？ ?python操作excel主要用到xlrd和xlwt這兩個庫，即xlrd是讀excel，xlwt是寫excel的庫。 今天就先來說一下xl ......

    uj5u.com 2020-09-10 05:36:28 more
  • 當我們創建HashMap時，底層到底做了什么？

    jdk1.7中的底層實作程序（底層基于陣列+鏈表） 在我們new HashMap()時，底層創建了默認長度為16的一維陣列Entry[ ] table。當我們呼叫map.put(key1,value1)方法向HashMap里添加資料的時候： 首先，呼叫key1所在類的hashCode()計算key1 ......

    uj5u.com 2020-09-10 05:36:38 more
最新发布
  • 【中介者設計模式詳解】C/Java/JS/Go/Python/TS不同語言實作

    * 中介者模式是一種行為型設計模式，它可以用來減少類之間的直接依賴關系，
    * 將物件之間的通信封裝到一個中介者物件中，從而使得各個物件之間的關系更加松散。
    * 在中介者模式中，物件之間不再直接相互互動，而是通過中介者來中轉訊息。 ......

    uj5u.com 2023-04-20 08:20:47 more
  • 露天煤礦現場調研和交流案例分享

    他們集團的資訊化公司及研究院在一個礦區正在做智能礦山的統一平臺的 試點，專案投資大概1億，包括了礦山的各方面的內容，顯示得我們這次交流有點多余。他們2年前開始做智能礦山的規劃，有很多煤礦行業專家的加持，他們的描述是非常完美，但是去年底應該上線的平臺，現在還沒有看到影子。他們確實有很多場景需求，但是被... ......

    uj5u.com 2023-04-20 08:20:25 more
  • 《社區人員管理》實戰案例設計&個人案例分享

    設計是一個讓人夢想成真程序，開始編碼、測驗、除錯之前進行需求分析和架構設計，才能保證關鍵方面都做正確 ......

    uj5u.com 2023-04-20 08:20:17 more
  • 軟體架構生態化-多角色交付的探索實踐

    作為一個技術架構師，不僅僅要緊跟行業技術趨勢，還要結合研發團隊現狀及痛點，探索新的交付方案。在日常中，你是否遇到如下問題 “ 業務需求排期長研發是瓶頸；非研發角色感受不到研發技改提效的變化；引入ISV 團隊又擔心質量和安全，培訓周期長“等等，基于此我們探索了一種新的技術體系及交付方案來解決如上問題。 ......

    uj5u.com 2023-04-20 08:20:10 more
  • 【中介者設計模式詳解】C/Java/JS/Go/Python/TS不同語言實作

    * 中介者模式是一種行為型設計模式，它可以用來減少類之間的直接依賴關系，
    * 將物件之間的通信封裝到一個中介者物件中，從而使得各個物件之間的關系更加松散。
    * 在中介者模式中，物件之間不再直接相互互動，而是通過中介者來中轉訊息。 ......

    uj5u.com 2023-04-20 08:19:44 more
  • 露天煤礦現場調研和交流案例分享

    他們集團的資訊化公司及研究院在一個礦區正在做智能礦山的統一平臺的 試點，專案投資大概1億，包括了礦山的各方面的內容，顯示得我們這次交流有點多余。他們2年前開始做智能礦山的規劃，有很多煤礦行業專家的加持，他們的描述是非常完美，但是去年底應該上線的平臺，現在還沒有看到影子。他們確實有很多場景需求，但是被... ......

    uj5u.com 2023-04-20 08:19:07 more
  • 《社區人員管理》實戰案例設計&個人案例分享

    設計是一個讓人夢想成真程序，開始編碼、測驗、除錯之前進行需求分析和架構設計，才能保證關鍵方面都做正確 ......

    uj5u.com 2023-04-20 08:18:57 more
  • 軟體架構生態化-多角色交付的探索實踐

    作為一個技術架構師，不僅僅要緊跟行業技術趨勢，還要結合研發團隊現狀及痛點，探索新的交付方案。在日常中，你是否遇到如下問題 “ 業務需求排期長研發是瓶頸；非研發角色感受不到研發技改提效的變化；引入ISV 團隊又擔心質量和安全，培訓周期長“等等，基于此我們探索了一種新的技術體系及交付方案來解決如上問題。 ......

    uj5u.com 2023-04-20 08:18:49 more
  • 05單件模式

    #經典的單件模式 public class Singleton { private static Singleton uniqueInstance; //一個靜態變數持有Singleton類的唯一實體。 // 其他有用的實體變數寫在這里 //構造器宣告為私有，只有Singleton可以實體化這個類! ......

    uj5u.com 2023-04-19 08:42:51 more
  • 【架構與設計】常見微服務分層架構的區別和落地實踐

    軟體工程的方方面面都遵循一個最基本的道理：沒有銀彈，架構分層模型更是如此，每一種都有各自優缺點，所以請根據不同的業務場景，并遵循簡單、可演進這兩個重要的架構原則選擇合適的架構分層模型即可。 ......

    uj5u.com 2023-04-19 08:42:41 more

Copyright © 2010-2020 有解無憂