Problem mit Set



  • Hallo,

    für den A* Algorithmus wollte ich für die openlist ein Set nehmen. Das Set wird nach dem f-Wert sortiert.

       class Node {
       	
       	public:
       		Node *previous;		
       		std::pair<int, int> point;
       		int f;
       
       		Node(Node *previous, std::pair<int, int> point) {
       			this->previous = previous;
       			this->point = point;
       		}
       
       		bool operator< (const Node &node) const { // sortieren
       			return f < node.f;
       		}
    

    Füge ich jetzt z.B sowas zum Set hinzu, bekomme ich als Set Größe 1 ausgegeben.

        std::set<Node> openList;
        Node n1(nullptr, start); // haben alle f-wert 0, aber unterschiedliche Punkte-pairs
        Node n2(&n1, std::pair<int, int>(1, 0));
        Node n3(&n2, std::pair<int, int>(0, 1));
        openList.insert(n1);
        openList.insert(n2);
        openList.insert(n3);
    

    Ein Set darf ja keine doppelten Werte enthalten, wieso wird aber nur ein Knoten zum Set hinzugefügt?
    Wie kann ich das Problem lösen?


  • Mod

    Dein f ist undefiniert. Aber nehmen wir mal an, du hättest Recht und es wäre tatsächlich alle 0: Wieso wunderst du dich dann? Nach deinem Vergleichskriterium vergleichen die dann doch alle gleich, denn 0 ist gleich 0. Und was ist dein Problem? Wenn du doppelte Werte erlauben möchtest, gibt es dafür Multiset. Wenn du keine doppelten Werte erlauben möchtest, aber die Werte trotzdem als doppelt gelten, dann ist dein Vergleichskriterium falsch.

    Trotzdem ist dein f undefiniert und das ist ganz schlecht.



  • OT: die Knoten werden kopiert. Nach openList.insert(n2); hast du eine Kopie von n2, die auf n1 und nicht auf die Kopie von n1 im Set verweist. Ist das wirklich so gewollt?



  • @SeppJ Ich wundere mich nur, weil das Set nach f-werten sortiert wird, die Knoten die ich hinzufüge aber offensichtlich nicht gleich sind, weil sie ja andere pairs übergeben bekommen. Danke für den Tipp mit Multiset, dann muss ich das wohl verwenden.

    @manni66 sagte in Problem mit Set:

    OT: die Knoten werden kopiert. Nach openList.insert(n2); hast du eine Kopie von n2, die auf n1 und nicht auf die Kopie von n1 im Set verweist. Ist das wirklich so gewollt?

    Wo habe ich da eine Kopie?



  • @member42
    Zeilen 5-7



  • @member42 sagte in Problem mit Set:

    Ich wundere mich nur, weil das Set nach f-werten sortiert wird,

    Das Sortieren ist nur ein Nebeneffekt. Das Set benutze deinen operator< für den Vergleich. point ist also für den Vergleich egal.



  • Ich verwende jetzt ein Multiset statt eines Sets. Wie kann ich überprüfen ob ein Knoten im Set enthalten ist(nach den Punkt-koordinaten und nicht nach dem f-wert)?
    Ich hatte folgendes versucht:

        if (openList.find(Node(nullptr, std::pair<int, int>(3, 0))) != openList.end() ) {
    	std::cout << "In Liste" << std::endl;
    }
    

    Was aber immer "In Liste" ausgibt, obwohl der Knoten nicht im Set ist. Wahrscheinlich funktioniert find auch mit dem <operator, und deswegen funktinoiert es nicht.


  • Mod

    @member42 sagte in Problem mit Set:

    @SeppJ Ich wundere mich nur, weil das Set nach f-werten sortiert wird, die Knoten die ich hinzufüge aber offensichtlich nicht gleich sind, weil sie ja andere pairs übergeben bekommen. Danke für den Tipp mit Multiset, dann muss ich das wohl verwenden.

    Häh? Hier ist dein Widerspruch. Sie werden nach f-Werten sortiert. Deine f-Werte sind (Nachdem du endlich dein Programm korrigierst!) gleich. Also sind die Elemente aus Sicht des Sets gleich. Worüber wunderst du dich? Der andere Kram fließt doch gar nicht ein bei dir.



  • Ein set in C++ ist eine geordnete Menge an Dingen. Die Ordnung legst du hier mit dem operator< fest. Dadurch kannst du ein Element in logarithmischer Zeit finden. Selbstverständlich wird diese Sortierung von find genutzt.

    Jetzt scheinst du aber ein anderes Kriterium zu haben. Du könntest natürlich std::find benutzen und nach dem Punkt suchen. Aber das wäre ja eine lineare Suche in O(n) über das gesamte Set. Bist du sicher, dass du das willst?

    Übrigens bedeutet dein operator< nicht (in erster Linie): "Das Set wird nach dem f-Wert sortiert", wie du es schreibst. Sondern es bedeutet eher: "Es gibt eine definierte Ordnung meiner Nodes, diese leitet sich aus dem f-Wert ab."

    Daraus ergibt sich dann, weil du beim set<Node, Compare, Alloc> keinen Compare-Parameter angegeben hast, dass das set ebenfalls nach std::less sortiert wird. Wenn ein set nach einem Wert sortiert sein soll, die Elemente aber eigentlich keine Ordnung haben oder logisch anders geordnet sind, würde ich operator< für die logisch sinnvolle Sortierung verwenden und dem set eine benutzerdefinierte Vergleichsfunktion geben.



  • @wob Danke wob, mit std::find klappt es. Wie müsste den eine eigene Vergleichsfunktion ungefähr aussehen?
    Habe jetzt sowas versucht, bekomme aber den Fehler das es zu viele Parameter sind:

         struct compare {
     bool operator< (const Node &node1, const Node &node2) const {
    	return node1.f < node2.f;
    }
    
    bool operator==(const Node &node1, const Node &node2) {
    	return node1.point == node2.point;
           }
    };
    

    @SeppJ sagte in Problem mit Set:

    @member42 sagte in Problem mit Set:

    @SeppJ Ich wundere mich nur, weil das Set nach f-werten sortiert wird, die Knoten die ich hinzufüge aber offensichtlich nicht gleich sind, weil sie ja andere pairs übergeben bekommen. Danke für den Tipp mit Multiset, dann muss ich das wohl verwenden.

    Häh? Hier ist dein Widerspruch. Sie werden nach f-Werten sortiert. Deine f-Werte sind (Nachdem du endlich dein Programm korrigierst!) gleich. Also sind die Elemente aus Sicht des Sets gleich. Worüber wunderst du dich? Der andere Kram fließt doch gar nicht ein bei dir.

    Ich glaube ich habs jetzt einigermaßen verstanden.



  • @member42 sagte in Problem mit Set:

    Wie müsste den eine eigene Vergleichsfunktion ungefähr aussehen?

    Default für compare ist std::less, wie man hier sieht. Schau doch dort einfach mal nach, wie das bei std::less gemacht ist. Zum Beispiel hier. Du macht eine Klasse, wo du den operator() implementierst.

    Noch was zu deinen beiden Funktion < und ==. Normalerweise folgt aus a < b oder b < a, dass a != b ist. Wenn a nicht kleiner als b ist und b nicht kleiner als a ist, dann sind a und b gleich. Wenn du deine Funktionen wie oben implementierst, dann würde das nicht mehr gelten. Das ist schlecht! Mach das nicht!

    Weiterführend: bilde dich zum Thema "ordering". Zum Beispiel hier: https://stackoverflow.com/questions/18781405/partialordering-strictweakordering-totalordering-whats-the-main-difference-i - bestimmt gibt es auch bessere Quellen.



  • @wob Also ist es nicht möglich 2 "getrennte Funktionen" zu haben, eine fürs sortieren nach dem f-Wert und eine equals(um zu sehen ob bestimmte Punkte enthalten sind)?


  • Mod

    @member42 sagte in Problem mit Set:

    @wob Also ist es nicht möglich 2 "getrennte Funktionen" zu haben, eine fürs sortieren nach dem f-Wert und eine equals(um zu sehen ob bestimmte Punkte enthalten sind)?

    Natürlich kannst du das machen. Du kannst auch eine Funktion operator+ schreiben, die alle Argumente auf 0 setzt. Oder einen operator&&, der die Werte auf die Festplatte schreibt. Ob das eine gute Idee ist, die übliche Semantik von mathematischen Operatoren ohne Not zu verletzen, darf aber bezweifelt werden.

    Dein Problem ist nach wie vor, dass du wahrscheinlich das Problem nicht verstanden hast. Wenn du Vergleiche nur nach f machst, wie können dann Dinge ungleich sein, obwohl sie gleiches f haben? Das kannst du zwar so programmieren, aber das macht keinen logischen Sinn. Daher macht dein Programm komische, unerwartete Dinge. Weil es zwar technisch richtig ist, aber logisch falsch ist.

    Vielleicht fehlt dir die Idee, dass man Dinge auch nach mehr als einem Kriterium sortieren kann? Die Wörter im Lexikon sind zwar nach Anfangsbuchstaben sortiert. Aber zu jedem Buchstaben gibt es viele Wörter, die eben nicht alle gleich sind. Und sie sind dann untereinander auch noch weiter sortiert, nämlich nach dem zweiten Buchstaben, etc.



  • @SeppJ sagte in Problem mit Set:

    Dein Problem ist nach wie vor, dass du wahrscheinlich das Problem nicht verstanden hast. Wenn du Vergleiche nur nach f machst, wie können dann Dinge ungleich sein, obwohl sie gleiches f haben? Das kannst du zwar so programmieren, aber das macht keinen logischen Sinn. Daher macht dein Programm komische, unerwartete Dinge. Weil es zwar technisch richtig ist, aber logisch falsch ist.

    Mir geht es nur darum das Set nach f-werten zu sortieren und dann zu schauen ob das Set bestimmte Punkte-pairs enthält. Ich weiß nicht, warum das keinen Sinn macht.

    @SeppJ sagte in Problem mit Set:

    Natürlich kannst du das machen. Du kannst auch eine Funktion operator+ schreiben, die alle Argumente auf 0 setzt. Oder einen operator&&, der die Werte auf die Festplatte schreibt. Ob das eine gute Idee ist, die übliche Semantik von mathematischen Operatoren ohne Not zu verletzen, darf aber bezweifelt werden.

    Bei Stackoverflow habe ich jetzt gelesen das es anscheinend nicht möglich ist Vergleichs und Sortierfunktion bei einem Set zutrennen(https://stackoverflow.com/questions/1114856/stdset-with-user-defined-type-how-to-ensure-no-duplicates). Ansonsten könnte ich std::find verwenden, was dann aber von der Laufzeit schlechter wäre. Wie würdest du das den ungefähr machen? (wie @wob meinte).


  • Mod

    Ich bin ziemlich sicher, du hast es immer noch nicht verstanden, aber ich weiß auch nicht so recht, was ich noch genauer erklären sollte, was nicht eine Wiederholung von schon Gesagtem wäre.

    Jedenfalls ist doch dein Problem trivial zu lösen indem du das Sortierkriterium wie gesagt erweiterst. Das löst sowohl dein Problem, und es macht auch dein Programm intern logisch konsistent. Ich kapier nicht, wieso du das nicht verstehst.



  • @SeppJ sagte in Problem mit Set:

    Jedenfalls ist doch dein Problem trivial zu lösen indem du das Sortierkriterium wie gesagt erweiterst. Das löst sowohl dein Problem, und es macht auch dein Programm intern logisch konsistent. Ich kapier nicht, wieso du das nicht verstehst.

    Mein Problem ist, ich weiß nicht wie wie ich das Sortierkriterium erweitern soll. Habe in der Nodeklasse noch ==operator hinzugefügt, was aber auch nichts geändert hat.

               bool operator< (const Node &node) const {
    		return f < node.f;
    	}
    
    	bool operator== (const Node &node) const {
    		return point == node.point;
    	}

  • Mod

    @member42 Versuch mal, die beiden obigen Operatoren zu implementieren, sodass die folgende Identitaet gilt:

    a=b¬(a<b)¬(b<a)a = b \Leftrightarrow \lnot (a < b) \land \lnot (b < a)

    Tatsaechlich wird das von jedem strict weak ordering erwartet, siehe http://eel.is/c++draft/concept.strictweakorder.

    Dabei spielt es keine Rolle, wie der operator== letzten Endes definiert ist, denn er wird nie aufgerufen (deshalb ist deine Konklusion im vorigen Post nicht ueberraschend), aber es wird Dir helfen, operator< kohaerent zu implementieren.



  • @Columbo sagte in Problem mit Set:

    @member42 Versuch mal, die beiden obigen Operatoren zu implementieren, sodass die folgende Identitaet gilt:

    a=b¬(a<b)¬(b<a)a = b \Leftrightarrow \lnot (a < b) \land \lnot (b < a)>

    Wie soll ich den f mit point vergleichen?


  • Mod

    Vielleicht solltest Du erstmal einen Schritt zurückgehen und überlegen, wie genau zwei Node Objekte verglichen werden könnten. Wenn f im Objekt A größer ist als von B, aber point kleiner ist, wie stehen A und B zueinander? Wiegt f mehr, analog zu dem ersten Buchstaben in einem Wörterbuch (wie SeppJ suggeriert hat)? Oder sind sie gleichwertig? Hierbei ist noch anzumerken, dass point, welches eine Spezialisierung von pair ist, implizit eine lexikographische Ordnung hat (das erste Element first wiegt mehr als das zweite).

    Du könntest alternativ eine multimap nehmen, nach f sortieren und dann, um ein spezifisches Objekt zu finden, durch equal_range alle Instanzen eines spezifischen fs finden und linear nach dem point absuchen. Das bedeutet allerdings auch, dass mehrere Instanzen die völlig identisch sind existieren können.



  • @Columbo sagte in Problem mit Set:

    Vielleicht solltest Du erstmal einen Schritt zurückgehen und überlegen, wie genau zwei Node Objekte verglichen werden könnten. Wenn f im Objekt A größer ist als von B, aber point kleiner ist, wie stehen A und B zueinander? Wiegt f mehr, analog zu dem ersten Buchstaben in einem Wörterbuch (wie SeppJ suggeriert hat)? Oder sind sie gleichwertig? Hierbei ist noch anzumerken, dass point, welches eine Spezialisierung von pair ist, implizit eine lexikographische Ordnung hat (das erste Element first wiegt mehr als das zweite).

    Das Set soll nach f-werten sortiert werden , Objekte A und B sollen aber als gleich gelten wenn die points gleich sind(unabhänig von f).


Log in to reply