Проблема с алгоритмом, чтобы найти минимальный путь 2d массива - PullRequest
Новая
       7

Проблема с алгоритмом, чтобы найти минимальный путь 2d массива

0 голосов
/ 08 сентября 2018

Вопрос:

На встрече 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
 ]

Мое решение:

Для использования очереди приоритетов, а также для отслеживания элементов, которые уже были посещены. В основном подход поиска в ширину. Также я буду использовать карту для отслеживания уровней.

Моя проблема

Я пытаюсь использовать приоритетную очередь, но не могу пройти 2d массив с очередью. Я покрываю только уровень 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;
  }
}

1 Ответ

0 голосов
/ 08 сентября 2018

Вы ищете минимальную стоимость пути через ориентированный граф.Таким образом, алгоритм Дейкстры - это то, что вы хотите.

Вот простая реализация 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
...