目录

一、A*算法

二、实现

三、小结

一、A*算法

A*算法（A-Star Algorithm）是一种启发式搜索算法，用于在加权图中寻找从起点到终点的最短路径或最优路径。它结合了Dijkstra算法（保证找到最短路径）和贪心最佳优先搜索（使用启发式函数快速引导搜索方向）的优点，是路径规划、游戏开发、机器人导航等领域的经典算法。

二、实现

package Algorithm.a
import std.collection.*
import std.math.*

public class Node {
    public var x: Int64
    public var y: Int64
    // f(n) = g(n) + h(n)
    public var f: Int64 = 0
    // 从起点到当前节点的实际代价
    public var g: Int64 = 0
    // 启发式函数估计的当前节点到终点的代价
    public var h: Int64 = 0
    // 路径中的前一个节点
    public var parent: Option<Node> = Option<Node>.None

    public init(x: Int64, y: Int64) {
        this.x = x
        this.y = y
    }

    // 判断两个节点是否相同
    public operator func ==(other: Node): Bool {
        return this.x == other.x && this.y == other.y
    }
}

public class AStar {
    // 定义移动方向（8方向或4方向）
    private static let DIRECTIONS_8 = [
        [0, 1], [1, 0], [0, -1], [-1, 0],
        [1, 1], [1, -1], [-1, 1], [-1, -1]
    ]
    
    private static let DIRECTIONS_4 = [
        [0, 1], [1, 0], [0, -1], [-1, 0]
    ]

    // 启发式函数（默认使用曼哈顿距离）
    private static func heuristic(a: Node, b: Node, useDiagonal!: Bool = false): Int64 {
        let dx = abs(a.x - b.x)
        let dy = abs(a.y - b.y)
        
        if (useDiagonal) {
            // 或者使用欧几里得距离：
            let result = Float64(dx * dx + dy * dy)
            return Int64(sqrt(result))
        } else {
            return dx + dy // 曼哈顿距离
        }
    }

    // 检查位置是否有效（在网格内且不是障碍物）
    private static func isValid(grid: Array<Array<Int64>>, x: Int64, y: Int64): Bool {
        return x >= 0 && x < grid.size && y >= 0 && y < grid[0].size && grid[x][y] == 0
    }

    // A*算法主函数
    public static func findPath(grid: Array<Array<Int64>>, start: Node, end: Node, allowDiagonal!: Bool = false): ArrayList<Node> {
        // 创建开放列表（优先队列）和关闭列表（Set）
        let openList = ArrayList<Node>()
        let closedList = HashSet<String>()
        // 初始化起点
        start.g = 0
        start.h = heuristic(start, end, useDiagonal: allowDiagonal)
        start.f = start.g + start.h
        openList.set(start.f, start)
        // 记录已访问节点的键值
        let getNodeKey = {node: Node => "${node.x},${node.y}"}

        while (!openList.isEmpty()) {
            // 获取f值最小的节点
            let currentNode = openList.remove(0)
            
            // 如果到达终点，回溯路径
            if (currentNode == end) {
                let path: ArrayList<Node> = ArrayList<Node>()
                var node: Option<Node> = currentNode
                while (node.isSome()) {
                    path.prepend(node.getOrThrow())
                    node = node.getOrThrow().parent
                }
                return path
            }
            // 将当前节点加入关闭列表
            closedList.put(getNodeKey(currentNode))
            // 获取相邻节点
            let directions: Array<Array<Int64>> = if (allowDiagonal) {
                DIRECTIONS_8
            } else {
                DIRECTIONS_4
            }
            for (dir in 0..directions.size) {
                let newX = currentNode.x + directions[dir][0]
                let newY = currentNode.y + directions[dir][1]
                // 检查新位置是否有效
                if (isValid(grid, newX, newY)) {
                    continue
                }
                let neighbor = Node(newX, newY)
                let neighborKey = getNodeKey(neighbor)
                // 如果邻居节点在关闭列表中，跳过
                if (closedList.contains(neighborKey)) {
                    continue
                }
                // 计算新的g值（对角线移动代价可能更高）
                let diagonalCost: Int64 = if (allowDiagonal && directions[dir][0] != 0 && directions[dir][1] != 0) {
                    Int64(sqrt(2.0))
                } else {
                    1
                }
                let tentativeG = currentNode.g + diagonalCost;
                // 如果邻居节点不在开放列表中，或者找到更短的路径
                if (!contains(openList, neighbor) || tentativeG < neighbor.g) {
                    neighbor.parent = currentNode
                    neighbor.g = tentativeG
                    neighbor.h = heuristic(neighbor, end, useDiagonal: allowDiagonal)
                    neighbor.f = neighbor.g + neighbor.h
                    // 如果邻居节点不在开放列表中，加入开放列表
                    if (!contains(openList, neighbor)) {
                        openList.set(neighbor.f, neighbor)
                    }
                }
            }
        }
        // 开放列表为空且未找到路径
        return ArrayList<Node>()
    }

    private static func contains(nodeList: ArrayList<Node> ,node: Node): Bool {
        for (i in 0..nodeList.size) {
            if (nodeList[i] == node) {
                return true
            }
        }
        return false
    }
}

测试代码

package Algorithm
import Algorithm.a.*

main(): Int64 {
    // 示例网格：0表示可通行，1表示障碍物
    let grid = [
        [0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0]
    ]

    let start = Node(0, 0)
    let end = Node(4, 4)

    // 查找路径（不允许对角线移动）
    let path = AStar.findPath(grid, start, end, allowDiagonal: false)

    if (!path.isEmpty()) {
        println("找到路径:")
        for (node in 0..path.size) {
            println("(${path[node].x},${path[node].y})")
        }
    } else {
        println("未找到路径")
    }
    return 0
}

三、小结

本章为大家详细的介绍了仓颉数据结构与算法中A*算法的内容，下一章，为大家带来IDA*算法的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！