2023面试题个人最短路径算法优化

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

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

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

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

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

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

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

​

代码示例：

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的回溯元素优化

  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);

​