前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >个人最短路径算法优化

个人最短路径算法优化

原创
作者头像
疯狂的KK
发布2023-04-12 15:20:17
9910
发布2023-04-12 15:20:17
举报
文章被收录于专栏:Java项目实战

只针对个人写的业务最短路径的算法优化

原代码逻辑见文章:回溯算法在项目中的实际应用 - 腾讯云开发者社区-腾讯云 (tencent.com)

当第一次选择开始的客户点为N-0个,不能重复计算...

当第二次选择开始的客户点为N-1个,不能重复计算...

当第三次选择开始的客户点为N-2个,不能重复计算...

终止条件为满足排列组合等于当前数组的长度...

或者可以用多层map去判断,当第一层时为map不包含全部数字,然后向下,当第二层时为map不包含全部数字,直到第[数组长度]层,向上返回,向上返回一层时把当前层已选择的数字从map中去掉,如果向上返回时的数字仍有下层节点则接着遍历,如果没有接着向上返回,直到返回到根节点为止。如图

代码示例:

代码语言:javascript
复制
function  getDistance(int[] nums)   ->[[][],[][],[][]]{

      result = new ArrayList<List<Integer>>();
      
       cur   = new ArrayList<Integer>();
      for(int num :nums){
       cur.add(num);
      }
      backtracking(nums.length, cur, res, 0);
      
      }
      backtracking(int n, List<Integer> cur, List<List<Integer>> res, int index);{
      //终止条件
      if(result.length == n)
        res.add(new ArrayList<>(cur));
        return;
      for (int i = index; i < n; i++) {    
         if(res.contains(nums[i]))continue;
             cur.add(i);
            //向下一层
            backtracking(n,cur,res,index+1);
            //返回上一层是删除
             cur.removelast(); 
          }  
     } 

优化代码

1.针对逻辑判断的if语句优化

2.针对map的重复遍历优化

3.针对map的回溯元素优化

代码语言:javascript
复制
  private void backTracking(HashMap<String, String> map, String code, List<String> List) {
        if (map.isEmpty()) {
            return;
        }
        BigDecimal temp = BigDecimal.ZERO;
        String shortestRoute = null;
        for (Map.Entry<String, String> entry : map.entrySet()) {
            BigDecimal num = Utils.getDistance(code, entry.getValue()
                    , "", "",
                    "", "", "",
                    "", 1, 1,
                    1, "");
            if (temp.compareTo(BigDecimal.ZERO) == 0 || num .compareTo(temp) < 0) {
                temp = num ;
                shortestRoute = entry.getKey();
            }
        }
        if (shortestRoute != null) {
            code= map.get(shortestRoute);
            map.remove(shortestRoute);
            List.add(shortestRoute);
            log.info("开始送达至->{}", shortestRoute);
        }
        backTracking(map, code, List);

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云开发 CloudBase
云开发(Tencent CloudBase,TCB)是腾讯云提供的云原生一体化开发环境和工具平台,为200万+企业和开发者提供高可用、自动弹性扩缩的后端云服务,可用于云端一体化开发多种端应用(小程序、公众号、Web 应用等),避免了应用开发过程中繁琐的服务器搭建及运维,开发者可以专注于业务逻辑的实现,开发门槛更低,效率更高。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档