第十一章：圖論part11

Floyd 算法精講

Floyd 算法代碼很簡(jiǎn)單，但真正理解起原理 還是需要花點(diǎn)功夫她按，大家在看代碼的時(shí)候牛隅，會(huì)發(fā)現(xiàn) Floyd 的代碼很簡(jiǎn)單炕柔，甚至看一眼就背下來(lái)了，但我為了講清楚原理媒佣，本篇還是花了大篇幅來(lái)講解匕累。
文章講解

思路

• 本題是經(jīng)典的多源最短路問(wèn)題，即 求多個(gè)起點(diǎn)到多個(gè)終點(diǎn)的多條最短路徑默伍。

Floyd算法簡(jiǎn)介及其核心思想

Floyd算法哩罪，又稱為Floyd-Warshall算法，是一種用于求解所有節(jié)點(diǎn)對(duì)之間最短路徑的算法巡验。該算法特別強(qiáng)大的一點(diǎn)是际插，它對(duì)邊的權(quán)值正負(fù)沒(méi)有限制，也就是說(shuō)显设，邊的權(quán)值可以是正數(shù)框弛、零，甚至是負(fù)數(shù)（前提是沒(méi)有負(fù)權(quán)環(huán)）捕捂。因此瑟枫，F(xiàn)loyd算法能夠處理更廣泛的問(wèn)題。

Floyd算法的核心思想：動(dòng)態(tài)規(guī)劃

Floyd算法的核心思想是動(dòng)態(tài)規(guī)劃指攒。它通過(guò)不斷更新所有節(jié)點(diǎn)對(duì)之間的最短路徑慷妙，最終找到全局最優(yōu)解。

遞推關(guān)系的推導(dǎo)：

1. 直接路徑：如果我們要計(jì)算節(jié)點(diǎn)1到節(jié)點(diǎn)9的最短路徑允悦，可以直接從節(jié)點(diǎn)1到節(jié)點(diǎn)9得到該路徑的初始值膝擂，記為grid[1][9]。

2. 通過(guò)中間節(jié)點(diǎn)路徑：節(jié)點(diǎn)1到節(jié)點(diǎn)9的最短路徑可以通過(guò)某個(gè)中間節(jié)點(diǎn)（如節(jié)點(diǎn)5）來(lái)拆分隙弛，即：grid[1][9] = grid[1][5] + grid[5][9]

   其中架馋，grid[1][5]表示從節(jié)點(diǎn)1到節(jié)點(diǎn)5的最短路徑，而grid[5][9]表示從節(jié)點(diǎn)5到節(jié)點(diǎn)9的最短路徑全闷。

3. 逐步分解：進(jìn)一步地叉寂，節(jié)點(diǎn)1到節(jié)點(diǎn)5的最短路徑可以通過(guò)其他中間節(jié)點(diǎn)（如節(jié)點(diǎn)3）來(lái)分解：grid[1][5] = grid[1][3] + grid[3][5]

   以此類推，我們可以將節(jié)點(diǎn)1到節(jié)點(diǎn)9的最短路徑逐步分解為更小的子路徑总珠，直到不能再分解屏鳍。

Floyd算法的動(dòng)態(tài)規(guī)劃五部曲總結(jié)

之前在講解動(dòng)態(tài)規(guī)劃的時(shí)候，給出過(guò)動(dòng)規(guī)五部曲：

• 確定dp數(shù)組（dp table）以及下標(biāo)的含義
• 確定遞推公式
• dp數(shù)組如何初始化
• 確定遍歷順序
• 舉例推導(dǎo)dp數(shù)組
  接下來(lái)還是用這五部講解 Floyd局服。

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

在Floyd算法中钓瞭，dp數(shù)組可以用grid[i][j][k]表示，含義是節(jié)點(diǎn)i到節(jié)點(diǎn)j腌逢，以集合[1...k]為中間節(jié)點(diǎn)的最短距離為m降淮。

• grid[i][j][k]：表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j，經(jīng)過(guò)節(jié)點(diǎn)1到節(jié)點(diǎn)k之間所有節(jié)點(diǎn)的最短路徑搏讶。
• k表示一個(gè)節(jié)點(diǎn)的集合佳鳖，不是單獨(dú)的一個(gè)節(jié)點(diǎn)。通過(guò)這樣的定義媒惕，可以遞歸地計(jì)算出任意兩個(gè)節(jié)點(diǎn)之間的最短路徑系吩。

2. 確定遞推公式

Floyd算法的遞推公式是通過(guò)分析兩種情況得出的：

1. 路徑經(jīng)過(guò)節(jié)點(diǎn)k：如果節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑經(jīng)過(guò)節(jié)點(diǎn)k，那么：
   grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1]
   其中grid[i][k][k-1]和grid[k][j][k-1]分別表示節(jié)點(diǎn)i到節(jié)點(diǎn)k和節(jié)點(diǎn)k到節(jié)點(diǎn)j的最短路徑妒蔚，不經(jīng)過(guò)節(jié)點(diǎn)k穿挨。

2. 路徑不經(jīng)過(guò)節(jié)點(diǎn)k：如果節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑不經(jīng)過(guò)節(jié)點(diǎn)k，那么：
   grid[i][j][k] = grid[i][j][k-1]
   因此肴盏，遞推公式為：
   grid[i][j][k] = \min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1])

3. dp數(shù)組如何初始化

grid數(shù)組是一個(gè)三維數(shù)組科盛，那么我們初始化的數(shù)據(jù)在 i 與 j 構(gòu)成的平層，如圖：

image.png

紅色的 底部一層是我們初始化好的數(shù)據(jù)

初始化dp數(shù)組時(shí)：

• grid[i][j][0]表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的直接路徑長(zhǎng)度菜皂。如果節(jié)點(diǎn)i直接連向節(jié)點(diǎn)j（例如邊p1 -> p2贞绵，權(quán)值為val），那么：
  grid[p1][p2][0] = val
  同樣恍飘，因?yàn)閳D是雙向的榨崩，所以：
  grid[p2][p1][0] = val
• 對(duì)于沒(méi)有直接連通的節(jié)點(diǎn)，grid[i][j][0]應(yīng)初始化為一個(gè)很大的值（如10005章母，題目中最大是10004）母蛛，表示無(wú)法直接連通。

代碼：

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 節(jié)點(diǎn)數(shù)量
int m = scanner.nextInt(); // 邊的數(shù)量

// 初始化三維數(shù)組 grid
int[][][] grid = new int[n + 1][n + 1][n + 1];
for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
        Arrays.fill(grid[i][j], 10005); // 設(shè)置初始值為10005
    }
}

// 讀取邊的信息并初始化 grid 數(shù)組
for (int i = 0; i < m; i++) {
    int p1 = scanner.nextInt();
    int p2 = scanner.nextInt();
    int val = scanner.nextInt();
    grid[p1][p2][0] = val;
    grid[p2][p1][0] = val; // 處理雙向圖
}

4. 確定遍歷順序

遍歷順序的確定是Floyd算法的關(guān)鍵：
從遞推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]乳怎， grid[i][j][k - 1])可以看出彩郊，我們需要三個(gè)for循環(huán)，分別遍歷i蚪缀，j 和k
而 k 依賴于 k - 1焦辅， i 和j 的到 并不依賴與 i - 1 或者 j - 1 等等。

那么這三個(gè)for的嵌套順序應(yīng)該是什么樣的呢椿胯？
我們來(lái)看初始化筷登，我們是把 k =0 的 i 和j 對(duì)應(yīng)的數(shù)值都初始化了，這樣才能去計(jì)算 k = 1 的時(shí)候 i 和 j 對(duì)應(yīng)的數(shù)值哩盲。
這就好比是一個(gè)三維坐標(biāo)前方，i 和j 是平層，而k 是 垂直向上 的廉油。
遍歷的順序是從底向上 一層一層去遍歷惠险。
所以遍歷k 的for循環(huán)一定是在最外面，這樣才能一層一層去遍歷抒线。

image.png

• k放在最外層：首先遍歷k（中間節(jié)點(diǎn)的集合）班巩，然后遍歷i和j（起點(diǎn)和終點(diǎn)），確保在更新grid[i][j][k]時(shí)嘶炭，已經(jīng)計(jì)算出了grid[i][j][k-1]的值抱慌。

  for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= n; j++) {
              grid[i][j][k] = Math.min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
          }
      }
  }
  

• 如果將k放在內(nèi)層逊桦，可能會(huì)導(dǎo)致不能正確利用之前的計(jì)算結(jié)果，導(dǎo)致錯(cuò)誤的最短路徑抑进。

5. 舉例推導(dǎo)dp數(shù)組

為了確保理解Floyd算法的遞推過(guò)程强经，可以通過(guò)舉例分析各個(gè)步驟：

• 先初始化k=0的dp數(shù)組，然后逐層計(jì)算k=1, 2, ...時(shí)的最短路徑寺渗。
• 通過(guò)打印出每層的dp數(shù)組匿情，可以直觀地看到如何一步步接近最終的最短路徑。

Java 版本的 Floyd 算法實(shí)現(xiàn)及空間優(yōu)化

原始版本

import java.util.Scanner;

public class FloydWarshall {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 節(jié)點(diǎn)數(shù)量
        int m = scanner.nextInt(); // 邊的數(shù)量

        int[][][] grid = new int[n + 1][n + 1][n + 1];
        
        // 初始化三維數(shù)組 grid信殊，所有元素設(shè)置為10005
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= n; k++) {
                    grid[i][j][k] = 10005;
                }
            }
        }

        // 讀取邊的信息并初始化 grid 數(shù)組
        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            grid[p1][p2][0] = val;
            grid[p2][p1][0] = val; // 雙向圖
        }

        // 開(kāi)始 Floyd-Warshall 算法
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    grid[i][j][k] = Math.min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
                }
            }
        }

        // 輸出結(jié)果
        int z = scanner.nextInt();
        while (z-- > 0) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if (grid[start][end][n] == 10005) {
                System.out.println(-1);
            } else {
                System.out.println(grid[start][end][n]);
            }
        }
    }
}

空間優(yōu)化版本

空間優(yōu)化版本利用滾動(dòng)數(shù)組和二維數(shù)組來(lái)減少空間消耗炬称，將三維數(shù)組優(yōu)化為二維數(shù)組：

import java.util.Scanner;

public class FloydWarshallOptimized {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 節(jié)點(diǎn)數(shù)量
        int m = scanner.nextInt(); // 邊的數(shù)量

        int[][] grid = new int[n + 1][n + 1];

        // 初始化二維數(shù)組 grid，所有元素設(shè)置為10005
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                grid[i][j] = 10005;
            }
        }

        // 讀取邊的信息并初始化 grid 數(shù)組
        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            grid[p1][p2] = val;
            grid[p2][p1] = val; // 雙向圖
        }

        // 開(kāi)始 Floyd-Warshall 算法
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);
                }
            }
        }

        // 輸出結(jié)果
        int z = scanner.nextInt();
        while (z-- > 0) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if (grid[start][end] == 10005) {
                System.out.println(-1);
            } else {
                System.out.println(grid[start][end]);
            }
        }
    }
}

代碼解釋

• 初始化:

  • 在原始版本中涡拘，使用三維數(shù)組grid[i][j][k]來(lái)表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j玲躯，經(jīng)過(guò)前k個(gè)節(jié)點(diǎn)時(shí)的最短路徑。
  • 在優(yōu)化版本中鲸伴，使用二維數(shù)組grid[i][j]來(lái)表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑府蔗。每次更新時(shí)，直接使用當(dāng)前二維數(shù)組的狀態(tài)汞窗，這樣只需存儲(chǔ)當(dāng)前和前一個(gè)狀態(tài)的最短路徑姓赤。

• Floyd-Warshall算法:

  • 遍歷k，i仲吏，j三個(gè)維度不铆，通過(guò)中間節(jié)點(diǎn)k來(lái)更新節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑。

• 空間優(yōu)化:

  • 通過(guò)使用二維數(shù)組代替三維數(shù)組裹唆，將空間復(fù)雜度從O(n^3)優(yōu)化到O(n^2)誓斥。

復(fù)雜度分析

• 時(shí)間復(fù)雜度:

  • 兩個(gè)版本的時(shí)間復(fù)雜度都是O(n^3)，因?yàn)樾枰闅v三個(gè)維度i许帐，j劳坑，k。

• 空間復(fù)雜度:

  • 原始版本的空間復(fù)雜度是O(n^3)成畦。
  • 優(yōu)化版本的空間復(fù)雜度是O(n^2)距芬，因?yàn)橹皇褂昧硕S數(shù)組。

A * 算法精講 （A star算法）

一般 筆試或者 面試的時(shí)候循帐，不會(huì)考察A框仔， 都是會(huì)結(jié)合具體業(yè)務(wù)場(chǎng)景問(wèn) A算法，例如：地圖導(dǎo)航拄养，游戲開(kāi)發(fā) 等等离斩。
其實(shí)基礎(chǔ)版的A* 并不難，所以大家不要畏懼，理解本篇內(nèi)容跛梗，甚至獨(dú)立寫(xiě)出代碼寻馏，大家可以做到，加油
文章講解

思路

我們看到這道題目的第一個(gè)想法就是廣搜茄袖，這也是最經(jīng)典的廣搜類型題目操软。

import java.util.*;

public class KnightMoves {
    static int[][] moves = new int[1001][1001];
    static int[][] dir = {
        {-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
        {2, 1}, {2, -1}, {1, -2}, {-1, -2}
    };

    public static void bfs(int a1, int a2, int b1, int b2) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{a1, a2});

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int m = current[0];
            int n = current[1];

            if (m == b1 && n == b2) {
                break;
            }

            for (int i = 0; i < 8; i++) {
                int mm = m + dir[i][0];
                int nn = n + dir[i][1];

                if (mm < 1 || mm > 1000 || nn < 1 || nn > 1000) {
                    continue;
                }

                if (moves[mm][nn] == 0) {
                    moves[mm][nn] = moves[m][n] + 1;
                    q.offer(new int[]{mm, nn});
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        while (n-- > 0) {
            int a1 = scanner.nextInt();
            int a2 = scanner.nextInt();
            int b1 = scanner.nextInt();
            int b2 = scanner.nextInt();

            // 重置moves數(shù)組
            for (int i = 0; i < 1001; i++) {
                Arrays.fill(moves[i], 0);
            }

            bfs(a1, a2, b1, b2);
            System.out.println(moves[b1][b2]);
        }
        
        scanner.close();
    }
}

提交后會(huì)發(fā)現(xiàn)嘁锯，超時(shí)了宪祥。
因?yàn)楸绢}地圖足夠大，且 n 也有可能很大家乘，導(dǎo)致有非常多的查詢蝗羊。

Astar

A算法是廣度優(yōu)先搜索（BFS）和Dijkstra算法的改良版，適用于在圖上尋找最短路徑的問(wèn)題仁锯。A通過(guò)結(jié)合啟發(fā)式函數(shù)耀找，引導(dǎo)搜索過(guò)程更高效地找到目標(biāo)節(jié)點(diǎn)。

1. 選擇算法的場(chǎng)景

• 無(wú)權(quán)圖（邊的權(quán)值都是1）：使用BFS业崖，代碼簡(jiǎn)潔野芒，效率較高。
• 有權(quán)圖（邊有不同的權(quán)值）：優(yōu)先考慮Dijkstra算法双炕。
• 目標(biāo)導(dǎo)向搜索：A*算法適合有明確起點(diǎn)和終點(diǎn)的搜索狞悲，能有效減少不必要的遍歷。

2. A*算法的核心：?jiǎn)l(fā)式函數(shù)

A算法的關(guān)鍵在于啟發(fā)式函數(shù)*妇斤，它影響搜索過(guò)程中從容器（隊(duì)列或優(yōu)先隊(duì)列）中取出節(jié)點(diǎn)的優(yōu)先順序摇锋。

BFS與A*的對(duì)比

• BFS：一層一層地遍歷節(jié)點(diǎn)，無(wú)目的性站超，搜索過(guò)程是無(wú)方向的荸恕。
• A*：搜索過(guò)程中有方向性，基于啟發(fā)式函數(shù)優(yōu)先選擇更有可能到達(dá)終點(diǎn)的路徑死相，節(jié)省了大量不必要的遍歷步驟融求。

3. 啟發(fā)式函數(shù)的作用

啟發(fā)式函數(shù)用于給每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)值F，并按照F值來(lái)排序隊(duì)列中的節(jié)點(diǎn)算撮，決定搜索的方向生宛。公式如下：

• F = G + H
  • G：從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)（路徑長(zhǎng)度）。
  • H：當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估算代價(jià)（通常用距離計(jì)算）钮惠。

4. 距離計(jì)算方法

在網(wǎng)格狀圖中茅糜，常用的距離計(jì)算方法有三種：

• 曼哈頓距離：d = abs(x1-x2) + abs(y1-y2)
• 歐氏距離（歐拉距離）：d = sqrt((x1-x2)^2 + (y1-y2)^2)
• 切比雪夫距離：d = max(abs(x1-x2), abs(y1-y2))

三種距離的詳細(xì)講解

在圖算法（如A*算法）中，計(jì)算距離是確定啟發(fā)式函數(shù)的重要部分素挽。曼哈頓距離蔑赘、歐氏距離和切比雪夫距離是最常用的三種距離計(jì)算方式，它們適用于不同的場(chǎng)景。以下是對(duì)這三種距離的詳細(xì)講解：

1. 曼哈頓距離（Manhattan Distance）

公式：d = abs(x1 - x2) + abs(y1 - y2)

• 概念：

  • 曼哈頓距離是指在網(wǎng)格狀的地圖中缩赛，只能沿著水平或垂直方向移動(dòng)的情況下耙箍，兩個(gè)點(diǎn)之間的距離總和。
  • 這種距離計(jì)算方式得名于曼哈頓的街道布局酥馍，在這種布局中辩昆，街道呈網(wǎng)格狀，車輛只能沿著正北旨袒、正南汁针、正東、正西方向移動(dòng)砚尽。

• 適用場(chǎng)景：

  • 當(dāng)只能在網(wǎng)格上水平或垂直移動(dòng)時(shí)施无，曼哈頓距離是最準(zhǔn)確的。
  • 例如：在棋盤(pán)游戲中必孤，棋子只能水平或垂直移動(dòng)猾骡。

• 舉例：

  • 假設(shè)有兩個(gè)點(diǎn)A和B，A的坐標(biāo)是(1, 2)敷搪，B的坐標(biāo)是(4, 6)兴想，那么它們之間的曼哈頓距離為：
    [
    d = abs(1 - 4) + abs(2 - 6) = 3 + 4 = 7
    ]
  • 這個(gè)值表示從A到B的最短路徑需要7個(gè)單位長(zhǎng)度的移動(dòng)，如果只能沿著網(wǎng)格的水平和垂直方向移動(dòng)赡勘。

2. 歐氏距離（Euclidean Distance）

公式：d = sqrt((x1 - x2)^2 + (y1 - y2)^2)

• 概念：

  • 歐氏距離是平面直角坐標(biāo)系中嫂便，兩個(gè)點(diǎn)之間的直線距離。
  • 它是使用勾股定理計(jì)算出來(lái)的狮含，也被稱為歐拉距離或直線距離顽悼。

• 適用場(chǎng)景：

  • 當(dāng)可以在任意方向上移動(dòng)時(shí)，歐氏距離是最準(zhǔn)確的几迄。
  • 例如：在平面中自由移動(dòng)的機(jī)器人蔚龙，或者需要測(cè)量點(diǎn)與點(diǎn)之間的直線距離時(shí)。

• 舉例：

  • 假設(shè)有兩個(gè)點(diǎn)A和B映胁，A的坐標(biāo)是(1, 2)木羹，B的坐標(biāo)是(4, 6)，它們之間的歐氏距離為：
    [
    d = \sqrt{(1 - 4)^2 + (2 - 6)^2} = \sqrt{9 + 16} = \sqrt{25} = 5
    ]
  • 這個(gè)值表示從A到B的直線距離為5個(gè)單位長(zhǎng)度解孙，適合可以沿任意方向移動(dòng)的情況坑填。

3. 切比雪夫距離（Chebyshev Distance）

公式：d = max(abs(x1 - x2), abs(y1 - y2))

• 概念：

  • 切比雪夫距離是指在允許沿著水平、垂直以及對(duì)角線方向移動(dòng)的情況下弛姜，兩個(gè)點(diǎn)之間的最大單一方向上的距離脐瑰。
  • 這種距離計(jì)算方式適用于可以沿對(duì)角線方向自由移動(dòng)的場(chǎng)景。

• 適用場(chǎng)景：

  • 當(dāng)在網(wǎng)格上移動(dòng)時(shí)廷臼，既可以沿水平或垂直方向移動(dòng)苍在，也可以沿對(duì)角線移動(dòng)時(shí)绝页，切比雪夫距離是最準(zhǔn)確的。
  • 例如：在國(guó)際象棋中寂恬，國(guó)王每次可以沿任意方向移動(dòng)一個(gè)單位续誉，適用切比雪夫距離。

• 舉例：

  • 假設(shè)有兩個(gè)點(diǎn)A和B初肉，A的坐標(biāo)是(1, 2)酷鸦，B的坐標(biāo)是(4, 6)，它們之間的切比雪夫距離為：
    [
    d = \max(abs(1 - 4), abs(2 - 6)) = \max(3, 4) = 4
    ]
  • 這個(gè)值表示從A到B的最短路徑需要4步牙咏，如果允許沿水平臼隔、垂直和對(duì)角線方向移動(dòng)。

總結(jié)

• 曼哈頓距離：適用于只能沿水平或垂直方向移動(dòng)的場(chǎng)景眠寿，計(jì)算簡(jiǎn)單躬翁，結(jié)果為移動(dòng)步數(shù)的總和焦蘑。
• 歐氏距離：適用于可以在任意方向上自由移動(dòng)的場(chǎng)景盯拱，結(jié)果為兩個(gè)點(diǎn)之間的直線距離。
• 切比雪夫距離：適用于可以沿水平例嘱、垂直以及對(duì)角線方向移動(dòng)的場(chǎng)景狡逢，結(jié)果為兩個(gè)點(diǎn)之間最大單一方向的距離。

5. A*算法的實(shí)現(xiàn)

在A*算法中拼卵，啟發(fā)式函數(shù)引導(dǎo)搜索過(guò)程奢浑，可以通過(guò)優(yōu)先級(jí)隊(duì)列來(lái)實(shí)現(xiàn)：

• 優(yōu)先級(jí)隊(duì)列：根據(jù)節(jié)點(diǎn)的F值進(jìn)行排序，每次從隊(duì)列中取出F值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展腋腮。

import java.util.PriorityQueue;
import java.util.Scanner;

class Knight implements Comparable<Knight> {
    int x, y;
    int g, h, f;

    // 重載運(yùn)算符雀彼，用于優(yōu)先級(jí)隊(duì)列的排序
    @Override
    public int compareTo(Knight k) {
        return Integer.compare(this.f, k.f);
    }
}

public class AStarKnight {
    static int[][] moves = new int[1001][1001];
    static int[][] dir = {
        {-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
        {2, 1}, {2, -1}, {1, -2}, {-1, -2}
    };
    static int b1, b2;
    static PriorityQueue<Knight> que = new PriorityQueue<>();

    public static int heuristic(Knight k) { // 歐拉距離
        return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 統(tǒng)一不開(kāi)根號(hào)，這樣可以提高精度
    }

    public static void astar(Knight k) {
        que.offer(k);
        while (!que.isEmpty()) {
            Knight cur = que.poll();
            if (cur.x == b1 && cur.y == b2)
                break;
            for (int i = 0; i < 8; i++) {
                int nextX = cur.x + dir[i][0];
                int nextY = cur.y + dir[i][1];
                if (nextX < 1 || nextX > 1000 || nextY < 1 || nextY > 1000)
                    continue;
                if (moves[nextX][nextY] == 0) {
                    moves[nextX][nextY] = moves[cur.x][cur.y] + 1;

                    Knight next = new Knight();
                    next.x = nextX;
                    next.y = nextY;
                    next.g = cur.g + 5; // 統(tǒng)一不開(kāi)根號(hào)即寡，這樣可以提高精度徊哑，馬走日，1 * 1 + 2 * 2 = 5
                    next.h = heuristic(next);
                    next.f = next.g + next.h;
                    que.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        while (n-- > 0) {
            int a1 = scanner.nextInt();
            int a2 = scanner.nextInt();
            b1 = scanner.nextInt();
            b2 = scanner.nextInt();

            // 重置 moves 數(shù)組
            for (int i = 0; i < 1001; i++) {
                for (int j = 0; j < 1001; j++) {
                    moves[i][j] = 0;
                }
            }

            Knight start = new Knight();
            start.x = a1;
            start.y = a2;
            start.g = 0;
            start.h = heuristic(start);
            start.f = start.g + start.h;
            
            astar(start);
            que.clear(); // 清空隊(duì)列
            System.out.println(moves[b1][b2]);
        }
        scanner.close();
    }
}

代碼解釋

1. Knight類：

   • 定義了騎士的坐標(biāo)x和y聪富，以及g（從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑消耗）莺丑、h（當(dāng)前節(jié)點(diǎn)到終點(diǎn)的預(yù)估消耗）、f（總消耗墩蔓，即g + h）梢莽。
   • 實(shí)現(xiàn)了Comparable<Knight>接口，以便在PriorityQueue中根據(jù)f值進(jìn)行排序奸披。

2. AStarKnight類：

   • moves：二維數(shù)組昏名，用于記錄騎士到達(dá)每個(gè)位置的最短路徑長(zhǎng)度。
   • dir：存儲(chǔ)騎士可以移動(dòng)的8個(gè)方向阵面。
   • b1和b2：目標(biāo)位置的坐標(biāo)轻局。
   • que：優(yōu)先級(jí)隊(duì)列份殿，用于按照f值對(duì)節(jié)點(diǎn)進(jìn)行排序。

3. 啟發(fā)式函數(shù)：

   • heuristic(Knight k)：計(jì)算歐拉距離（啟發(fā)式函數(shù)H）嗽交，這里不開(kāi)根號(hào)以提高精度卿嘲。

4. A算法的實(shí)現(xiàn)*：

   • astar(Knight k)：使用A*算法從起點(diǎn)開(kāi)始搜索最短路徑，每次選擇f值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展夫壁，直到找到終點(diǎn)拾枣。

5. main方法：

   • 讀取輸入數(shù)據(jù)，初始化起點(diǎn)騎士的位置和其他參數(shù)盒让，調(diào)用astar方法進(jìn)行搜索梅肤，最后輸出到達(dá)終點(diǎn)的最短路徑長(zhǎng)度。

你提到的關(guān)于坐標(biāo)系的解釋是正確的邑茄，涉及到的是二維數(shù)組的標(biāo)準(zhǔn)坐標(biāo)系（行列表示法）與通常的笛卡爾坐標(biāo)系之間的區(qū)別姨蝴。這種區(qū)別確實(shí)在不同的應(yīng)用場(chǎng)景中可能會(huì)導(dǎo)致混淆。讓我為你澄清這兩種坐標(biāo)系在騎士移動(dòng)問(wèn)題中的具體應(yīng)用肺缕，并解釋它們?nèi)绾我恢禄虿煌?/p>

6. 二維數(shù)組坐標(biāo)系（行列表示法）
   在二維數(shù)組（如圖像處理左医、棋盤(pán)游戲等）中，通常采用的坐標(biāo)系如下：

• 行（row）：表示x軸同木，通常從上到下浮梢，x值遞增。
• 列（column）：表示y軸彤路，通常從左到右秕硝，y值遞增。

(0,0)  (0,1)  (0,2)  ...
(1,0)  (1,1)  (1,2)  ...
(2,0)  (2,1)  (2,2)  ...

在這個(gè)系統(tǒng)中：

• 向右移動(dòng)：y增加 (y+1)
• 向下移動(dòng)：x增加 (x+1)
• 向上移動(dòng)：x減少 (x-1)
• 向左移動(dòng)：y減少 (y-1)

在騎士的移動(dòng)問(wèn)題中洲尊，坐標(biāo)系通常遵循二維數(shù)組的定義远豺，即：

• x 表示行數(shù)，向下遞增坞嘀。
• y 表示列數(shù)躯护，向右遞增。

static int[][] dir = {
    {-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
    {2, 1}, {2, -1}, {1, -2}, {-1, -2}
};

這些方向的含義如下：

• {-2, -1}：向上移動(dòng)2格姆吭，同時(shí)向左移動(dòng)1格（x減少2榛做，y減少1）
• {-2, 1}：向上移動(dòng)2格，同時(shí)向右移動(dòng)1格（x減少2内狸，y增加1）
• {-1, 2}：向上移動(dòng)1格检眯，同時(shí)向右移動(dòng)2格（x減少1，y增加2）
• {1, 2}：向下移動(dòng)1格昆淡，同時(shí)向右移動(dòng)2格（x增加1锰瘸，y增加2）
• {2, 1}：向下移動(dòng)2格，同時(shí)向右移動(dòng)1格（x增加2昂灵，y增加1）
• {2, -1}：向下移動(dòng)2格避凝，同時(shí)向左移動(dòng)1格（x增加2舞萄，y減少1）
• {1, -2}：向下移動(dòng)1格，同時(shí)向左移動(dòng)2格（x增加1管削，y減少2）
• {-1, -2}：向上移動(dòng)1格倒脓，同時(shí)向左移動(dòng)2格（x減少1，y減少2）

A* 算法的復(fù)雜度分析

時(shí)間復(fù)雜度：

• 不可量化：A*算法的時(shí)間復(fù)雜度難以精確量化含思，因?yàn)樗叨纫蕾囉趩l(fā)式函數(shù)的設(shè)計(jì)崎弃。
• 最壞情況：在最壞情況下，A*算法可能退化為廣度優(yōu)先搜索（BFS）含潘，其時(shí)間復(fù)雜度為O(n^2)饲做，其中n為節(jié)點(diǎn)數(shù)量。
• 最佳情況：如果啟發(fā)式函數(shù)非常有效遏弱，使得搜索路徑直接從起點(diǎn)到終點(diǎn)盆均，時(shí)間復(fù)雜度可以降到O(d log d)，其中d為起點(diǎn)到終點(diǎn)的深度漱逸。
• 一般情況：通常泪姨，A*算法的時(shí)間復(fù)雜度介于最優(yōu)和最壞情況之間，可以粗略地認(rèn)為是O(n log n)虹脯，其中n為節(jié)點(diǎn)數(shù)量驴娃。這是因?yàn)樵谒阉鬟^(guò)程中，節(jié)點(diǎn)需要通過(guò)優(yōu)先級(jí)隊(duì)列排序循集，而隊(duì)列操作的時(shí)間復(fù)雜度是O(log n)。

空間復(fù)雜度：

• A*算法的空間復(fù)雜度是O(b^d)蔗草，其中d為起點(diǎn)到終點(diǎn)的深度咒彤，b是圖中節(jié)點(diǎn)間的連接數(shù)量。在網(wǎng)格圖中咒精，每個(gè)節(jié)點(diǎn)通常有4個(gè)相鄰節(jié)點(diǎn)镶柱，因此b通常為4。

擴(kuò)展分析

• 啟發(fā)式函數(shù)的選擇：

  • 啟發(fā)式函數(shù)的設(shè)計(jì)直接影響A*算法的搜索路徑和效率模叙。不同的啟發(fā)式函數(shù)歇拆，如曼哈頓距離和切比雪夫距離，可能在某些場(chǎng)景下導(dǎo)致次優(yōu)路徑范咨。
  • 例如在某些小型地圖（如8x8棋盤(pán)）上故觅，使用曼哈頓距離可能不會(huì)明顯影響結(jié)果，但在較大或更復(fù)雜的地圖上渠啊，不準(zhǔn)確的啟發(fā)式函數(shù)會(huì)影響路徑質(zhì)量输吏。

• 啟發(fā)式函數(shù)與效率的權(quán)衡：

  • A*算法并不是嚴(yán)格的最短路徑算法，其結(jié)果取決于啟發(fā)式函數(shù)的設(shè)計(jì)替蛉。啟發(fā)式函數(shù)需要在時(shí)間效率和路徑準(zhǔn)確度之間找到平衡贯溅。
  • 在某些應(yīng)用場(chǎng)景拄氯，如游戲開(kāi)發(fā)中，A*算法的啟發(fā)式函數(shù)可能設(shè)計(jì)為次優(yōu)路徑它浅，以提高運(yùn)行效率译柏，而不一定追求最短路徑。玩家通常接受接近最短路徑的結(jié)果姐霍，而不會(huì)在意微小的偏差艇纺。

A* 算法的缺點(diǎn)

1. 空間消耗：

   • A*算法在搜索過(guò)程中會(huì)擴(kuò)展大量節(jié)點(diǎn)并將它們存儲(chǔ)在優(yōu)先級(jí)隊(duì)列中。即使這些節(jié)點(diǎn)可能不被訪問(wèn)邮弹，它們?nèi)匀徽加每臻g黔衡，導(dǎo)致高內(nèi)存消耗。
   • 優(yōu)化方案：IDA（Iterative Deepening A）算法是A的改進(jìn)版腌乡，旨在解決A算法中空間消耗過(guò)大的問(wèn)題盟劫。

2. 多目標(biāo)問(wèn)題：

   • A算法不擅長(zhǎng)處理多個(gè)潛在目標(biāo)的問(wèn)題。如果需要在多個(gè)目標(biāo)中找到最近的一個(gè)与纽，A算法可能表現(xiàn)不佳侣签。
   • 替代方案：對(duì)于多個(gè)目標(biāo)問(wèn)題，可以考慮使用Dijkstra算法急迂、BFS或Floyd算法影所，它們?cè)谶@種場(chǎng)景下可能更合適。

最短路算法總結(jié)篇

最各個(gè)最短路算法有個(gè)全面的了解
文章講解

算法選擇的場(chǎng)景分析總結(jié)

1. 單源最短路徑僚碎，且邊權(quán)為正：

   • 優(yōu)先選擇：Dijkstra算法猴娩。
   • 具體實(shí)現(xiàn)：
     • 樸素版Dijkstra適用于圖較稠密的情況。
     • 堆優(yōu)化版Dijkstra適用于圖較稀疏的情況勺阐。
   • 稠密度判斷：稠密圖和稀疏圖的具體劃分沒(méi)有嚴(yán)格的量化標(biāo)準(zhǔn)卷中，通常可以通過(guò)實(shí)驗(yàn)對(duì)比樸素版和堆優(yōu)化版Dijkstra的性能來(lái)判斷渊抽。

2. 單源最短路徑蟆豫，邊權(quán)可以為負(fù)：

   • 優(yōu)先選擇：Bellman-Ford算法。
   • 具體實(shí)現(xiàn)：
     • Bellman-Ford適用于圖較稠密的情況懒闷。
     • SPFA（Shortest Path Faster Algorithm）適用于圖較稀疏的情況十减。
   • 一般推薦：通常情況下，優(yōu)先使用SPFA愤估，因?yàn)樗诖蟛糠智闆r下比Bellman-Ford更快帮辟。

3. 存在負(fù)權(quán)回路或有限節(jié)點(diǎn)最短路徑問(wèn)題：

   • 優(yōu)先選擇：Bellman-Ford算法。
   • 理由：Bellman-Ford能夠檢測(cè)負(fù)權(quán)回路灵疮，并且代碼實(shí)現(xiàn)相對(duì)簡(jiǎn)單织阅，適合處理復(fù)雜的路徑問(wèn)題。

4. 多源最短路徑：

   • 優(yōu)先選擇：Floyd-Warshall算法震捣。
   • 例外情況：如果源點(diǎn)非常少且邊權(quán)為正荔棉，可以使用多次Dijkstra來(lái)求解闹炉，但這種情況較少見(jiàn)，多源問(wèn)題通常直接適用于Floyd-Warshall算法润樱。

5. A算法的應(yīng)用場(chǎng)景*：

   • 廣泛使用：A*算法由于其高效性渣触，廣泛應(yīng)用于實(shí)際工程中，例如游戲開(kāi)發(fā)壹若、地圖導(dǎo)航嗅钻、數(shù)據(jù)包路由等。
   • 注意事項(xiàng)：A*算法的結(jié)果不一定是唯一的店展，可能會(huì)得到次短路徑养篓，因此在算法競(jìng)賽中較少使用，更多應(yīng)用于實(shí)際工程需求中赂蕴。

總結(jié)

• Dijkstra：用于單源正權(quán)圖柳弄。
• Bellman-Ford和SPFA：用于單源負(fù)權(quán)圖，尤其是Bellman-Ford適用于檢測(cè)負(fù)權(quán)回路概说。
• Floyd-Warshall：用于多源最短路徑問(wèn)題碧注。
• A算法*：適用于實(shí)際工程中的路徑搜索需求，尤其是在需要高效搜索但不要求唯一最短路徑的場(chǎng)景糖赔。

圖論總結(jié)

文章講解