时间戳

首页 > 解决方案 > 找到二维数组的最小路径的算法问题

java - 找到二维数组的最小路径的算法问题

问题描述

问题：

有 10 人参加聚会。
每个人都有 0 - 9 级（输入的索引），并且在那里认识一些其他人。
你的工作是找到第 0 个人与第 9 个人见面的最便宜的方式。介绍的成本等于级别差异的平方。

目标：0 级的人希望用尽可能少的分数达到 9 级。
成本：级别差的平方
数组的索引表示级别（0-9）
，值是一个数组，每个人都知道其他人的索引。
请注意，关系是单向的（例如 2 可以将您介绍给 3，但反之亦然）例如最小成本：23 最小路径：[0, 1, 4, 6, 9]

 people = [
   [1, 2, 3],   # person 0 knows 1, 2, 3
   [8, 6, 4],   # person 1 knows 8, 6, 4
   [7, 8, 3],   # person 2 knows 7, 8, 3
   [8, 1],      # person 3 knows 8, 1
   [6],         # person 4 knows 6
   [8, 7],      # person 5 knows 8, 7
   [9, 4],      # person 6 knows 9, 4
   [4, 6],      # person 7 knows 4, 6
   [1],         # person 8 knows 1 
   [1, 4],      # person 9 knows 1, 4
 ]

我的解决方案：

使用优先队列并设置跟踪已经被访问的元素。基本上是广度优先搜索方法。我也将使用地图来跟踪水平。

我的问题

我尝试使用优先级队列，但无法使用队列遍历二维数组。我只涉及级别 0，而不涉及其他级别。以下是我尝试的解决方案

class Solution {
  public static void main(String[] args) {
    int[][] arr ={{1, 2, 3},
                  {8, 6, 4},
                  {7, 8, 3},
                  {8, 1},
                  {6},
                  {8,7},
                  {9, 4},
                  {4, 6},
                  {1},
                  {1,4}};
    
    Solution sol = new Solution();
    sol.meetUp(arr);
  }
  
  List<Integer> meetUp(int[][] arr) {
   if (arr == null || arr.length == 0)  {
     return new ArrayList<>();
  }
    
  Set<Integer> visited = new HashSet<>();
  PriorityQueue<MinQueue> pq = new PriorityQueue<>();
  Map<Integer, Integer> parentMap = new HashMap<>();
    
  pq.offer(new MinQueue(0, 0, arr[0][0]));
    
  while(!pq.isEmpty()) {
   MinQueue temp = pq.poll();
   int col = temp.col + 1;
   while (col < arr[temp.row].length) {
    if(!visited.contains(arr[temp.row][col])) {
     pq.offer(new MinQueue(temp.row, col, arr[temp.row][col])); 
     col += 1;
    }
  }
     
  if(!parentMap.containsKey(temp.row)) {
        parentMap.put(temp.row, temp.data);
      } else {
          int v = parentMap.get(temp.row);
          int n = (int)Math.pow(temp.data, 2) - (int)Math.pow(temp.row, 2);
          int o = (int)Math.pow(v, 2) - (int)Math.pow(temp.row, 2);
        if(n < o) {
          parentMap.put(temp.row, temp.data);
      }
    }
    visited.add(temp.data);
  }
    return new ArrayList<>();
  }
}

class MinQueue implements Comparable<MinQueue> {
  
   int data;
   int row;
   int col;
  
   MinQueue(int row, int col, int data) {
     this.row = row;
     this.col = col;
     this.data = data;
   }
  
  public int compareTo(MinQueue other) {
    if(this.data - other.data > 0) return 1;
    else if(this.data - other.data < 0) return -1;
    else return 0;
  }
}

标签： javapriority-queuebreadth-first-search

解决方案

您正在寻找通过有向图的最小成本路径。因此，Dijkstra 的算法就是您想要的。

这是一个针对您的任务定制的简单 Java 实现。如果不存在路径，则返回 -1。

static int minCost(int[][] relations, int[] prev)
{
    PriorityQueue<Person> q = new PriorityQueue<>();

    Person[] person = new Person[relations.length];
    for(int i=0; i<relations.length; i++) 
    {
        person[i] = new Person(i, i==0 ? 0 : Integer.MAX_VALUE);
    }

    q.offer(person[0]);     
    while(!q.isEmpty())
    {
        Person p = q.poll();

        if(p.level == person.length-1) 
            return p.cost;          

        for(int n : relations[p.level])
        {
            int d = p.cost + (n-p.level)*(n-p.level); 
            if(d < person[n].cost)
            {
                q.offer(person[n] = new Person(n, d));
                prev[n] = p.level;
            }
        }
    }       
    return -1;
}

static class Person implements Comparable<Person>
{
    public int level;
    public int cost;

    public Person(int level, int cost)
    {
        this.level = level;
        this.cost = cost;
    }

    @Override
    public int compareTo(Person o)
    {
        return cost - o.cost;
    }
}

static String buildPath(int[] arr, int i, String path)
{
    path = i + " " + path;
    if(i == 0) return path;
    else return buildPath(arr, arr[i], path);
}

public static void main(String[] args) 
{
    int[][] arr ={{1, 2, 3},
                  {8, 6, 4},
                  {7, 8, 3},
                  {8, 1},
                  {6},
                  {8,7},
                  {9, 4},
                  {4, 6},
                  {1},
                  {1,4}};

    int[] prev = new int[arr.length];
    int min = minCost(arr, prev);
    if(min < 0) System.out.println("No path");    
    else System.out.println(min + " : " + buildPath(prev, arr.length-1, ""));        
}

输出：

23 : 0 1 4 6 9

推荐阅读