Algorithmen für Suchbäume Flashcards
Wie sieht der Pseudocode vom Grundlegenden Suchbaumalgorithmus aus?
Was wird beim Grundlegenden Suchbaumalgorithmus als Expandierung bezeichnet?
Der Schritt bei dem auf dem aktuellen Knoten alle anwendbaren Aktionen ausgeführt werden und so die Folgezustände generiert werden und in den Problemraum mit aufgenommen werden.
Wie sieht der Pseudocode des alternativen Algorithmuses mit Speicherung der Pfade für das Suchproblem aus?
Was ist der Vorteil des Algorithmuses mit Pfaden gegenüber dem grundlegenden Suchbaumalgorithmuses?
Gelingt der Zieltest muss nicht erst der Pfad konstruiert werden.
Was ist der Nachteil des Algorithmuses mit Pfaden gegenüber dem grundlegenden Suchbaumalgorithmuses?
Der Speicheraufwand ist erheblich größer.
Nach welchen Kriterien beurteilt man die Qualität eines konkreten Suchalgorithmuses?
- Vollständigkeit: der Algorithmus findet garantiert in endlicher Zeit eine Lösung falls diese existiert.
- Optimalität: der Algorithmus liefert die Lösung mit minimalen Pfadkosten
- Laufzeitkomplexität: Laufzeit des Algorithmus lässt sich mti der Zahl der Schleifeniterationen für ein unlösbares Suchproblem abschätzen. “Jeder Knoten wird nur einmal durchlaufen”
- Speicherkomplexität: Speicherkomplexität = max Anzahl gleichzeitig im Speicher liegender Knoten.
Hinweis: Optimalität unf Vollständigkeit sind nur für nicht negative Aktionskosten garantiertbar.
Was ist der Verzweigungsgrad von einem Suchbaum?
Die maximale Anzahl an Nachfolgern, die ein Zustand besitzen kann.
Was ist die Tiefe eines Suchbaums?
Die Länge des längsten Pfades
