Problem mit Set


  • Mod

    @member42 Mir scheint, dass Deine Anforderungen (ob diese nun sinnvoll sind oder nicht) ueber set hinausgehen.

    Du musst Dir set wie einen Container von Äquivalenzklassen vorstellen. Jedes Element im Set ist in einer Äquivalenzklasse, sprich, einer Menge von Werten die für die Zwecke des Sets als gleich gelten. Wie Du wissen solltest, gibt es keine zwei "gleichen" Objekte in einer Menge. Anders gesagt: Es gibt keine zwei Objekte derselben Äquivalenzklasse. Bspw., ein Set welches positive reelle Zahlen aufgerundet sortiert, hat Aequivalenzklassen, die fuer jede Ganzzahl so bestimmt sind: xZ+(x1,x]x \in \mathbb Z^+ \mapsto (x-1, x], also alle Zahlen, die zu dieser Zahl aufgerundet wuerden. Keine zwei solcher Zahlen können in einem Set mit dieser Relation residieren.

    Die Äquivalenzklassen in die Objekte eingeteilt werden, sind allerdings vollständig durch die Relation bestimmt, die diese Äquivalenzklassen ordnet. Sprich: Die Vergleichsfunktion bildet und sortiert die Äquivalenzklassen. Wenn also Äquivalenzklassen anhand f sortiert werden sollen, dann werden keine zwei Äquivalenzklassen denselben Wert fuer f haben können, und deshalb koennen auch keine zwei Objekte (voellig unabhaengig von point, oder welcher untergeordneten Rolle es in der Vergleichsfunktion spielt) unterschiedlichen fs als äquivalent, oder gleich, betrachtet werden.



  • @Columbo Irgendwie verstehe ich nicht warum das so kompliziert ist. In Java z.B kann ich eine Queue über eine Comparator-funktion sortieren und über eine equals-Methode die Gleichheit von Objekten definieren(nach meinen Kriterien). Mit dieser definierten equals Methode kann ich dann einfach überprüfen ob ein Objekt enthalten ist.

    @Columbo sagte in Problem mit Set:

    @member42 Mir scheint, dass Deine Anforderungen (ob diese nun sinnvoll sind oder nicht) ueber set hinausgehen.

    Also ist es wie ich es mir vorgestellt hatte nicht möglich?
    @SeppJ meinte ja es wäre trivial zu lösen.


  • Mod

    @member42 Wenn Du nach f sortierst, aber dann nach point suchen willst... dann brauchst Du halt eine lineare Suche. Simple as that.



  • . In Java z.B kann ich eine Queue über eine Comparator-funktion sortieren und über eine equals-Methode die Gleichheit von Objekten definieren(nach meinen Kriterien)

    Warum nimmst du dann in C++ ein std::set?

    std:: vector, std::sort mit lambda und std::find machen das Gleiche.



  • Ein set finden einen enthaltenen Wert nicht, indem es alles im Set mit dem == operator vergleicht, sondern indem es auf einige wenige Elemente den < anwendet. Daher kannst du da nicht irgendwelchen Zusammenhanglosen Quatsch programmieren. Das set kann Sachen nur einordnen, finden oder löschen, wenn alle Elemente nach einer totalen Ordnung, die sich aus dem < ergeben hintereinanderliegen und du kannst daher nicht einfach sagen, das irgendwelche Wert gleich oder ungleich sind unabhängig von dieser Ordnung.

    Um bei dem Beispiel des Lexikons zu bleiben, kannst du nicht einfach sagen das die Wort Foto und Photo gleich sind, weil wenn Foto nicht zwischen Ente und Gletscher gefunden wird, schliesst der Algorithmus das F/Photo gar nicht enthalten sein kann weil Ente < F/Photo und F/Photo < Gletscher und wird dann gar nicht auch noch unter den Wörtern mit P nachschauen.



  • @Columbo sagte in Problem mit Set:

    @member42 Wenn Du nach f sortierst, aber dann nach point suchen willst... dann brauchst Du halt eine lineare Suche. Simple as that.

    Ja, das hatte ich auch schon versucht, ich dachte es gäbe nur eine bessere Alternative, weil ich eine möglich gute Laufzeit haben wollte. Aber dann mache ich es jetzt einfach mit std::find(hauptsache es läuft erstmal)

    @manni66 sagte in Problem mit Set:

    . In Java z.B kann ich eine Queue über eine Comparator-funktion sortieren und über eine equals-Methode die Gleichheit von Objekten definieren(nach meinen Kriterien)

    Warum nimmst du dann in C++ ein std::set?

    std:: vector, std::sort mit lambda und std::find machen das Gleiche.

    Habe bei Stackoverflow gelesen, dass ein Set am besten für A* Algorithmus wäre.



  • @member42 Wo musst du denn da nach einem Punkt suchen und das f ignorieren?



  • @wob Ich benutze den Pseudocode von wikipedia. Hier z.B (ist ja unabhängig von f)

                if openlist.contains(successor) and tentative_g >= g(successor) then
                        continue


  • @member42 sagte in Problem mit Set:

    Ja, das hatte ich auch schon versucht, ich dachte es gäbe nur eine bessere Alternative, weil ich eine möglich gute Laufzeit haben wollte.

    Ja und ich habe gerade erklärt, warum diese Idee wiedersinning ist. Die gute Laufzeit wird erreicht, indem nicht == in jedem Objekt aufgerufen wird, sonst ist keine sublineare Laufzeit erreichbar. Und dazu muss das Ergebnis der == Funktion aus der < Funktion logisch erschliessbar sein. Das passiert eben indem alle Objekte in einer eindeuten Reihenfolge angeordnet sind. Es muss gelten wenn A < B und B < C dann auch immer A < C (also z.B. nicht RPS!) und wenn weder A < B noch B < A dann ist A == B.

    Verstehst du überhaupt was schon mehrere Personen versucht haben zu erklären, bzw. versuchst du zu verstehen oder willst du nur auf deiner Meinung "das muss doch gehen weil in Java ist blubb" beharren? Dann stelle ich die Kommunikation an der Stelle nämlich ein.



  • @member42
    Für das A* routing benutzt man eigentlich auch eine Priority Queue. Warum nimmst Du ein Set?



  • @member42 sagte in Problem mit Set:

    Ich benutze den Pseudocode von wikipedia.

    Dort (also in A*-Algorithmus) steht aber auch, daß für die openList eine PriorityQueue (Prioritätenwarteschlange) verwendet wird.

    Nimm also statt dem set dafür std::priority_queue.
    Nur für die closedList nimmst du dann das set<Node>.



  • Das löst aber nicht das Problem des OP, denn man kann ein set problemlos als Priority-Queue verwenden (wenn es auch etwas weniger effizient ist). Auch eine Priority-Queue wird nach einer Bedingung sortiert (bzw man kennt zumindest das Extrem-Element) und es ist auch dort nicht effizient, alle Elemente mithilfe einer anderen Bedingung, die keinen Bezug zur Ordnung hat, zu durchsuchen.

    @member42 Denk darüber nach, warum du die Suche unabhängig von f haben willst oder ob es nicht sinnvoller wäre, wenn die Abhängigkeit von f erlaubt wäre.



  • Ich muss ja Elemente updaten/löschen und bei einer Queue wüsste ich nicht wie das geht. Ich kann zwar das erste Element entfernen, aber nicht mittendrin, weil die Queue ja keinen Iterator hat(So wie ich das gelesen habe, könnte man einen Binary Heap verwenden, der sehr effzient für solche Probleme sein soll). So wie ich das verstanden habe ist ein Set im Grunde ja sehr änhlich zu einer Queue. Aber ich denke ich belasse es erstmal mit std::find im multiset.

    @TGGC sagte in Problem mit Set:

    Verstehst du überhaupt was schon mehrere Personen versucht haben zu erklären, bzw. versuchst du zu verstehen oder willst du nur auf deiner Meinung "das muss doch gehen weil in Java ist blubb" beharren?

    Das mit Java war nur ein Beispiel, weil ich das Gefühl hatte, dass mein Problem nicht deutlich geworden ist.



  • @member42 In Deiner open List must Du nichts updaten. Du must nur den bisherigen Pfad bearbeiten, falls Du eine günstigere route findest als das, was Du bisher hast.

    Das Prinzip der Openlist ist relativ einfach:

    Du ermittelst ausgehend vom aktuellen Knoten alle erreichbaren Knoten und für diese die geschätzen Gesamtkosten (=berrechnete Kosten der bisherigen Route + Schätzung des Rests (z.B. Luftlinienentfernung)) diese Werte (Knoten + Kosten) schiebst Du in die Priority Queue. Dann holst Du Dir den nächsten Knoten aus der Queue. Wenn dessen vorheriger Knoten identisch mit deinem aktuellen Knoten ist, hängst Du ihn an den bisherigen Pfad, machst ihn zum aktuellen Knoten und gehst wieder auf Start. Wenn nicht, mußt Du halt Deinen bisherigen Pfad ändern.

    Das machst Du solange bis Du die Route gefunden hast oder die openList leer ist. Im letzteren Fall gibt es halt keine Route von A nach B.

    Wenn A* richtig implementiert ist, ist die erste gefundene Route auch die beste.



  • @mgaeckler

    @mgaeckler sagte in Problem mit Set:

    Du must nur den bisherigen Pfad bearbeiten, falls Du eine günstigere route findest als das, was Du bisher hast.

    Das meinte ich ja glaube ich mit updaten.

    Bei wiki steht z.B folgendes:

           if openlist.contains(successor) then
               openlist.updateKey(successor, f)

Anmelden zum Antworten