Fehler in Datenstruktur für A*

Java-Forum Allgemeine Themen
1

Es wird immer komplizierter. Für eine Visualisierung und Geschwindigkeit musste ich jetzt die DS anpassen:

  • null ist weder für Knoten noch Kante gestattet
  • c ist als ID eindeutig
  • es gibt nicht mehr als (‘z’ - ‘a’ + 1) Knoten
  • Knoten werden anhand ihres h-Werts und c verglichen
  • alle Kanten sind ungerichtet,
  • dennoch weiß jeder Knoten, zu welchem Knoten es eine Kante gibt
  • eine Kante hat unabhängig von der Hin- und Rückrichtung denselben Hash
  • eine Kante ist gleich einer anderen, wenn sie auf denselben Knoten zeigt
  • vertext ist (i-eine) Referenz für eine Visualisierung
  • edge ist (i-eine) Referenz für eine Visualisierung

Wo hab ich einen Fehler gemacht?:

class Knot implements Comparable<Knot> {

    int x, y;
    char c;
    int h;
    List<Kant> n = new LinkedList<>();
    Object vertex;

    Knot(char c) {
        this.c = c;
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 89 * hash + this.c;
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Knot other = (Knot) obj;
        return c == other.c;
    }

    @Override
    public String toString() {
        String s = c + " " + x + " " + y + "\nh = " + h;
        // s += c + " [label=\"" + c + "\\nh = " + h + "\", pos=\"" + x + "," + y + "!\"]";
        return s;
    }

    @Override
    public int compareTo(Knot o) {
        if (h == o.h) {
            return c - o.c;
        }
        return Integer.compare(h, o.h);
    }
}

class Kant {

    Knot k1, k2, k3;
    int k;
    Object edge;

    Kant(Knot k1, Knot k2, int k) {
        if (k1.c < k2.c) {
            this.k1 = k1;
            this.k2 = k2;
        } else {
            this.k1 = k2;
            this.k2 = k1;
        }
        this.k3 = k2;
        this.k = k;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 83 * hash + Objects.hashCode(this.k1);
        hash = 83 * hash + Objects.hashCode(this.k2);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Kant other = (Kant) obj;
        return k3.c == other.k3.c;
    }

}
2

Ohje, also erst mal hab ich falsch eingefügt:

k1.n.add(new Kant(k1, k2, k));
k2.n.add(new Kant(k1, k2, k)); // ungerichtet

muss lauten:

k1.n.add(new Kant(k1, k2, k));
k2.n.add(new Kant(k2, k1, k)); // ungerichtet

Dann, kann man Java, Set und contains nicht überlisten. Ein (ungeschriebenes) Gesetzt besagt:
Wenn a gleich b, dann hash(a) == hash(b).

Es existiert aber mind. ein a,b, für das gilt: a gleich b und hash(a) != hash(b). (Sorry, für die schlechte math. Formulierung…)

Speziell Set und contains: Findet Hashkollidierung… (was danach passiert, ist mir noch nicht ganz klar…)

Also, einerseits sollen a->b und b->a gleich sein, anderseits muss ich doch wissen, in welche Richtung eine Kante nun zeigt. Ist das widersprüchlich?

3

Ich versteh schon lange nicht mehr was du sagst, aber kannst du nicht einfach die hash-Funktion überschreiben und die Info mit einbauen?

4

Der Fehler müsste sein, dass ich einmal List-contains brauche, was auf equals() basiert, und einmal Set-contains, was auf hashCode() und equals() basiert, mit unterschiedlichen Kriterien, und das unvereinbar ist. :blush: Ich nehm beide Methoden zum Vergleichen von Kanten aus, und mache das komplett anders…

5

Wenn zwei Kanten mit Endpunkten (a,b) in diesem Sinne “ungerichtet” sein sollen, kann man

int hashCode() { return a.hashCode() ^ b.hashCode; }

und

boolean equals(...) {
    return (a.equals(other.a) && b.equals(other.b)) ||
            (a.equals(other.b) && b.equals(other.a))
}

schreiben. Ein bißchen aufpassen muss man trotzdem. Wenn die Kanten noch Informationen enthalten, die darüber hinausgehen, kann das unerwartete Effekte haben.

6

Was du zunächst erstmal brauchst, ist Nachhilfe in Hashcode-Equals-Konventionen.

  1. Equals prüft Objekte auf inhaltliche Gleichheit. Identische Objekte sind ganz sicher auch vom Inhalt her gleich.

  2. Ein Hashcode wird über den genau jenen Inhalt errechnet, der in Equals für die Prüfung verwendet wird. Da es meistens theoretisch weit mehr als 2^32 Instanzen einer Klasse geben kann, gilt, dass zwei Objekte ganz sicher inhaltlich ungleich sind, wenn ihr Hashcode unterschiedlich ist, jedoch auch dann noch unterschiedlich sein können, wenn sie den selben Hashcode haben.

Eine Lektion, die ich damals auch nicht gleich verstanden habe, als ich Code postete, in welchem ich „hashCode()“ in „equals()“ verwendete… Das geht ja mal gar nicht! :wink:

Dein Fehler ist zwar ein Anderer aber auch dieser hat mit oben genannten Konventionen zu tun. In der Klasse Kant errechnest du den Hashcode aus den beiden Knoten und prüfst in Equals dann nur k3.c.
Warum eine Kante bei dir 3 Knoten hat, weißt wahrscheinlich auch nur du - Eine Kante ist afaik die Verbindung zwischen nicht mehr als zwei Knoten.
Die Konvention, dass k1.c < k2.c zu sein hat, ist durchaus legitim, nur sollte man es auch dabei belassen. Das bedeutet k3 ist ohnehin überflüssig.
Wenn du nun immernoch eine Contains-Methode auf Ident-Basis benötigts, kannst du dir diese auch in einer erweiterten LinkedList implementieren, aber ich denke mal, das wird überflüssig, wenn du dich an die Hashcode-Equals-Konventionen hälst.

1 „Gefällt mir“
7

Irgendwo steckt ein Denkfehler…
Es gibt jetzt nur noch k1 und k2 (k3 war ja k2)…
Und sortiert sind die Kanten (sorry, Knoten) auch nicht…
Anwendung:

if (!k1.n.contains(new Kant(k1, k2, -1))) { } // soll true sein, wenn k1->k2 oder k2->k1 nicht enthalten ist

for (Knot knot : knots) {
    for (Kant kant : knot.n) {
        if (!kants.contains(kant)) { // kants ist Set; soll true sein,
// wenn kant.k1->kant.k2 oder kant.k2->kant.k1 nicht enthalten ist
            kants.add(kant);

Sprachlich ist das etwas schwer. Gegeben sei k1 und k2. Wenn k1->k2 enthalten ist, dann soll contains true liefern. Wenn k2->k1 enthalten ist, dann soll contains true liefern.
Hieße verneint, dass beide oder keins von beiden enthalten sind?

8

Ein Test sollte doch nicht so schwer sein

Edge e0 = new Edge(v0, v1, -1);
Edge e1 = new Edge(v1, v0, -1);
if (!e0.equals(e1)) throw new SomethingWrongException("Booyah!");
9

Wieso machst du es dir so schwer? Wenn du bei der Instanzierung von Kant-Objekten stets darauf achtest, dass Knot 1 kleiner Knot 2 ist, wird es keine Kanten geben, bei denen Knot 1 größer Knot 2 ist und folglich können solche Kanten auch nicht in irgend einer Collection landen. Ein diesbezüglicher Test (siehe Post von Marco13) sollte zeigen, dass ein Test auf Knot 1 größer Knot 2 innerhalb einer Contains-Methode vollkommen überflüssig sind.

10

Bin begeistert, es funktioniert:

    @Override
    public int hashCode() {
        int hash = this.k1.hashCode() ^ this.k2.hashCode();
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Kant other = (Kant) obj;
        return k1.equals(other.k1) && k2.equals(other.k2)
                || k1.equals(other.k2) && k2.equals(other.k1);
    }

(+ ist kommutativ, ich hätte doch auch + schreiben können…)

gd1.PNG986×993 40.6 KB

Es lag wahrscheinlich daran: Gegeben sein a->b und b->a. Set-contains findet bei b->a eine Hashkollision (a->b wurde vorher eingefügt), DANACH sagte equals aber: Ne, b->a ist ungleich a->b, und diese Kante wurde (in denselben bucket) eingefügt.

Das Thema darf als gelöst betrachtet werden. Aber wem gebührt jetzt die Ehre, es gelöst zu habn? TMII lag nicht falsch, Marco hatte den richtigen Code, Spacerat hat es super erklärt…

Marco hatte als erster den richtigen Code… Ihm gebührt die Ehre. Falls falsch, bitte umändern. :slight_smile: