Suchprobleme repräsentieren Flashcards
Woraus besteht ein Suchproblem?
Ein Suchproblem besteht aus einem Startzustand s_0, einem Zielzustand ZT und einer Menge von Aktionen a_i mt assoziierten Aktionskosten c_i.
Was ist der Zieltest bei einem Suchproblem?
Eine boolesche Funktion ZT: S -> bool, die für jeden Zustand berechnet, ob er eine Lösung darstellt.
Was macht eine Aktion in einem Suchproblem?
a:S->S überführt den aktuellen Zustand in einen eindeutigen Nachfolgezustand.
Was macht eine Aktion in einem Suchproblem neben der
Überführung in einen neuen Zustand?
Es entstehen Aktionskosten c:A->R.
Ist es in der Regel besser viele konkrete Aktionen zu definieren oder wenige abstrakte Aktionen um ein Suchproblem zu beschreiben?
wenige abstrakte Aktionen.
Was wird als Pfad der Länge k in einem Suchproblem bezeichnet?
Eine Sequenz von Aktionen (a_1, … , a_k) sodass im jeweiligen Zustand s_i die Aktion a_i anwendbar ist und in den Folgezustand s_i+1 führt.
Wann ist ein Pfad eine Lösung für ein Suchproblem?
Wenn a_0 wendbar in s_0 ist und a_n den Zieltest erfüllt.
Wie werden die Pfadkosten eines Pfades (a_0, … , a_n) berechnet?
c_0 + … + c_n
Wie werden die Pfadkosten in einem Suchproblem auch noch gennant?
akkumulierte Aktionskosten.
Wann ist eine Lösung für ein Suchproblem optimal?
Wenn die Pfadkosten minimal sind.
Wann spricht man von uniformen Aktionskosten bei einem Suchproblem?
Wenn jede Aktion die gleichen Kosten hat.
Was ist ein Problemraum von einem Suchproblem?
Das ist ein Graph bei dem die Konten alle möglichen Zustände sind und die Kanten die Aktionen repräsentieren.
Warum kann es sinnvoll sein einen Problemraum zu verwenden anstelle von einer normalen Suche?
Weil man z.B. die kürzesten Pfade ausgehend von einem Startknoten mit dem Djisktra-Algorithmus in quadratischer Zeit lösen kann was normal ein NP-schweres Problem wäre. Aber Achtung. Ist der Problemgraph nicht gegeben lohnt es sich meist vom Zeitaufwand nicht diesen zu Berechnen.
Welche Eigenschaften muss ein Suchproblem erfüllen, damit es eine adäquat gelöst werden kann?
- Begrenzter Problemraum: endliche viele Zustände
- Begrenzter Aktionionsraum: endlich viele Aktionen
- Einfach anwendbare Aktionen: geringe Laufzeitkomplexität für sowohl den Test auf die Anwendbarkeit der Aktion als auch auf die Erzeugung des Nachfolgezustands
- Einfacher Zieltest: gerine Laufzeitkomplexität für die Überprüfung ob ein Zustand ein Ziel ist.
Was sind Beispiele für Fragestellungen die zwar mit einem Suchproblem gelöst werden können, aber es wahrscheinlich andere Verfahren gibt die besser geeignet sind?
- Existiert ein Zustand?
- Suche nach allen möglichen Lösungen: bei der Durchsuchung des gesamten Problemraums ist das Suchverfahren zumeist ineffizient
- Maximierungsprobleme: Die Suchbaumverfahren terminieren mit minimalen Pfad und sind meist für Maximierungsprobleme sehr schwierig zu formulieren
- Komplexes Optimialitätskriterium: wenn das Optimalitätsketerium nicht nur von den Pfadkosten abhängt ist dieses nicht mittels Suche zu Lösen.
