JAVA - Wie programmiert man Node Nachbarn in einem Raster?

Question

Ich bin neu in der Programmierung und als schulische Aufgabe muss ich BFS, DFS und A* Suchalgorithmen in Java implementieren, um nach einem gegebenen Ziel von einer gegebenen Startposition in einem Raster mit einer bestimmten Größe, z.B. 4x4, 8x8, usw., zu suchen.

Zu Beginn weiß ich nicht, wie ich die Nachbarn aller Knoten codieren soll. Zum Beispiel hat im 8x8-Raster Kachel 1 die Nachbarn 2 und 9, und Kachel 12 hat 4, 11, 13 und 20 als Nachbarn, aber ich habe Schwierigkeiten, das zu codieren. Ich brauche den Teil mit den Nachbarn, damit ich mich von der Startposition aus legal horizontal oder vertikal durch die Nachbarn bewegen kann.

 1  2  3  4  5  6  7  8 
 9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 
33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 
49 50 51 52 53 54 55 56 
57 58 59 60 61 62 63 64

Meine Knotenklasse sieht so aus:

class Node {
   int value;
   LinkedList neighbors;
   boolean expanded;
}

Angenommen, mir wird ein 8x8-Raster gegeben, Wenn ich das Programm mit einem Raster der Größe 8x8 starte:

1 - Meine Hauptmethode wird z.B. ein Array-Liste von Knoten erstellen

ArrayList test = new ArrayList();

Und dann mit einer For-Schleife jedem Knoten in der Array-Liste von 1 bis 64 (wenn die Rastergröße 8x8 war) einen Wert zuweisen.

ABER irgendwie muss ich die Nachbarn jedes Knotens hinzufügen, wenn mir jemand Einzelheiten geben könnte, würde ich das sehr schätzen.

Answer 1

Angenommen, Ihre Nodes sind in M Reihen und N Spalten angeordnet. Zur Vereinfachung sei nodes[r][c] der Verweis auf Node in Zeile r und Spalte c (nullbasierte Indizierung) mit einer leeren List neighbors, die wir aufbauen möchten.

So können Sie sie aufbauen:

for (int r = 0; r < M; r++) {
  for (int c = 0; c < N; c++) {
    Node n = nodes[r][c];
    List neighbors = n.neighbors;
    if (r > 0) {     // hat Norden
      neighbors.add(nodes[r-1][c]);
    }
    if (r < M - 1) { // hat Süden
      neighbors.add(nodes[r+1][c]);
    }
    if (c > 0) {     // hat Westen
      neighbors.add(nodes[r][c-1]);
    }
    if (c < N - 1) { // hat Osten
      neighbors.add(nodes[r][c+1]);
    }
  }
}

---

Meine main-Methode wird ein ArrayList erstellen

Es ist viel einfacher, ein Raster in einer 2-dimensionalen Datenstruktur zu behandeln, sei es ein Array-von-Arrays oder eine Liste-von-Listen. Wenn Sie darauf bestehen, eine 1-D-Liste zu haben, dann rufen Sie anstelle von nodes[r][c] die Hilfsfunktion nodeAt(r, c) auf:

Node nodeAt(int r, int c) {
   return nodesList.get(r * N + c);
}

Dies ist eine Standardumwandlung von 2-D-Indizierung in 1-D (unter der Annahme der zeilenweisen Anordnung).