理論

概念

啟發(fā)式搜索(Heuristically Search)又稱為有信息搜索(Informed Search)，它是利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少搜索范圍、降低問題復(fù)雜度的目的，這種利用啟發(fā)信息的搜索過程稱為啟發(fā)式搜索。

估價(jià)函數(shù)

啟發(fā)式函數(shù)： h(n)，它用來評價(jià)哪些結(jié)點(diǎn)最有希望的是一個(gè)我們要找的結(jié)點(diǎn)，h(n) 會(huì)返回一個(gè)非負(fù)實(shí)數(shù),也可以認(rèn)為是從結(jié)點(diǎn)n的目標(biāo)結(jié)點(diǎn)路徑的估計(jì)成本。
注意：估價(jià)函數(shù)的選取十分重要，會(huì)直接影響到算法的效率。

代碼模板

有點(diǎn)類似于bfs，但這里使用的是優(yōu)先隊(duì)列，估價(jià)函數(shù)即優(yōu)先級。

def AstarSearch(graph, start, end): 
    pq = collections.priority_queue() # 優(yōu)先級 —> 估價(jià)函數(shù)
    pq.append([start]) 
    visited.add(start) 
    while pq: 
        node = pq.pop() # can we add more intelligence here ? 
        visited.add(node) 
        process(node) 
        nodes = generate_related_nodes(node) 
        unvisited = [node for node in nodes if node not in visited] 
        pq.push(unvisited)

算法實(shí)踐

1091. 二進(jìn)制矩陣中的最短路徑

問題描述

給你一個(gè) n x n 的二進(jìn)制矩陣 grid 中，返回矩陣中最短 暢通路徑 的長度。如果不存在這樣的路徑，返回 -1 。

二進(jìn)制矩陣中的 暢通路徑 是一條從 左上角 單元格（即，(0, 0)）到 右下角 單元格（即，(n - 1, n - 1)）的路徑，該路徑同時(shí)滿足下述要求：

• 路徑途經(jīng)的所有單元格的值都是 0 。
• 路徑中所有相鄰的單元格應(yīng)當(dāng)在 8 個(gè)方向之一 上連通（即，相鄰兩單元之間彼此不同且共享一條邊或者一個(gè)角）。
  暢通路徑的長度 是該路徑途經(jīng)的單元格總數(shù)。

示例

解題思路

先準(zhǔn)備好8個(gè)方向的變化變量，然后從(0,0)開始進(jìn)行類bfs搜索，使用優(yōu)先隊(duì)列，估價(jià)函數(shù)為：到當(dāng)前位置花費(fèi)的成本 + x/y坐標(biāo)和上一個(gè)位置差的絕對值的最大值。

代碼示例

class Solution {
    int len = 0;
    int[][] directions = new int[][]{{-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        len = grid.length;
        if (grid[0][0] == 1 || grid[len - 1][len - 1] == 1) {
            return -1;
        }
        if (len == 1) {
            return 1;
        }

        Queue<Node> queue = new PriorityQueue<>(10, Comparator.comparingInt(Node::cost));
        queue.offer(new Node(0, 0, 1));
        grid[0][0] = 1;
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            for (int i = 0; i < directions.length; i++) {
                int x = current.x + directions[i][0];
                int y = current.y + directions[i][1];
                if (x == len - 1 && y == len - 1) {
                    return current.step + 1;
                }
                if (x < 0 || x >= len || y < 0 || y >= len) {
                    continue;
                }
                if (grid[x][y] == 0 || grid[x][y] > grid[current.x][current.y] + 1) {
                    grid[x][y] = current.step + 1;
                    Node newNode = new Node(x, y, grid[x][y]);
                    queue.add(newNode);
                }
            }
        }
        return -1;
    }

    class Node {
        public int x;
        public int y;
        public int step;

        public Node() {
        }

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

        public int cost() {
            return step + Math.max(Math.abs(len - x - 1), Math.abs(len - y - 1));
        }
    }
}