WorksheetsTut 10 Heuristic A*
Total questions: 6
Worksheet time: 4mins
Was sind wahre Aussagen über heuristische Algorithmen?
Heuristische Algorithmen funktionieren nur bei kleinen Problemgrößen.
Heuristische Algorithmen garantieren die optimale Lösung.
Heuristische Algorithmen liefern oft gute, aber nicht notwendigerweise optimale Lösungen.
Heuristische Algorithmen nutzen Näherungsverfahren oder Erfahrungswerte, um Entscheidungen zu treffen.
Welche Aussagen zu Approximationsalgorithmen sind wahr?
Ein p-Approximationsalgorithmus liefert eine Lösung, deren Kosten höchstens p-mal so schlecht sind wie die optimale Lösung.
Jedes NP-schwere Problem lässt sich mittels eines p-Approximationsalgorithmus approximieren.
Ein p-Approximationsalgorithmus für Maximierungsprobleme liefert immer eine optimale Lösung, solange p groß genug ist.
Wenn ein Problem approximierbar ist, kann p beliebig gewählt werden.
Der A*- Algorithmus
benutzt eine Heuristik um die kürzesten Pfade in Richtung eines Zielknotens schenller zu finden
relaxiert jede Kante nur einmal wenn die Heuristik konsistent ist.
findet kürzere Pfade als der Dijkstra Algortihmus wenn die Heuristik zulässig ist.
ist ein approximativer Algortihmus.
Ist diese Heuristik zulässig?
Ist diese Heuristik konsistent?
Welche dieser Regeln gelten immer bei einer konsistente Heuristik?
h(n):= Heuristikfunktion eines Knoten n
c(n,n'):= Kantengewicht der Kante zwischen Knoten n zu n'
d(n) := minimale tatsächlichen Kosten zum Ziel vom Knoten n
Wenn für alle Knoten n und deren Nachfolger n′ gilt:
h(n)-h(n′)≤c(n,n′)
Wenn für alle Knoten n und deren Nachfolger n′ gilt:
h(n)≤h(n′)
Die Heuristik überschätzt immer die tatsächlichen Kosten zum Ziel, also
d(n) < h(n)
für alle Knoten n.
Jede konsistente Heuristik ist auch immer zulässig.
