Problem bei rekursion und Call byRef



  • Hallo, ich habe ein Problem mit der Rekursion und Parametern die byRef übergeben werden:
    Und zwar habe ich einen Baum realsiert über eine Datenstruktur von links (from, to). Jeder dieser Knoten hat eine ID.
    Ich suche also jetzt einen Weg von Knoten 4 nach 7. Dabei will ich den Baum in einer Art Breitensuche durchwandern um eine Weg von 4 nach 7 zu finden...

    bool experience_map_mean::graphsearch(std::vector<std::vector<Link_mean> >& _links, std::vector<int> pc_ids_from, uint pc_id_to, std::vector<int> &path) {
    
    	std::vector<int> childs;
    	int from;
    
    	if (pc_ids_from.size() <= 0) {
    		return false;
    	}
    	for (uint h=0; h < pc_ids_from.size(); h++) {
    		from = pc_ids_from.at(h);
    
    		for (uint i = 0; i < _links.at(from).size(); i++) {
    			if ((!(_links.at(from).at(i).visited)) && (_links.at(from).at(i).delta_time_s > 0)) {
    				_links.at(from).at(i).visited = true;
    
    				if (i == pc_id_to) { //found
    					path.push_back(from);
    					path.push_back(pc_id_to);
    					return true;
    
    				} else {
    					childs.push_back(i);
    				}
    			} //if visited
    		}
    	}
    
    		bool _bool = graphsearch(_links, childs, pc_id_to, path);	
    		if (_bool) {
    			path.insert(path.begin(), pc_ids_from.front());
    			return true;
    	}
    	return false;
    }
    

    Nach ein paar Durchläufen bekomme ich immer einen "Speicherzugriffsfehler" an der Stelle, wo die Rekursion immer wieder aufgerufen wird.

    Wenn ich _links nicht als Ref, sondern byVal übergebe, dann bekomme ich den Fehler nicht.

    bool experience_map_mean::graphsearch(std::vector<std::vector<Link_mean> > _links, std::vector<int> pc_ids_from, uint pc_id_to, std::vector<int> &path) {
    

    Leider ist der Vektor sehr groß und daher ein ständiges kopieren nicht wirklich vorteilhaft.

    Hat jmd. eine Idee, warum das mit ByRef nicht geht?



  • So auf die Schnelle nicht. Mach mein ein minimales kompilierbares Beispiel, dann schau ichs mir mal an.



  • Okay. Das Problem liegt daran, dass

    bool _bool = graphsearch(_links, childs, pc_id_to, path);
    

    aufgerufen wird, childs aber manchmal leer sein kann.

    Das kann ich ja einfach beheben, indem ich die Größe checke.

    Jetzt habe ich aber ein anderes Problem: Ich bin davon ausgegangen, dass ich eine einfache Vorwärtssuche von der Wurzel zum Knoten habe. Das ist leider nicht so, denn ich habe auch rückwärtige Links von z.B. 5 -> 6 -> 2 -> 7.

    Ich habe mir einen 2D Vector angelegt Vec[from][to], welcher Alle Verküpfungen von nach speichert. Ich prüfe, ob in einem Vectorelement gültige Daten stehen und nur dann verarbeite ich das Element. Dennoch habe ich eine zu hohe Laufzeit.

    Wie bekomm ich die Suchzeit runter? - Mein Vector besteht teilweise aus [20000][20000] Elementen, von denen aber nur 10% mit Daten gefüllt sind.



  • Sortieren und unbenutzte Teile einfach bei der Suche auslassen ?


Anmelden zum Antworten