A* Algorithm

A* Algorithm

·

6 min read

Let's see the leetcode problem Cut Off Trees for Golf Event. Even though it is a hard problem, but actually it is not very hard. So walk with me to see how to solve this.

The problem want us to cut all the tree with order from low to high and return the minimum steps need to walk to finish the task. So this is a graph shortest path problem. Instead of calculate one shortest path, but to calculate many times.

So from the general view, what we will do is sort the trees with ascending order and calculate shortest path one by one.

function cutOffTree(forest: number[][]): number {

    const trees: number[][] = [];
    for (let i = 0; i < forest.length; i++) {
        for (let j = 0; j < forest[i].length; j++) {
            if (forest[i][j] > 1) {
                trees.push([i, j, forest[i][j]]);
            }
        }
    }
    trees.sort((t1, t2) => t1[2] - t2[2]);

    let totalSteps = 0;
    let source = [0, 0];

    for (const [x, y, _] of trees) {
        const destination = [x, y];
        const steps = shortestSteps(forest, source, destination);
        if (steps === -1) return -1;

        totalSteps += steps;
        source = destination;
    }

    return totalSteps;
};

So now the problem becomes how to calculate shortest path from source to destination.

The most general solution for this is just use BFS. Let's see it first.

function shortestSteps(forest: number[][], source: number[], destination: number[]): number {
    const [sourceX, sourceY] = source;
    const [destinationX, destinationY] = destination;
    const m = forest.length;
    const n = forest[0].length;

    let queue = [[sourceX, sourceY, 0]];
    const options = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = forest.map(row => row.map(_ => false));
    visited[sourceX][sourceY] = true;

    while (true) {

        const co = queue.shift();
        if (co === undefined) break;

        const [currentX, currentY, steps] = co;
        if (currentX === destinationX && currentY === destinationY) {
            return steps;
        }

        for (const [moveX, moveY] of options) {
            const nextX = currentX + moveX;
            const nextY = currentY + moveY;
            if (nextX < 0 || nextY < 0) continue;
            if (nextX >= m || nextY >= n) continue;
            if (forest[nextX][nextY] === 0) continue;
            if (visited[nextX][nextY]) continue;
            visited[nextX][nextY] = true;
            queue.push([nextX, nextY, steps + 1]);
        }
    }

    return -1;
}

It is just a standard BFS process. Then we have to think about how to optimize this.

We may consider to use Dijkstra's algorithm, because we know Dijkstra's algorithm is a shortest path algorithm. I wrote an article about it before, if you don't familar with it, feel free to check the article first.

So, can we use Dijkstra's algorithm to solve this problem? Of course we can. The process goes like below. (I emit the heap implementation, check my previous article about it).

function shortestSteps(forest: number[][], source: number[], destination: number[]): number {
    const [sourceX, sourceY] = source;
    const [destinationX, destinationY] = destination;
    const m = forest.length;
    const n = forest[0].length;

    const h = [[sourceX, sourceY, 0] as Val];
    const options = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = forest.map(row => row.map(_ => false));
    visited[sourceX][sourceY] = true;

    while (true) {
        const co = heapq.heappop(h);
        if (co === undefined) break;

        const [currentX, currentY, steps] = co;

        if (currentX === destinationX && currentY === destinationY) {
            return steps;
        }

        for (const [moveX, moveY] of options) {
            const nextX = currentX + moveX;
            const nextY = currentY + moveY;

            if (nextX < 0 || nextY < 0) continue;
            if (nextX >= m || nextY >= n) continue;
            if (forest[nextX][nextY] === 0) continue;

            if (visited[nextX][nextY]) continue;
            visited[nextX][nextY] = true;

            heapq.heappush(h, [nextX, nextY, steps + 1])
        }
    }

    return -1;
}

As you can see, for normal BFS, we choose the next node with a queue logic. In Dijkstra's algorithm, we choose the next node which has the minimum steps in the heap. Because in this problem, every move have the same weight(1), so Dijkstra's algorithm really doesn't have much effect here.

Based on Dijkstra's algorithm, an algorithm called a* algorithm is created, whicn can be used to solve this problem and speed up a lot.

As I just said, in Dijkstra's algorithm, we choose the next node which has the miminum steps. In a* algorithm, instead of only using steps as the ordering factor, we also use some other heuristic function.

Consider this problem, not only we want to know the shortest path, we also want to make the process faster. So instead of only choosing the currently shortest node, we also considering the distance between current node and destination node. So basically, we want to move toward the destination sooner.

So how to calculate the distance? The manhattan is the most simple way.

function manhattan(source: number[], destination: number[]) {
    return Math.abs(source[0] - destination[0]) + Math.abs(source[1] - destination[1]);
}

Then we make this manhanttan distance as another factor for choosing the next node. So the basic process is almost similiar with the Dijkstra's algorithm, let's implement it.

function shortestSteps(forest: number[][], source: number[], destination: number[]): number {
    const [sourceX, sourceY] = source;
    const [destinationX, destinationY] = destination;
    const m = forest.length;
    const n = forest[0].length;

    const h = [[sourceX, sourceY, manhattan(source, destination), 0] as Val];
    const options = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = Array.from({ length: m }, _ => Array.from({ length: n }, _ => false));
    visited[sourceX][sourceY] = true;

    while (true) {
        const co = heapq.heappop(h);
        if (co === undefined) break;

        const [currentX, currentY, _, steps] = co;

        if (currentX === destinationX && currentY === destinationY) {
            return steps;
        }

        for (const [moveX, moveY] of options) {
            const nextX = currentX + moveX;
            const nextY = currentY + moveY;

            if (nextX < 0 || nextY < 0) continue;
            if (nextX >= m || nextY >= n) continue;
            if (forest[nextX][nextY] === 0) continue;
            if (visited[nextX][nextY]) continue;
            visited[nextX][nextY] = true;

            heapq.heappush(h, [
                nextX,
                nextY,
                steps + 1 + manhattan([nextX, nextY], destination), // add manhattan distance as another factor
                steps + 1
            ]);
        }
    }

    return -1;
}

So in this way, we will incline to choose the node near the destination, so the process will be faster.

But another thing need to be noted here. In a* star algorithm, it is possible the the heap ordering factor can be equal. So when they are equal, we don't want the result to be random. We need the heap to rely on the steps factor again. So a little change to the heap implementation as below.


type Val = [number, number, number, number];

class heapq {
    public static heapify(nums: Val[]) {
        for (let i = nums.length - 1; i >= 0; i--) {
            heapq._heapify(nums, i);
        }
    }

    public static heappush(nums: Val[], val: Val) {
        nums.push(val);
        heapq._swapWithParent(nums, nums.length - 1);
    }

    public static heappop(nums: Val[]): Val {
        const res = nums[0];
        nums[0] = nums[nums.length - 1];
        nums.splice(nums.length - 1, 1);
        heapq._heapify(nums, 0);
        return res;
    }

    private static _swapWithParent(nums: Val[], index: number) {
        if (index === 0) return;
        const parentIndex = Math.trunc((index - 1) / 2);
        // change is here
        if (
            (
                nums[index][2] !== nums[parentIndex][2] &&
                nums[index][2] < nums[parentIndex][2]
            ) || (
                nums[index][2] === nums[parentIndex][2] &&
                nums[index][3] < nums[parentIndex][3]
            )
        ) {
            [nums[index], nums[parentIndex]] = [nums[parentIndex], nums[index]];
            heapq._swapWithParent(nums, parentIndex);
        }
    }

    private static _heapify(nums: Val[], index: number) {
        const leftChildIndex = index * 2 + 1;
        const rightChildIndex = index * 2 + 2;

        let minValueIndex = index;
        if (leftChildIndex < nums.length) {
            // change is here
            if (
                nums[leftChildIndex][2] < nums[minValueIndex][2] || (
                    nums[leftChildIndex][2] === nums[minValueIndex][2] &&
                    nums[leftChildIndex][3] < nums[minValueIndex][3]
                )
            ) {
                minValueIndex = leftChildIndex;
            }
        }
        if (rightChildIndex < nums.length) {
            // change is here
            if (
                nums[rightChildIndex][2] < nums[minValueIndex][2] || (
                    nums[rightChildIndex][2] === nums[minValueIndex][2] &&
                    nums[rightChildIndex][3] < nums[minValueIndex][3]
                )
            ) {
                minValueIndex = rightChildIndex;
            }
        }

        if (minValueIndex !== index) {
            [nums[index], nums[minValueIndex]] = [nums[minValueIndex], nums[index]];
            heapq._heapify(nums, minValueIndex);
        }
    }
}