[算法]-最短路径算法总结「建议收藏」

[算法]-最短路径算法总结「建议收藏」Dijkstra最短路径算法按路径长度的递增次序,逐步产生最短路径的贪心算法基本思想:首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从顶点v到其它各顶点的最短路径全部求出为止。时间复杂度为O(n2)算法流程:首先选定源点1,建立邻接矩阵C[5][5],初始化三个数组分别为D[n],P[n],S[n],分别用来存储从源点到对应点的最短距离和最短路…

大家好,又见面了,我是你们的朋友全栈君。

Dijkstra最短路径算法

按路径长度的递增次序,逐步产生最短路径的贪心算法

基本思想:首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从顶点v 到其它各顶点的最短路径全部求出为止。

时间复杂度为O(n2)

算法流程:
在这里插入图片描述

  1. 首先选定源点1,建立邻接矩阵C[5] [5],初始化三个数组分别为D[n],P[n],S[n],分别用来存储从源点到对应点的最短距离和最短路径上到该序列节点的前序节点,以及是否已经找到最短路径。
  2. 开始遍历源点的出边,将邻接矩阵的第一行放入数组D,找出距离最小的节点序号2,将数组P中的P[2]置为1,因为2的前序节点为1。
  3. 以上一步骤找到的节点为起点,继续遍历其邻接点(此处为2),若C[1][2]+C[2][m]<D[m] 则将其替换进数组D中,并将数组P中的P[m]置为2,因为m最短路径上的前序节点为2,节点2的邻接点全部遍历完成后,再从数组D中找出值最小且未被选中过的节点
  4. 重复以上步骤3,直到所有点都已经加入到数组S中。
    在这里插入图片描述

程序实现:

public class Dijikstra extends Strategy {

  // open表
  Map<Integer, Node> open = new HashMap<>();
  // close表
  Map<Integer, Node> close = new HashMap<>();
  // 动作列表
  int[][] motion = get_motion();

  @Override
  public List<Location> nextstep(Location start, Location work) {
    Node startnode = new Node(start.getX(), start.getY(), 0, -1);
    Node worknode = new Node(work.getX(), work.getY(), 0, -1);

    // 将起点放入open表
    open.put(cal_grid_index(startnode), startnode);
    // 向起点的上下左右四个方向扩展
    while (true) {

      // 与Astar算法不同 A*算法含有启发式函数 可以保证更快找到目标点
      // 但A*算法有可能永远无法找到目标点
      // Dijikstra算法虽然较慢 会遍历全部方向的点 但一定可以找到一条到目标点的路径

      // 找到map中节点cost最小的元素
      int temp_cost = Integer.MAX_VALUE;
      int current_id = 0;
      Node current = null;
      for (Map.Entry<Integer, Node> entry : open.entrySet()) {
        int current_cost =
            entry.getValue().cost + cal_Manhattan_distance(entry.getValue(), worknode);
        if (current_cost < temp_cost) {
          current_id = entry.getKey();
          temp_cost = current_cost;
          current = entry.getValue();
        }
      }
      // 判断是否找到目标点
      if (current.x == work.getX() && current.y == work.getY()) {
        System.out.println("找到目标点!");
        worknode.pind = current.pind;
        worknode.cost = current.cost;
        break;
      }
      // 移除open表中的current节点
      for (Iterator<Integer> iterator = open.keySet().iterator(); iterator.hasNext();) {
        Integer key = iterator.next();
        if (key == current_id) {
          iterator.remove();
        }
      }

      // 将current节点放入close表中
      close.put(current_id, current);
      for (int i = 0; i < motion.length; i++) {
        Node node = new Node(current.x + motion[i][0], current.y + motion[i][1],
            current.cost + motion[i][2], current_id);
        int node_id = cal_grid_index(node);
        // 该节点不能被扩展
        if (!verify_node(node)) {
          continue;
        }
        // 该节点已被确认过
        if (close.containsKey(node_id)) {
          continue;
        }
        // 将新扩展节点放入open表中
        if (!open.containsKey(node_id)) {
          open.put(node_id, node);
        } else {
          // 更新open表
          if (open.get(node_id).cost > node.cost) {
            open.put(node_id, node);
          }
        }
      }
    }
    open.clear();
    return cal_final_path(worknode, close);
  }

  /**
   * 根据终点回溯计算最短路径
   * 
   * @param worknode
   * @param close
   * @return
   */
  private List<Location> cal_final_path(Node worknode, Map<Integer, Node> close) {
    List<Location> ans = new ArrayList<>();
    int pind = worknode.pind;
    int i = 0;
    while (pind != -1) {
      // System.out.println(i);
      Node node = close.get(pind);
      Location location = new Location(node.x, node.y);
      ans.add(location);
      pind = node.pind;
    }
    return ans;
  }

  /**
   * 计算曼哈顿距离
   * 
   * @param now
   * @param end
   * @return
   */
  private int cal_Manhattan_distance(Node now, Node end) {
    return Math.abs(now.x - end.x) + Math.abs(now.y - end.y);
  }

  /**
   * 判断节点是否合理 1. 是否超出范围 2. 是否遇到货柜
   * 
   * @param node
   * @return
   */
  private boolean verify_node(Node node) {
    Container[][] map = ContainerMap.getMap();
    if (node.x < 0 || node.x >= ContainerMap.N || node.y < 0 || node.y >= ContainerMap.N) {
      return false;
    }
    if (map[node.x][node.y] != null) {
      return false;
    }
    return true;
  }

  /**
   * 计算栅格地图中的线性坐标
   * 
   * @param node
   * @return
   */
  private int cal_grid_index(Node node) {
    return node.y * ContainerMap.N + node.x;
  }

  /**
   * 定义动作及其代价 motion = {dx, dy, cost}
   * 
   * @return
   */
  private int[][] get_motion() {
    int[][] motion = {
  
  {1, 0, 1}, {0, 1, 1}, {-1, 0, 1}, {0, -1, 1}};
    return motion;
  }
}

A*算法

利用A*算法在拓扑地图上实现的路径规划:
关键:代价函数

  • 对于任意节点n
    • g(n)=从树根到n的代价
    • h*(n)=从n到目标节点的优化路径的代价
    • f*(n)=g(n) + h*(n)是节点n的代价
  • 估计h*(n)
    • 使用任何方法去估计h*(n), 用h(n)表示h*(n)的估计
    • h(n) <= h*(n)总为真
    • f(n)=g(n)+h(n) <= g(n)+h*(n)=f*(n)定义为n的代价

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

利用A*算法在栅格地图上实现的路径规划:
A*算法的核心思想是通过设置代价函数对未遍历点进行筛选,使搜索方向更偏向目标点,缩小搜索范围,进而提升搜索速度。公式f(n)=g(n)+h(n)是路径成本表达式。其中,f(n)为起点P—遍历中间点n—目标点g的路径总成本;g(n)为起点P—遍历中间点n之间的实际路径成本;h(n)为遍历中间点n—目标点Q的预估路径成本。寻找到最优解的条件是f(n)尽可能接近起点P到目标点Q的真实路径成本,此时搜寻到的点都是最短路径的过程点。由于遍历中间点n的g(n)值己知,因此只能提升h(n)的估计准确性,根据AGV在作业环境中只有“上下左右”四个行走方向,所以选取 h(n) = |Xn – XQ|+|Yn – YQ| (即曼哈顿距离),
算法流程描述如下:
(1)新建两个列表用作路径数据点存储:open list和close list,open list初始默认包含路径起点;
(2)计算与起点相邻的节点的f(n),按数值大小进行排序,f(n)最小的节点m转移到close list作为当前最优路径过程点,其余点留在open list中做备选点。
(3)若m为目标点,则停止搜索,并输出最优路径结果,否则继续;
(4)计算遍历中间栅格点m的所有相邻栅格点的f(n),若相邻节点n未加入open list,及时添加,并令g(n) = g(m) + d(m,n),此时n的父节点为m;若相邻点n在open list中,当g(n) > g(m) + d(m,n)时,更新g(n) = g(m) + d(m,n),设置n的父节点为m;
(5)遍历完所有备选点后重复步骤(2)-(4),直到目标点Q出现在open list中,搜索结束,按进入closed list的先后顺序输出中的节点栅格序列,该序列即为最优路径。

程序实现:

public class Astar extends Strategy {

  // open表
  Map<Integer, Node> open = new HashMap<>();
  // close表
  Map<Integer, Node> close = new HashMap<>();
  // 动作列表
  int[][] motion = get_motion();

  @Override
  public List<Location> nextstep(Location start, Location work) {
    Node startnode = new Node(start.getX(), start.getY(), 0, -1);
    Node worknode = new Node(work.getX(), work.getY(), 0, -1);

    // 将起点放入open表
    open.put(cal_grid_index(startnode), startnode);
    // 向起点的上下左右四个方向扩展
    while (true) {
      if (open.size() == 0) {
        System.out.println("open表空!查找失败!");
        break;
      }
      // 找到map中节点cost最小的元素
      int temp_cost = Integer.MAX_VALUE;
      int current_id = 0;
      Node current = null;
      for (Map.Entry<Integer, Node> entry : open.entrySet()) {
        int current_cost =
            entry.getValue().cost + cal_Manhattan_distance(entry.getValue(), worknode);
        if (current_cost < temp_cost) {
          current_id = entry.getKey();
          temp_cost = current_cost;
          current = entry.getValue();
        }
      }
      // 判断是否找到目标点
      if (current.x == work.getX() && current.y == work.getY()) {
        System.out.println("找到目标点!");
        worknode.pind = current.pind;
        worknode.cost = current.cost;
        break;
      }
      // 移除open表中的current节点
      for (Iterator<Integer> iterator = open.keySet().iterator(); iterator.hasNext();) {
        Integer key = iterator.next();
        if (key == current_id) {
          iterator.remove();
        }
      }

      // 将current节点放入close表中
      close.put(current_id, current);
      for (int i = 0; i < motion.length; i++) {
        Node node = new Node(current.x + motion[i][0], current.y + motion[i][1],
            current.cost + motion[i][2], current_id);
        int node_id = cal_grid_index(node);

        // 该节点不能被扩展则查找下一个节点
        if (!verify_node(node)) {
          continue;
        }
        // 该节点已被确认过则查找下一个节点
        if (close.containsKey(node_id)) {
          continue;
        }

        // 将新扩展节点放入open表中
        if (!open.containsKey(node_id)) {
          open.put(node_id, node);
        } else {
          // 更新节点的代价
          if (open.get(node_id).cost > node.cost) {
            open.put(node_id, node);
          }
        }
      }
    }
    open.clear();
    return cal_final_path(worknode, close);
  }

  /**
   * 根据终点回溯计算最短路径
   * 
   * @param worknode
   * @param close
   * @return
   */
  private List<Location> cal_final_path(Node worknode, Map<Integer, Node> close) {
    List<Location> ans = new ArrayList<>();
    int pind = worknode.pind;
    int i = 0;
    while (pind != -1) {
      // System.out.println(i);
      Node node = close.get(pind);
      Location location = new Location(node.x, node.y);
      ans.add(location);
      pind = node.pind;
    }
    return ans;
  }

  /**
   * 计算曼哈顿距离
   * 
   * @param now
   * @param end
   * @return
   */
  private int cal_Manhattan_distance(Node now, Node end) {
    return Math.abs(now.x - end.x) + Math.abs(now.y - end.y);
  }

  /**
   * 判断节点是否合理 1. 是否超出范围 2. 是否遇到货柜
   * 
   * @param node
   * @return
   */
  private boolean verify_node(Node node) {
    Container[][] map = ContainerMap.getMap();
    if (node.x < 0 || node.x >= ContainerMap.N || node.y < 0 || node.y >= ContainerMap.N) {
      return false;
    }
    if (map[node.x][node.y] != null) {
      return false;
    }
    return true;
  }

  /**
   * 计算栅格地图中的线性坐标
   * 
   * @param node
   * @return
   */
  private int cal_grid_index(Node node) {
    return node.y * ContainerMap.N + node.x;
  }

  /**
   * 定义动作及其代价 motion = {dx, dy, cost}
   * 
   * @return
   */
  private int[][] get_motion() {
    int[][] motion = {
  
  {1, 0, 1}, {0, 1, 1}, {-1, 0, 1}, {0, -1, 1}};
    return motion;
  }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/141010.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 代理服务器调研[通俗易懂]

    代理服务器调研[通俗易懂]1.名词解释:代理服务器是一种重要的服务器安全功能,它的工作主要在开放系统互联(OSI)模型的会话层,从而起到防火墙的作用。代理服务器大多被用来连接国际互联网和局域网。2.相关概念(1)代理也称网络代理,是一种特殊的网络服务,允许一个网络终端(一般为客户端)通过这个服务与另一个网络终端(一般为服务器)进行非直接的连接。一些网关、路由器等网络设备具备网络代理功能。一般认为代理服务有利于保

  • javascript(js)小数精度丢失的解决方案

    原因:js按照2进制来处理小数的加减乘除,在arg1的基础上将arg2的精度进行扩展或逆扩展匹配,所以会出现如下情况.javascript(js)的小数点加减乘除问题,是一个js的bug如0.3*

    2021年12月25日
  • java中高级工程师面试汇总

    java中高级工程师面试汇总1接口服务数据被劫包如何防止数据恶意提交1.1:防篡改客户端提交请求之前,先对自己请求的参数全部进行拼接加密得到一个加密字符串sign 请求参数加上sign,然后再发送给服务器 服务器将参数获取后也进行相同的拼接加密得到自己的sign 比较与客户端发来的sign是否相同 不相同则是被第三方修改过的,拒绝执行关键:第三方不知道加密方式和请求参数拼接规则,而客户端与服务器是知道的,因此第三方不知道修改参数后如何生成与服务器生成相同的sign 只要请求修改了一点点加密得到的就是不同的签名

  • 数据库压缩备份提高备份效率

    数据库压缩备份提高备份效率

    2021年11月26日
  • docker deepin_docker套件用法

    docker deepin_docker套件用法卸载1.卸载docker-cesudoapt-getremovedockerdocker-ce2.查看docker的文件位置whereisdocker结果如下:docker:/usr/bin/docker/etc/docker/usr/libexec/docker/usr/share/man/man1/docker.1.gz3.删除docker文件使用rm-rf命令删除这些文件如:sudorm-rf/usr/bin/docker删除后,可以使用dock

  • 重写finalize方法_Java的finalize方法干什么

    重写finalize方法_Java的finalize方法干什么Finalize方法在未能调用Dispose方法的情况下充当防护措施来清理资源。您应该只实现Finalize方法来清理非托管资源。Object.Finalize方法的范围是受保护的。当在类中重写该方法时,您应该保持这个有限的范围。您无法从C#或C++编程语言的托管扩展中调用或重写Object.Finalize方法。C#和托管扩展提供析构函数作为编写终止代码的机制。在

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号