Инициализация ребер с помощью алгоритма Дейкстры

Я не понимаю, как инициализировать класс Pointer (edge) при реализации моего алгоритма Дейкстры. Класс Node содержит ArrayList вызываемых соседей Pointer, которые представляют 4 соседей с любой стороны узла. Мой класс Pointer принимает целевой узел (куда он указывает) в качестве аргумента в конструкторе. Все они добавлены в двумерный массив узлов размером 36x25.

На данный момент я использую метод setNeighbors(), просматривающий каждый узел, построенный на сетке 36x25, после того, как все они были построены, который просматривает каждый возможный узел до 4 раз в зависимости от его релевантности в сетке (у угла есть 2 соседа ) и прерывается, как только сосед найден путем сравнения координат (x, y).

Этот процесс инициализации занимает слишком много времени для моей цели, поэтому я хотел знать, может ли кто-нибудь показать мне способ, который сделал бы эту инициализацию более эффективной.

У меня есть узел класса:

import java.util.ArrayList;

public class Node implements Comparable<Node>
{
     public int x;
     public int y;
     public ArrayList<Pointer> neighbors = new ArrayList<Pointer>();
     public double minDistance = Double.POSITIVE_INFINITY;
     public Node previous;

     public Node(int xPos, int yPos) 
     { 
        x = xPos;
        y = yPos;
     }

     public int compareTo(Node other)
     {
        return Double.compare(minDistance, other.minDistance);
     }
}

И указатель класса:

public class Pointer
{
     public final Node target;
     public final double weight = 1;
     public Pointer(Node targ)       
     { 
       target = targ;
     }
}

person SpiderShlong    schedule 07.11.2013    source источник
comment
где код, который на самом деле строит вашу карту?   -  person Mike 'Pomax' Kamermans    schedule 07.11.2013


Ответы (1)


Ну, вы можете позволить сетке представлять что-то вроде квадратной сетки с нижней и верхней границей как для x, так и для y, затем вы можете создать рекурсивный метод, в котором вы инициализируете узел в (x, y), и этот инициализированный узел будет инициализировать свой север /западные/южные/восточные соседи, если эти узлы x, y все еще находятся в пределах сетки, в противном случае вы наткнулись на стену и больше не можете инициализировать в этом направлении. Проблема здесь в том, что делает Pointer, это похоже на класс, который все усложняет. Если сетка квадратная, вы можете сохранить

Node north;
Node west
Node south
Node east

полей в вашем классе Node.

Если сетка не квадратная, вы все равно можете сохранить

List<Node> connectedTo
person arynaq    schedule 07.11.2013
comment
Спасибо, просто заставил меня переосмыслить свой код. Я по-прежнему буду использовать список соседних узлов, но поскольку я удалил взвешенные движения, необходимость в классе ребер (Pointer) отпала. - person SpiderShlong; 07.11.2013