BreadthSearch auf Graphen

mustBe · 18. Jul 2022

Kann mir vielleicht bitte jemand schnell sagen, was hier falsch ist? Ich möchte eine ganz einfache BreadthSearch auf einem Graphen, der Zyklen enthalten kann oder schnellere Rückwege, durchführen, die ALLE Wege liefert, um dann den kürzesten Weg zu suchen:

Java:

package gra;

public record WeightEdge(double costs, DirWeightNode node) {
}

package gra;

public class DirWeightNode {
    public Object content;
    public WeightEdge[] edges;
}

package gra;

public record Way(double sumCosts, DirWeightNode... way) {
}

package gra;

import java.util.*;

public class BreadthSearch {
    public static ArrayList<Way> allWays(DirWeightNode start) {
        ArrayList<Way> ways = new ArrayList<>();
        HashSet<WeightEdge> visited = new HashSet<>();
        Queue<Way> queue = new ArrayDeque<>();
        queue.add(new Way(0, start));
        while (!queue.isEmpty()) {
            Way first = queue.remove();
            DirWeightNode[] way1 = first.way();
            DirWeightNode last = way1[way1.length - 1];
            for (WeightEdge current : last.edges) {
                double newCosts = first.sumCosts() + current.costs();
                DirWeightNode[] newWay = extendArray(current.node(), way1);
                Way way2 = new Way(newCosts, newWay);
                ways.add(way2);
                if (!visited.contains(current)) {
                    visited.add(current);
                    queue.add(way2);
                }
            }
        }
        return ways;
    }

    public static DirWeightNode[] extendArray(DirWeightNode a, DirWeightNode... b) {
        DirWeightNode[] newArray = new DirWeightNode[b.length + 1];
        System.arraycopy(b, 0, newArray, 0, b.length);
        newArray[b.length] = a;
        return newArray;
    }

    public static void main(String[] args) {
        DirWeightNode a = new DirWeightNode();
        DirWeightNode b = new DirWeightNode();
        DirWeightNode c = new DirWeightNode();
        DirWeightNode d = new DirWeightNode();
        a.content = "a";
        b.content = "b";
        c.content = "c";
        d.content = "d";
        a.edges = new WeightEdge[]{new WeightEdge(100, b), new WeightEdge(90, c), new WeightEdge(50, d)};
        b.edges = new WeightEdge[]{new WeightEdge(1, a), new WeightEdge(10, c), new WeightEdge(15, d)};
        c.edges = new WeightEdge[]{new WeightEdge(10, b), new WeightEdge(90, a), new WeightEdge(25, d)};
        d.edges = new WeightEdge[]{new WeightEdge(25, c), new WeightEdge(1, b)};
        ArrayList<Way> ways = allWays(a);
        ways.sort(Comparator.comparing(Way::sumCosts));
        for (Way way : ways) {
            System.out.println(way.sumCosts());
            for (DirWeightNode node : way.way()) {
                System.out.print(node.content + " -> ");
            }
            System.out.println();
        }
    }
}

Es scheint so, als ob alles OK wäre, aber wenn ein Umweg hinzukommt, dann scheint das nicht mehr zu funktionieren:

Java:

    public static void main(String[] args) {
        DirWeightNode a = new DirWeightNode();
        DirWeightNode b = new DirWeightNode();
        DirWeightNode c = new DirWeightNode();
        DirWeightNode d = new DirWeightNode();
        DirWeightNode umweg = new DirWeightNode();
        a.content = "a";
        b.content = "b";
        c.content = "c";
        d.content = "d";
        umweg.content = "umweg";
        a.edges = new WeightEdge[]{new WeightEdge(110, umweg), new WeightEdge(100, b), new WeightEdge(90, c), new WeightEdge(50, d)};
        b.edges = new WeightEdge[]{new WeightEdge(110, umweg), new WeightEdge(1, a), new WeightEdge(10, c), new WeightEdge(15, d)};
        c.edges = new WeightEdge[]{new WeightEdge(110, umweg), new WeightEdge(10, b), new WeightEdge(90, a), new WeightEdge(25, d)};
        d.edges = new WeightEdge[]{new WeightEdge(110, umweg), new WeightEdge(25, c), new WeightEdge(1, b)};
        umweg.edges = new WeightEdge[]{new WeightEdge(110, a), new WeightEdge(110, b), new WeightEdge(110, c), new WeightEdge(110, d)};
        ArrayList<Way> ways = allWays(a);
        ways.sort(Comparator.comparing(Way::sumCosts));
        for (Way way : ways) {
            System.out.println(way.sumCosts());
            for (DirWeightNode node : way.way()) {
                System.out.print(node.content + " -> ");
            }
            System.out.println();
        }
    }

Oder habe ich etwas übersehen? Eine Optimierung ala Dijkstra möchte ich nicht durchführen.

Ausgabe 1

50.0
a -> d ->
51.0
a -> d -> b ->
52.0
a -> d -> b -> a ->
61.0
a -> d -> b -> c ->
66.0
a -> d -> b -> d ->
75.0
a -> d -> c ->
85.0
a -> d -> c -> b ->
90.0
a -> c ->
100.0
a -> b ->
100.0
a -> c -> b ->
100.0
a -> d -> c -> d ->
101.0
a -> b -> a ->
101.0
a -> c -> b -> a ->
110.0
a -> b -> c ->
110.0
a -> c -> b -> c ->
115.0
a -> b -> d ->
115.0
a -> c -> d ->
115.0
a -> c -> b -> d ->
116.0
a -> b -> d -> b ->
116.0
a -> c -> d -> b ->
120.0
a -> b -> c -> b ->
135.0
a -> b -> c -> d ->
140.0
a -> b -> d -> c ->
140.0
a -> c -> d -> c ->
151.0
a -> b -> a -> d ->
165.0
a -> d -> c -> a ->
180.0
a -> c -> a ->
191.0
a -> b -> a -> c ->
200.0
a -> b -> c -> a ->
201.0
a -> b -> a -> b ->
230.0
a -> c -> a -> d ->
270.0
a -> c -> a -> c ->
280.0
a -> c -> a -> b ->

Ausgabe 2

50.0
a -> d ->
51.0
a -> d -> b ->
52.0
a -> d -> b -> a ->
61.0
a -> d -> b -> c ->
66.0
a -> d -> b -> d ->
75.0
a -> d -> c ->
85.0
a -> d -> c -> b ->
90.0
a -> c ->
100.0
a -> b ->
100.0
a -> c -> b ->
100.0
a -> d -> c -> d ->
101.0
a -> b -> a ->
101.0
a -> c -> b -> a ->
110.0
a -> umweg ->
110.0
a -> b -> c ->
110.0
a -> c -> b -> c ->
115.0
a -> b -> d ->
115.0
a -> c -> d ->
115.0
a -> c -> b -> d ->
116.0
a -> b -> d -> b ->
116.0
a -> c -> d -> b ->
120.0
a -> b -> c -> b ->
135.0
a -> b -> c -> d ->
140.0
a -> b -> d -> c ->
140.0
a -> c -> d -> c ->
151.0
a -> b -> a -> d ->
160.0
a -> d -> umweg ->
161.0
a -> d -> b -> umweg ->
165.0
a -> d -> c -> a ->
180.0
a -> c -> a ->
185.0
a -> d -> c -> umweg ->
191.0
a -> b -> a -> c ->
200.0
a -> c -> umweg ->
200.0
a -> b -> c -> a ->
201.0
a -> b -> a -> b ->
210.0
a -> b -> umweg ->
210.0
a -> c -> b -> umweg ->
211.0
a -> b -> a -> umweg ->
220.0
a -> umweg -> a ->
220.0
a -> umweg -> b ->
220.0
a -> umweg -> c ->
220.0
a -> umweg -> d ->
220.0
a -> b -> c -> umweg ->
221.0
a -> umweg -> b -> a ->
221.0
a -> umweg -> d -> b ->
225.0
a -> b -> d -> umweg ->
225.0
a -> c -> d -> umweg ->
230.0
a -> umweg -> b -> c ->
230.0
a -> umweg -> c -> b ->
230.0
a -> c -> a -> d ->
235.0
a -> umweg -> b -> d ->
245.0
a -> umweg -> c -> d ->
245.0
a -> umweg -> d -> c ->
270.0
a -> umweg -> a -> d ->
270.0
a -> c -> a -> c ->
280.0
a -> c -> a -> b ->
290.0
a -> c -> a -> umweg ->
310.0
a -> umweg -> a -> c ->
310.0
a -> umweg -> c -> a ->
320.0
a -> umweg -> a -> b ->
330.0
a -> umweg -> a -> umweg ->
330.0
a -> umweg -> b -> umweg ->
330.0
a -> umweg -> c -> umweg ->
330.0
a -> umweg -> d -> umweg ->

mustBe · 19. Jul 2022

Ich hab nochmal drüber geschlafen, hier scheint alles korrekt zu sein.

KonradN · 20. Jul 2022

Ich muss gestehen, dass ich im Augenblick nicht ganz sicher bin, was Du erwartest / machen willst.

Eine einfache Breitensuche ist das, was Du da machst, ja so nicht, Diese würde die Gewichtungen ja auch nicht interessieren.

Breitensuche – Wikipedia

de.wikipedia.org

Code:

BFS(start_node, goal_node)
    erzeuge eine leere Warteschlange queue
    queue.enqueue(start_node);
    markiere start_node als gesehen
    while queue ist nicht leer
        node = queue.dequeue();
        if node == goal_node
            return true;
        foreach child in nachfolger(node)
            if child ist nicht markiert als gesehen
                queue.enqueue(child);
                markiere child als gesehen
    return false;

Was dann bei Deiner Implementierung sofort auffällt: Du packst den ersten Knoten in die Queue aber markierst diesen aber nicht als besucht.

Weiter ins Detail bin ich bei Deiner Implementation nicht gegangen, da ich - wie schon gesagt - nicht so ganz verstehe, worauf Du genau hinaus willst, denn Deine Aussage

der Zyklen enthalten kann oder schnellere Rückwege, durchführen, die ALLE Wege liefert, um dann den kürzesten Weg zu suchen:

passt nicht so ganz zu einer einfachen Breitensuche mit gewichten Graphen. Du bekommst eben nicht alle Wege, da ja die einfache Breitensuche einmal besuchte Knoten danach nicht weiter betrachtet.

mustBe · 20. Jul 2022

KonradN hat gesagt.:
Eine einfache Breitensuche ist das, was Du da machst, ja so nicht, Diese würde die Gewichtungen ja auch nicht interessieren.

Das ist aber auch nicht richtig. Es funktioniert doch nicht:

Java:

    public static void main(String[] args) {
        DirWeightNode a = new DirWeightNode();
        DirWeightNode b = new DirWeightNode();
        DirWeightNode c = new DirWeightNode();
        DirWeightNode d = new DirWeightNode();
        DirWeightNode engpass_start = new DirWeightNode();
        DirWeightNode engpass_end = new DirWeightNode();
        a.content = "a";
        b.content = "b";
        c.content = "c";
        d.content = "d";
        engpass_start.content = "e";
        engpass_end.content = "f";
        a.edges = new WeightEdge[]{new WeightEdge(100, engpass_start), new WeightEdge(1, b)};
        b.edges = new WeightEdge[]{new WeightEdge(1, engpass_start), new WeightEdge(1, a)};
        c.edges = new WeightEdge[]{};
        d.edges = new WeightEdge[]{};
        engpass_start.edges = new WeightEdge[]{new WeightEdge(50, engpass_end)};
        engpass_end.edges = new WeightEdge[]{new WeightEdge(50, c), new WeightEdge(50, d)};
        ArrayList<Way> ways = allWays(a);
        ways.sort(Comparator.comparing(Way::sumCosts));
        for (Way way : ways) {
            System.out.println(way.sumCosts());
            for (DirWeightNode node : way.way()) {
                System.out.print(node.content + " -> ");
            }
            System.out.println();
        }
    }

1.0
a -> b ->
2.0
a -> b -> e ->
2.0
a -> b -> a ->
3.0
a -> b -> a -> b ->
52.0
a -> b -> e -> f ->
100.0
a -> e ->
102.0
a -> b -> a -> e ->
150.0
a -> e -> f ->
200.0
a -> e -> f -> c ->
200.0
a -> e -> f -> d ->

Ich kann aber nach c und d über a b e f mit nur 102 Kosten gelangen.

Also irgendwo ist der Wurm drin, egal ob ich nun Knoten oder Kanten markiere... Wahrscheinlich muss ich jeden Weg auf Zyklen untersuchen 😥

KonradN · 20. Jul 2022

Das was ich Dir nur sagen wollte: Die einfache Breitensuche kann das, was Du willst, nicht leisten. Ein entscheidender Punkt bei der einfachen Breitensuche ist nun einmal, dass Du jeden Knoten nur genau einmal betrachtest.

Also müsstest du dich von diesem verabschieden und dann deutlich mehr Aufwand betreiben.

Ein Ansatz, der hier funktionieren würde aber sehr aufwendig ist:

Du hast die Map mit key: knoten und Value: Weg zu diesem Knoten mit Gewichtung.

Rekursive Methode findeWege(node, weg mit aktGewichtung):

Ist in der Map ein Weg zum aktuellen Node mit Gewichtung <= aktGewichtung? -> Abbruch
Trage in die Map für den aktuellen Node den Weg mit der aktGewichtung ein
Für jeden Child-Knoten: Rufe rekursiv auf mit erweitertem Weg / neuer Gewichtung

Das wäre etwas, mit dem du mehrere Runden gehen würdest. Das mal einfach skizziert anhand eines Bahnnetzes. Und die Knoten sind dann mal alle sortiert, dass immer erst welche im Norden kommen .. sozusagen im Uhrzeigersinn sortiert ... Einfach nur als Annahme... ist halt durch Zufall so ...

Dann kann es also sein, dass Du bei Startpunkt Mitte in Deutschland feststellst, dass es eine Route zu einem Punkt im Norden (und etwas Westlich) gibt, wenn du ganz nach Norden fährst bis zur Grenze um dann nach Osten zu drehen und alle Stationen an der Grenze abzufahren, bis du die ganze Grenze abgefahren bist und etwas westlich des einen Punktes an der Grenze ankommst. Aber das ist ja nur ein Zwischenstand. Irgendwann bist Du bei der Rekursion dann bei dem halben Weg zur nördlichen Grenze nach Osten gefahren ... da an der Grenze dann natürlich schön im Uhrzeigersinn entlang ...

Du kannst dir das vorstellen? Eine ganz nette Problematik: https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Das einfach nur als weitere Erläuterung. Hoffe Du ist nicht zu enttäuscht, dass Dir da jetzt hier niemand eine einfache Lösung zu diesem Problem anbieten konnte.

isaaccc · 20. Jul 2022

Mit dem Problem des Handlungsreisenden hatte ich mich ganz früher schon mal beschäftigt. Ich weiß dass es np-schwer ist. Aber deshalb habe ich doch hier einfach nach einer Breitensuche gefragt, nicht nach einer Optimierung ala Dijkstra oder A*. Bleibt mir also nur Backtracking übrig?

BreadthSearch auf Graphen

mustBe

Mitglied

mustBe

Mitglied

KonradN

Super-Moderator

Breitensuche – Wikipedia

mustBe

Mitglied

KonradN

Super-Moderator

isaaccc

Mitglied

Aktuelle Jobs

Neue Themen