Как сохранить соседей ячейки в гирде в очереди приоритетов - PullRequest
Новая
       80

Как сохранить соседей ячейки в гирде в очереди приоритетов

0 голосов
/ 01 мая 2020

Скажем, у меня есть 4 на 4 сетки, поэтому 16 ячеек. Каждая ячейка содержит значение между 1,5. например. 

     0 1 2 3
     _ _ _ _
0 - |2|1|3|2|
1 - |1|3|5|1|
2 - |5|2|1|4|
3 - |2|4|2|1|

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

Моя цель - найти кратчайшую сумму каждой ячейки для пункта назначения. Источник может быть случайным в сетке, а также в пункте назначения. (то есть не всегда слева направо и снизу справа).

Я работал с графиками, которые используют смежные матрицы. Однако с этой сеткой целесообразно создать смежную матрицу? т.е. установить все поля в бесконечность, которые не являются соседями. Что было бы наиболее эффективным способом вставки ячеек в приоритетную очередь? Это будет {(строка, столбец), расстояние}?

Просто чтобы уточнить, насколько я понимаю, очередь с приоритетами будет хранить лучший путь? Так что клетка и накопительная дистанция. Потому что алгоритм Диджстры использует BFS, который будет искать всех соседей для наименьшего расстояния в этом случае.

1 Ответ

0 голосов
/ 01 мая 2020

Сделайте Node класс, который имеет 3 поля (строка, столбец, расстояние) и реализует Comparable. Затем используйте Use PriorityQueue<Node>: 

import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(0, 9, 1));
        pq.add(new Node(4, 0, 8));

        System.out.println(pq.poll().getDistance()); //prints 1
    }
}

class Node  implements Comparable<Node>{

    private final int row, col, distance;

    public Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        distance = value;
    }

    int getDistance() {
        return distance;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(distance, other.distance);
    }
}

В качестве альтернативы установите Comperator в очередь с приоритетами, чтобы Node не пришлось реализовывать Comparable: 

import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Node::compare);
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(0, 9, 1));
        pq.add(new Node(4, 0, 8));

        System.out.println(pq.poll().getDistance()); //prints 1
    }
}

class Node{

    private final int row, col, distance;

    public Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        distance = value;
    }

    int getDistance() {
        return distance;
    }

    public static int compare(Node o1, Node o2) {
        return Integer.compare(o1.getDistance(), o2.getDistance());
    }
}

Вы можете также используйте лямбда-выражение для установки компаратора:

PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2)->Integer.compare(o1.getDistance(), o2.getDistance()));

Все три опции действительны.

...