Frage zu Referenzen



  • Hallo,
    ich habe jetzt den A* Algorithmus umgesetzt(vom Pseudocode von wikipedia), das Programm terminiert auch und erreicht das Zielfeld, nur werden dabei anscheinend die Referenzen auf den Vorgängerknoten nicht richtig gesetzt(Ich kann den Pfad also nicht rekonstruieren). In meiner Node Klasse habe ich eine Methode die von einem Feld alle Nachbarfelder zurück gibt. Ich vermute das der Algorithmus soweit richtig ist, weil ich, wie schon gesagt den Pseudocode verwendet habe. Warum werden die Referrenzen auf die Vorgänger nicht gesetzt?

       class Node {
    
     public:	
    	Node *previous;
    	std::pair<int, int> point;
    	int f = 0, h = 0, g = 0;
    
       std::vector<Node> getNeighbors() {
       			std::vector<Node> neighbors;
       			neighbors.reserve(4); //max. 4 Nachbarfelder, oben unten, rechts, links
                               ...
       			std::pair<int, int> p(x, y);
       			Node n(this, p);
       			neighbors.push_back(n);
       				
       			}
       			return neighbors;
       		}
    

    Meine aStar Methode sieht so aus:

                while (!openList.empty()) {
       
       		Node current = *openList.begin(); // Node mit kleinste f-wert
       		std::cout << current.previous << std::endl; // gibt immer selbe Adresse
                        std::vector<Node> neighbors = current.getNeighbors();
                        		
                        		for (Node neighbor : neighbors) {
                                 ....


  • @member42 sagte in Frage zu Referenzen:

    Warum werden die Referrenzen auf die Vorgänger nicht gesetzt?

    Das ist für uns unmöglch zu wissen, vmtl hast du dieses Setzen nicht oder nicht richtig programmiert. Das push_back ne const ref nimmt, ist dir aber klar?



  • @TGGC sagte in Frage zu Referenzen:

    Das push_back ne const ref nimmt, ist dir aber klar?

    Ne, was meinst du den damit?



  • Ich hatte dich im anderen Thread schon vor Kopien im Set gewarnt. Möglicherweise hast du jetzt genau das Problem.



  • @manni66 sagte in Frage zu Referenzen:

    Ich hatte dich im anderen Thread schon vor Kopien im Set gewarnt. Möglicherweise hast du jetzt genau das Problem.

    Ist das ein Problem vom Set oder allgemein?Wie kann ich die Kopien den verhindern?



  • @member42 sagte in Frage zu Referenzen:

    @manni66 sagte in Frage zu Referenzen:

    Ich hatte dich im anderen Thread schon vor Kopien im Set gewarnt. Möglicherweise hast du jetzt genau das Problem.

    Ist das ein Problem vom Set oder allgemein?Wie kann ich die Kopien den verhindern?

    Das betrifft alle Stellen, an denen Node und nicht Node* verwendet wird: Container, return einer Funktion ...



  • @member42 sagte in Frage zu Referenzen:

    Ist das ein Problem vom Set oder allgemein?Wie kann ich die Kopien den verhindern?

    Das ist kein Problem, das ist die Designphilosopie der std. Das willst du auch gar nicht verhindern, sondern lernen wir man es benutzt.



  • Vielen Dank @manni66 für den Tipp mit den Kopie. Es funktioniert jetzt(Ich hatte den Fehler die ganze Zeit woanders gesucht)! Wie du geschrieben hattest, verwende ich jetzt bei allen Methoden Node* statt Node. Gibt es keine einfachere Möglichkeit als mit Node* und mit new immer neue Objekte zu erstellen? Irgendwo habe ich gelesen das new in den meisten Fällen vermieden werden sollte, vermutlich habe ich jetzt einige Memoryleaks in meinem Programm(weil ich die Objekte wahrscheinlich nicht richtig delete).



  • Dafür solltest du Smart-Pointer wie unique_ptr<T> oder shared_ptr<T> verwenden...



  • @member42 sagte in Frage zu Referenzen:

    Gibt es keine einfachere Möglichkeit als mit Node* und mit new immer neue Objekte zu erstellen?

    Du könntest einen Container und die Adressen der Knoten darin verwenden. Du musst aber darauf achten, dass sich die Adressen nicht mehr ändern, wenn sie schon in Verwendung sind. Ein std::vector verschiebt die Objekte beim Einfügen eines Neuen z.B. gelegentlich. std::deque nicht, wenn nur am Ende eingefügt wird. std::set und std::list ändern die Adresse nie.

    Vorsicht mit shared_ptr: wenn du es schaffst, die Knoten in einem Kreis zu verküpfen, werden sie auch damit nie gelöscht.



  • @manni66
    Dazu gibt es weak_ptr.



  • @DocShoe sagte in Frage zu Referenzen:

    @manni66
    Dazu gibt es weak_ptr.

    Wenn alles weak_ptr sind, sind die Knoten auch ganz schnell wieder weg. IMHO sind shared_ptr für Graphen nicht wirklich hilfreich.



  • @manni66 sagte in Frage zu Referenzen:

    Ein std::vector verschiebt die Objekte beim Einfügen eines Neuen z.B. gelegentlich. std::deque nicht, wenn nur am Ende eingefügt wird.

    So lange man nur an den beiden Enden einfügt oder löscht, ja. Sobald man in der Mitte was macht verschiebt sich bei deque genau so alles.



  • @manni66 sagte in Frage zu Referenzen:

    IMHO sind shared_ptr für Graphen nicht wirklich hilfreich.

    Naja das kommt auf die Art des Graphen an. DAGs sollten schön gehen.



  • Der eigentliche Graph kann problemlos in einem std::vector<Node> liegen, er ändert sich ja nicht während der Berechnung nicht und ist konstant. Die Elemente da drin könnten dann natürlich woanders mit Referenz oder Pointern benutzte werden, man kann aber dann genauso einfach den Index nutzen. Die Nachbarfunktion dess Knoten gibt also dann einfach ein paar Indizes aus. Da kann nicht viel schief gehen, new ist auch nicht nötig.


Log in to reply