算法:A*算法最小实例

发布时间:2024年01月10日

A*算法主要作用是寻找两个节点之间的最短路径

首先,需要定义一个表示地图的二维数组,其中0表示可通过的空地,1表示障碍物:

const map = [
      [0, 0, 0, 0, 0],
      [0, 1, 1, 0, 0],
      [0, 0, 0, 0, 0],
      [0, 1, 0, 1, 0],
      [0, 0, 0, 0, 0]
    ];

接着,定义节点类,包含节点的坐标和计算曼哈顿距离的方法:

class Node {
   constructor(x, y) {
      this.x = x;
      this.y = y;
      this.g = 0; // 起点到当前节点的成本:从起始节点到当前节点的移动距离(父节点的g + 1)
      this.h = 0; // 当前节点到终点的预计成本:评估从此节点到目标节点成本最小路径,这里的预计成本使用曼哈顿距离(曼哈顿距离 = 两点的x轴距离 + 两点的y轴距离)
      this.f = 0; // 预计总成本:总成本最小的为最优路径(g + h)
      this.parent = null; // 当前节点的父节点,用于回溯最优路径
    }

    // 启发式函数:这里是计算当前节点到终点的曼哈顿距离
    calcHeuristic(target) {
      this.h = Math.abs(target.x - this.x) + Math.abs(target.y - this.y); 
    }
  }

接下来,定义A*算法的实现函数:

算法框架:

1.初始化开启列表和关闭列表。开始时,将起始节点添加到开启列表。

2.进入循环,直到开启列表为空或找到目标节点: 
  选取开启列表中的节点,该节点是根据启发式函数计算的最佳候选节点。
  将选定的节点从开启列表中移除,并将它添加到关闭列表中。

3.对于当前节点的所有可行相邻节点,计算它们的启发式函数值和代价函数值:
  如果相邻节点已经在关闭列表中,则忽略它并继续下一个节点。 
  如果相邻节点不在开启列表中,则将它添加到开启列表,并计算它的启发式函数值和代价函数值。 然后,将当前节点设置为该相邻节点的父节点。

4.如果相邻节点已经在开启列表中,比较当前路径代价和新计算的代价:    
  如果新计算的代价更小,则更新相邻节点的父节点为当前节点,并重新计算启发式函数值和代价函数值。 
  如果新计算的代价更大,则保持相邻节点的父节点不变。 

5.在循环结束后,如果找到了目标节点,则从目标节点回溯到起始节点,即可获得找到的最佳路径。

function aStar(start, target) {
      const openList = []; // 待探索的节点列表
      const closedList = []; // 已探索的节点列表

      openList.push(start);

      while (openList.length > 0) {
        // 在openList中选择评估值最小的节点
        let current = openList[0];
        let currentIndex = 0;
        for (let i = 1; i < openList.length; i++) {
          if (openList[i].f < current.f) {
            current = openList[i];
            currentIndex = i;
          }
        }

        // 如果当前节点是目标节点,说明路径已找到,进行回溯
        if (current.x === target.x && current.y === target.y) {
          let path = [];
          let temp = current;
          while (temp !== null) {
            path.push({ x: temp.x, y: temp.y });
            temp = temp.parent;
          }
          return path.reverse();
        }

        // 将当前节点从openList中移除,并加入closedList中
        openList.splice(currentIndex, 1);
        closedList.push(current);

        // 寻找当前节点的相邻节点
        const neighbors = [
          { x: current.x - 1, y: current.y },
          { x: current.x + 1, y: current.y },
          { x: current.x, y: current.y - 1 },
          { x: current.x, y: current.y + 1 }
        ];

        for (let neighbor of neighbors) {
          // 排除超出地图范围和障碍物的节点
          if (
            neighbor.x < 0 ||
            neighbor.x >= map.length ||
            neighbor.y < 0 ||
            neighbor.y >= map[0].length ||
            map[neighbor.x][neighbor.y] === 1
          ) {
            continue;
          }

          // 如果相邻节点已在closedList中,则跳过
          if (closedList.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
            continue;
          }

          let newG = current.g + 1; // 相邻节点的实际成本
          let neighborNode = openList.find(node => node.x === neighbor.x && node.y === neighbor.y);

          if (!neighborNode || newG < neighborNode.g) {
            // 如果相邻节点不在openList中或新的路径成本更低
            if (!neighborNode) {
              neighborNode = new Node(neighbor.x, neighbor.y);
              openList.push(neighborNode);
            }
            neighborNode.g = newG;
            neighborNode.calcHeuristic(target);
            neighborNode.f = neighborNode.g + neighborNode.h;
            neighborNode.parent = current;
          }
        }
      }

      return null; // 如果无法找到路径,返回null
    }

最后,我们可以使用上述函数来查找起点(0, 0)到目标点(4, 4)的最短路径:

    const startNode = new Node(0, 0);
    const targetNode = new Node(3, 4);
    startNode.calcHeuristic(targetNode);

    const path = aStar(startNode, targetNode);
    console.log(path); // 输出最短路径
文章来源:https://blog.csdn.net/weixin_41981909/article/details/135506703
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。