Breadth-First Search statt einem Pfad, alle Pfade herausfinden

[lennero]

Hallo
Habe folgenden Code, der den kürzesten Pfad zwischen Zwei Knoten in einem 2D-Array herausfindet. Allerdings kann es vorkommen, dass es mehrere kürzeste Pfade zwischen den Knoten gibt, und ich brauche immer einen bestimmten, von der Aufgabenstellung verlangten Pfad.

        Node optimalNode = null;
        Queue<Node> nodes = new LinkedList<Node>();
        nodes.offer(new Node(startingPos, null));

        Set<Point> examinedPoints = new HashSet<Point>();
        

        while(!nodes.isEmpty())
        {
            Node current = nodes.poll();
            examinedPoints.add(current.point);
           
            //check if we found a target
            for(int i = 0; i < possibleTargets.size(); i++)
            {
                if(current.point.equals(possibleTargets.get(i)))
                {
                    optimalNode = current;
                    break;
                }
            }

            //add all relevant nodes in the vicinity (up, left, right, down) to the queue (the way the grid is set-up makes it impossible to be out of bounds here)
            if(grid[current.point.y - 1][current.point.x]== '.' && !examinedPoints.contains(new Point(current.point.x, current.point.y - 1)))
            {
                nodes.offer(new Node(new Point(current.point.x, current.point.y - 1), current));
            }
            if(grid[current.point.y][current.point.x - 1] == '.' && !examinedPoints.contains(new Point(current.point.x - 1, current.point.y)))
            {
                nodes.offer(new Node(new Point(current.point.x - 1, current.point.y), current));
            }
            if(grid[current.point.y][current.point.x + 1] == '.' && !examinedPoints.contains(new Point(current.point.x + 1, current.point.y)))
            {
                nodes.offer(new Node(new Point(current.point.x + 1, current.point.y), current));
            }
            if(grid[current.point.y + 1][current.point.x] == '.' && !examinedPoints.contains(new Point(current.point.x, current.point.y + 1)))
            {
                nodes.offer(new Node(new Point(current.point.x, current.point.y + 1), current));
            }
        }

und so sieht das Feld aus

#######
#.E...#
#...!.#
#..!G!#
#######

Hierbei muss ich das 'E' auf das nächstgelegene Ausrufezeichen transportieren. (ist nur ein kleines Beispiel, in der Aufgabe gibt es mehrere 'E' und 'G' Zeichen auf dem Feld). Falls zwei Ausrufezeichen dieselbe Distanz vom 'E' haben, muss das Ausrufezeichen gewählt werden, welches von links nach rechts gelesen als erstes vorkommt.

Der Pfad der für das Beispiel berechnet wird, ist folgender

#######
#.E...#
#.+++.#
#...G.#
#######

Ich möchte aber diesen Pfad haben

#######
#.E++.#
#...+.#
#...G.#
#######

Ich hab mir überlegt, dass jeder Knoten ja mehrere Eltern hat. In meinem Codebeispiel setze ich allerdings immer nur 1 Elternknoten. Dann müsste ich ja eine Liste von Eltern für jeden Knoten führen oder gibt es einen anderen Weg?

 

[mihe7]

welches von links nach rechts gelesen als erstes vorkommt.

Du meinst von oben nach unten und von links nach rechts gelesen?

Unabhängig davon wird in deinen beiden Beispielen jeweils das gleiche ! angesteuert.

 

[lennero]

Du meinst von oben nach unten und von links nach rechts gelesen?

Unabhängig davon wird in deinen beiden Beispielen jeweils das gleiche ! angesteuert.

Ja, genau, allerdings soll auch der Pfad gewählt werden, welcher von oben, unten, links, rechts als erstes gelesen wird.

Was genau gemacht werden soll ist folgendes.

1. Suche nach allen 'G' Zeichen.
2. Überprüfe ob Stellen neben (links rechts oben unten) 'G' frei sind und speichere sie in einer Liste (possibleTargets im Code oben ).
3. Suche per BFS nach der nächstgelegenen Freien Stelle neben einem 'G'
4. Führe einen einzigen Schritt in Richtung des 'G' aus.

Das ist der Pfad der berechnet wird.

#######
#.E...#
#.+++.#
#...G.#
#######

Das ist auch richtig so, allerdings gibt es noch einen zweiten Pfad der genauso kurz ist und der erste Schritt auf diesem Pfad kommt von oben unten links rechts gelesen als erstes vor und ist in diesem Fall der "optimale" Pfad.

#######
#.E++.#
#...+.#
#...G.#
#######

 

[httpdigest]

Dann verändere einfach die Priorität der (links, rechts, unten, oben)-Schritte. Da du ja anscheinend denjenigen Weg präferierst, der zuerst auf der Horizontalen (nach links oder rechts) geht, und erst _dann_ nach oben/unten, prüfe also zuerst solche Wege, die zuerst nach links/rechts gehen würden.
Z.B.:

Spoiler

import static java.util.stream.Stream.concat;
import static java.util.stream.Stream.of;
import static java.util.Arrays.asList;
import static java.util.Comparator.comparingInt;
import static java.util.stream.Collectors.toList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.stream.Stream;
public class ShortestWay {
    private static class Point {
        public int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public boolean equals(Object obj) {
            Point pt = (Point) obj;
            return x == pt.x && y == pt.y;
        }
        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }
    private static Point pt(int x, int y) {
        return new Point(x, y);
    }
    private static Stream<Point> nextSteps(Point p) {
        return Arrays.stream(new Point[] {
            pt(p.x, p.y - 1), // up
            pt(p.x, p.y + 1), // down
            pt(p.x - 1, p.y), // left
            pt(p.x + 1, p.y)  // right
        });
    }
    public static Optional<List<Point>> way(char[][] m, Point start) {
        return way(m, start, asList(start));
    }
    private static Optional<List<Point>> way(char[][] m, Point pt, List<Point> way) {
        if (m[pt.y][pt.x] == '!')
            return Optional.of(way);
        return nextSteps(pt)
              .filter(p -> visitable(m, way, p))
              .map(p -> way(m, p, concat(way.stream(), of(p)).collect(toList())))
              .filter(Optional::isPresent)
              .map(Optional::get)
              .sorted(comparingInt(List::size))
              .findFirst();
    }
    private static boolean visitable(char[][] m, List<Point> way, Point p) {
        return !way.contains(p) &&
                p.y >= 0 && p.y < m.length &&
                p.x >= 0 && p.x < m[p.y].length
                && m[p.y][p.x] != '#';
    }

    // Test
    public static void main(String[] args) {
        char[][] m = {
            {'G', '.', '.', '.'},
            {'.', '.', '.', '.'},
            {'.', '.', '!', '.'},
            {'.', '.', '.', '.'},
        };
        way(m, pt(0, 0)).ifPresent(System.out::println);
    }
}

 

[lennero]

Dann verändere einfach die Priorität der (links, rechts, unten, oben)-Schritte. Da du ja anscheinend denjenigen Weg präferierst, der zuerst auf der Horizontalen (nach links oder rechts) geht, und erst _dann_ nach oben/unten, prüfe also zuerst solche Wege, die zuerst nach links/rechts gehen würden.
Z.B.:

Spoiler

import static java.util.stream.Stream.concat;
import static java.util.stream.Stream.of;
import static java.util.Arrays.asList;
import static java.util.Comparator.comparingInt;
import static java.util.stream.Collectors.toList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.stream.Stream;
public class ShortestWay {
    private static class Point {
        public int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public boolean equals(Object obj) {
            Point pt = (Point) obj;
            return x == pt.x && y == pt.y;
        }
        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }
    private static Point pt(int x, int y) {
        return new Point(x, y);
    }
    private static Stream<Point> nextSteps(Point p) {
        return Arrays.stream(new Point[] {
            pt(p.x, p.y - 1), // up
            pt(p.x, p.y + 1), // down
            pt(p.x - 1, p.y), // left
            pt(p.x + 1, p.y)  // right
        });
    }
    public static Optional<List<Point>> way(char[][] m, Point start) {
        return way(m, start, asList(start));
    }
    private static Optional<List<Point>> way(char[][] m, Point pt, List<Point> way) {
        if (m[pt.y][pt.x] == '!')
            return Optional.of(way);
        return nextSteps(pt)
              .filter(p -> visitable(m, way, p))
              .map(p -> way(m, p, concat(way.stream(), of(p)).collect(toList())))
              .filter(Optional::isPresent)
              .map(Optional::get)
              .sorted(comparingInt(List::size))
              .findFirst();
    }
    private static boolean visitable(char[][] m, List<Point> way, Point p) {
        return !way.contains(p) &&
                p.y >= 0 && p.y < m.length &&
                p.x >= 0 && p.x < m[p.y].length
                && m[p.y][p.x] != '#';
    }

    // Test
    public static void main(String[] args) {
        char[][] m = {
            {'G', '.', '.', '.'},
            {'.', '.', '.', '.'},
            {'.', '.', '!', '.'},
            {'.', '.', '.', '.'},
        };
        way(m, pt(0, 0)).ifPresent(System.out::println);
    }
}

Also die Priorität musste ich nicht ändern, die war schon richtig so. Erst oben nachschauen, dann links, dann rechts und dann unten . Das sollte sicherstellen, dass immer der richtige Pfad gewählt wird.

Hiermit klappt es wie es soll.

    while (!nodes.isEmpty()) {
            Node current = nodes.poll();
            examinedPoints.add(current.point);

            // add all relevant nodes in the vicinity (up, left, right, down) to
            // the queue (the way the grid is set-up makes it impossible to be
            // out of bounds here)
            Point up = new Point(current.point.x, current.point.y - 1);
            Point left = new Point(current.point.x - 1, current.point.y);
            Point right = new Point(current.point.x + 1, current.point.y);
            Point down = new Point(current.point.x, current.point.y + 1);

            if (grid[current.point.y - 1][current.point.x] == '.' && !examinedPoints.contains(up)) {
                if (possibleTargets.contains(up)) {
                    optimalNode = new Node(up, current);
                    break;
                } else
                    nodes.offer(new Node(up, current));
            }
            if (grid[current.point.y][current.point.x - 1] == '.' && !examinedPoints.contains(left)) {
                if (possibleTargets.contains(left)) {
                    optimalNode = new Node(left, current);
                    break;
                }
                nodes.offer(new Node(left, current));
            }
            if (grid[current.point.y][current.point.x + 1] == '.' && !examinedPoints.contains(right)) {
                if (possibleTargets.contains(right)) {
                    optimalNode = new Node(right, current);
                    break;
                }
                nodes.offer(new Node(right, current));
            }
            if (grid[current.point.y + 1][current.point.x] == '.' && !examinedPoints.contains(down)) {
                if (possibleTargets.contains(down)) {
                    optimalNode = new Node(down, current);
                    break;
                }
                nodes.offer(new Node(down, current));
            }
        }

Musste nur die Schleife abbrechen sobald eines der Knoten in Reichweite mein gesuchter Knoten ist. Die Reihenfolge in der ich die Knoten untersuche sorgt dann dafür, dass ich am Ende den richtigen Pfad bekomme.

Ein Schritt für einen etwas komplexeren Fall sieht dann so aus

initial
#########
#G..G..G#
#.......#
#.......#
#G..E..G#
#.......#
#.......#
#G..G..G#
#########

after round 1
#########
#.G...G.#
#...G...#
#...E..G#
#.G.....#
#.......#
#G..G..G#
#.......#
#########