[C++11] std::priority_queue ohne contains() und decreaseKey()

Treue Seele

12.02.2014, 21:50

[C++11] std::priority_queue ohne contains() und decreaseKey()

Hi, ich bin gerade dabei A* mit C++11 zu implementieren und musste gerade feststellen, dass die std::priority_queue gar keine contains()-Methode o.Ä. enthält, es mir also nicht möglich ist zu prüfen, ob mein Knoten mit kürzerem Pfad bereits in der OpenList enthalten ist.

Welche Möglichkeiten habe ich jetzt weiterzumachen? Bis auf das contains habe ich alles implementieren können xD Muss ich jetzt auf boost::heap::priority_queue ausweichen? :dash:

LG Glocke

EDIT: auch decreaseKey() fehlt mir (siehe Seite 2)

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Glocke« (16.12.2014, 11:31)

Zum Seitenanfang

Checkmateing

Community-Fossil

Beiträge: 2 218

12.02.2014, 22:46

Nein, wenn es unbedingt 'ne priority_queue sein muss, dann kannst du dir doch auch einfach einen eigenen Container basteln, der auf priority_queue basiert und die contains-Methode implementiert.
Zum Beispiel so:

C-/C++-Quelltext

#include <queue>

template<class t, class con = std::vector<t>, class cmp = std::less<typename con::value_type>
class Priority_Queue_With_Function_Contains : public std::priority_queue<t, con, cmp>
{
public:
    bool contains(const t& val) const
    {
        auto first = this->c.cbegin();
        auto last = this->c.cend();
        while(first!=last)
        {
            if(*first==val)
                return true;
            ++first;
        }
        return false;
    }
};

MfG
Check

Das gibt Übersicht! Stay gold.

Zum Seitenanfang

Supermoderator

Wohnort: Graz

12.02.2014, 23:00

Wofür genau brauchst du ein contains()?

m4studios

Zum Seitenanfang

Treue Seele

12.02.2014, 23:08

Zitat von »dot«

Wofür genau brauchst du ein contains()?

Um zu prüfen ob ich zur aktuellen Position bereits eine mit kürzeren g-Wert (d.h. kürzeren Pfad) gefunden habe.

Naja mein nächstes Problem: decreaseKey -.-

Zum Seitenanfang

Supermoderator

Wohnort: Graz

12.02.2014, 23:19

std::priority_queue hat kein contains(), weil

Priority Queues rein konzeptionell nichts mit einer derartigen Operation zu tun haben und
diese Operation sich für diese Datenstruktur nicht effizient implementieren lässt.

Wenn du contains() willst, willst du ein Set und keine Priority Queue. Wenn du eine Priority Queue willst, willst du kein contains(). Wenn du tatsächlich meinst, beides zu wollen, dann willst du sehr wahrscheinlich eigentlich etwas ganz Anderes...

Man könnte sich z.B. auch in jedem Knoten den Vorgängerknoten sowie zugehörigen g-Wert merken, über den er erreicht wurde. Damit braucht man dann keine Closed List mehr, muss nichtmehr die Open List durchsuchen und hat implizit auch schon das Backtracking drin, wenn ich mich nicht irre...

m4studios

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »dot« (12.02.2014, 23:28)

Zum Seitenanfang

Treue Seele

13.02.2014, 00:19

Naja, ich hatte mich an an den Wegfindung mit A*-Artikel imWiki gehalten, wo auf die Vorrangwarteschlage (priority queue) hingewiesen wurde. Und sofern ich mich erinnere, haben wir in der Vorlesung "Algorithmen und Datenstrukturen" ewig lange über Heap-Implementierungen (mit decreaseKey) gesprochen, die für PriorityQueues verwendet werden - nur, dass ich keine PrioQue-Implementierung finde, die decreaseKey anbietet... (das mit dem contain war aus dem bösen Wikipedia

)

Naja auf jeden Fall hab ich das ganze jetzt mit std::set für Open- und ClosedList implementiert: läuft gut

Zum Seitenanfang

Supermoderator

Wohnort: Graz

13.02.2014, 00:22

Bei diesen "Heap Implemetierungen", wurde da auch behandelt, wie man in einem Heap effizient suchen kann?

Wenn du nun ein Set für die Open List verwendest, wie genau findest du den nächsten zu betrachtende Knoten?

m4studios

Zum Seitenanfang

Treue Seele

13.02.2014, 08:38

Zitat von »dot«

Bei diesen "Heap Implemetierungen", wurde da auch behandelt, wie man in einem Heap effizient suchen kann?

Ja, aber ich bin ehrlich gesagt zu faul mir einen Min-Heap zu implementieren. C++ bietet nur Max-Heap Funktionalität an (afaik!).

Zitat von »dot«

Wenn du nun ein Set für die Open List verwendest, wie genau findest du den nächsten zu betrachtende Knoten?

In §O(n)§

Keine schöne Lösung, aber erstmal so, dass ich damit arbeiten kann

Ich könnte auch operator< und operator== überladen - werde ich vermutlich auch machen, um das ganze später (wenn mir die Performance nicht mehr ausreicht) zu optimieren.

Zum Seitenanfang

Supermoderator