Baumstruktur

[Guest]

Hallo,

ich habe mir eine Baumstruktur aufgebaut. Nun soll allen Knoten des Baumes abhängig von einem Kriterium ein bestimmer Wert zugewiesen werden. Einem Knoten kann nur dann ein Wert zugewiesen werden wenn er entweder keine Nachfolger hat oder aber wenn alle seine Nachfolger bereits bewertet wurden. Könnt ihr mir vielleicht sagen wie der Algorithmus aussehen könnte um die Baumstruktur auf diese Weise zu durchlaufen?

 

[SamHotte]

Den Knoten kann man ansehen, ob sie berechnet wurden? (Bspw. haben sie ein Attribut, das null ist, wenn noch nix berechnet wurde, und sonst einen Wert hat? Falls nicht, könnte man z. B. noch ein boolean 'istBerechnet' einbauen ...)

Dann klingt das nach einem Paradebeispiel für Rekursion:
- fange bei der Wurzel an
- rufe eine Methode 'berechne(knoten)' auf, der du die Wurzel gibst
- diese Methode macht: 1. hole mir die Kinder in ein Array/eine Liste, 2. Schleife über die Kinder: berechne(kind)
- Abbruchbedingung: knoten ist berechnet (siehe oben)

 

[Guest]

Könnt ihr mal drüberschaun ob das so richtig sein könnte?

	public void bewerteBaum(Knoten aktuellerKnoten)
	{
		/* 
	     *  schauen ob bereits alle Nachfolger bewertet wurden. Ist das nicht der 
	     *  Fall Methode rekursiv für noch nicht bewertete Nachfolger aufrufen.
	     *  Das ein Blatt keine Nachfolger hat fällt bei Blättern diese for-Schleife
	     *  weg
	     */	
		for(int i=0; i<aktuellerKnoten.getAnzahlNachfolger(); i++)
		{
			if(aktuellerKnoten.getNachfolgerAt(i).getWert() == 2)
			{
				bewerteBaum(aktuellerKnoten.getNachfolgerAt(i));
			}
		}
		
        /*
         *  nun da alle Nachfolger bewertet wurden kann auch der Knoten selbst bewertet werden.
         *  
         *  Man unterscheidet zwei Fälle: 
         *  
         *  1.) aktueller Knoten ist ein Blatt (hat also keine Nachfolger)
         *  --------------------------------------------------------------
         *  - war beim Vorgängerknoten der Rechner am Zug so hat der Rechner verloren
         *  - laut Aufgabenstellung wird dieser Knoten mit 0 bewertet
         *  - war beim Vorgängerknoten der Spieler am Zug so hat der Rechner gewonnen
         *  - laut Aufgabenstellung wird dieser Knoten mit 1 bewertet
         *  
         *  
         *  2.) aktueller Knoten ist ein innerer Knoten (hat also Nachfolger)
         *  -----------------------------------------------------------------
         *  
         *      Man unterscheidet nun wiederrum zwischen zwei Fällen:
         *  
         *      1.) beim aktuellen Knoten ist der Rechner am Zug
         *      ------------------------------------------------
         *      - der Rechner hat bei der Endstellung 1 gewonnen
         *      - hat der aktuelle Knoten nur eine 1 als Nachfolger so wird er mit 1 bewertet (max-Auswertung) 
         *      - ansonsten mit 0 (Rechner hat definitiv verloren)
         *      
         *      2.) beim aktuellen Knoten ist der Spieler am Zug
         *      ------------------------------------------------
         *      - der Spieler hat bei der Endstellung 0 gewonnen
         *      - hat der aktuelle Knoten nur eine 0 als Nachfolger so wird er mit 0 berwertet (min-Auswertung) 
         *      - ansonsten mit 1 (Spieler hat definitiv verloren)
         */
		for(int i=0; i<aktuellerKnoten.getAnzahlNachfolger(); i++)
		{
			if(aktuellerKnoten.getAnzahlNachfolger() == 0)
			{
				if(aktuellerKnoten.getVorgänger().getTyp().equals("Rechner"))
					aktuellerKnoten.setWert(0);
				else
					aktuellerKnoten.setWert(1);
			}
			else
			{
				if(aktuellerKnoten.getTyp().equals("Rechner"))
				{
					aktuellerKnoten.setWert(0);
					
					for(int j=0; j<aktuellerKnoten.getAnzahlNachfolger(); j++)
					{
						Knoten tempKnoten = aktuellerKnoten.getNachfolgerAt(j);
						if(tempKnoten.getWert() == 1)
							aktuellerKnoten.setWert(1);
					}
				}
				else
				{
					aktuellerKnoten.setWert(1);
					
					for(int j=0; j<aktuellerKnoten.getAnzahlNachfolger(); j++)
					{
						Knoten tempKnoten = aktuellerKnoten.getNachfolgerAt(j);
						if(tempKnoten.getWert() == 0)
							aktuellerKnoten.setWert(0);
					}
				}
			}
		}
		
	}

 

[bygones]

mal so ins Baumblaue geraten...

eine einfache Depth-First-Search

steh ich auf dem Schlauch oder macht die Bedingung "entweder kein kind oder alle kinder bewertet" nicht viel sinn. Dadurch werden ja schonmal alle Blätter markiert. Wenn alle Blätter markiert werden folglich auch alle ihre Eltern. Da dann alle Eltern der Blätter markiert sind folgen deren Eltern usw. ergo werden alle markiert...

oder ist das zeitverschoben ? d.h. zu unterschiedlichen Zeiten werden untersch. Knoten markiert ?