Grundlagen Der Künstlichen Intelligenz an der TU München | Karteikarten & Zusammenfassungen

Lernmaterialien für Grundlagen der künstlichen Intelligenz an der TU München

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Grundlagen der künstlichen Intelligenz Kurs an der TU München zu.

TESTE DEIN WISSEN

What are Heuristics in general?

Lösung anzeigen
TESTE DEIN WISSEN
  • refer to art of achieving good solutions with limited knowledge and time based on experience
Lösung ausblenden
TESTE DEIN WISSEN

What is the basic idea behind Greedy Best-First Search?

Lösung anzeigen
TESTE DEIN WISSEN
  • expands node that is closest to goal by using just heuristic function so that f(n) = h(n)
Lösung ausblenden
TESTE DEIN WISSEN

What is the performance of Greedy Best-First Search?

Lösung anzeigen
TESTE DEIN WISSEN
  • Completeness: Yes, if graph search is used, otherwise no
  • Optimality: No
  • Time complexity: worst case is that heuristic is misleading to search such that solution is found last O(b^m); good heuristic can improve
  • Space complexity: equals time complexity since all nodes are stored: O(b^m)
Lösung ausblenden
TESTE DEIN WISSEN

What is the idea behind A* search?

Lösung anzeigen
TESTE DEIN WISSEN
  • evaluates nodes by combining path cost g(n) and estimated cost to goal h(n): f(n) = g(n) + h(n)
  • h(n) has to be admissible (underestimation)
    • f(n) never overestimates cost of goal
    • algorithm keeps searching for paths that might have lower cost to goal than those found prevoiusly
Lösung ausblenden
TESTE DEIN WISSEN

What is an admissible heuristic?

Lösung anzeigen
TESTE DEIN WISSEN
  • Underestimation, has to be less than actual cost
Lösung ausblenden
TESTE DEIN WISSEN

What is a consistent/monotonic heuristic? When is it required?

Lösung anzeigen
TESTE DEIN WISSEN
  • for given cost of transactions c(n,a,n') , we have that for all nodes n and its successors n':
    • h(n) <= c(n,a,n') + h(n')
  • every consistent heuristic is admissible
  • required for applying A* with graph search
Lösung ausblenden
TESTE DEIN WISSEN

What is the effect of the heuristic in A* Search?

Lösung anzeigen
TESTE DEIN WISSEN
  • Heuristic "steers" search towards goal
  • A* expands nodes in order of increasing f value, so that "f-contours" of nodes are gradually added
  • Each contour i includes all nodes with f <= fi where fi < fi+1
Lösung ausblenden
TESTE DEIN WISSEN

What is pruning in A* Search?

Lösung anzeigen
TESTE DEIN WISSEN
  • Given cost C* of optimal path, only paths with f(n) <= C* are expanded
    • equality occurs when heuristic returns exact remaining costs
  • Pruning = eliminating possibilities from consideration without having to examine them
    • brings enormous time savings
Lösung ausblenden
TESTE DEIN WISSEN

What is the performance of A* Search?

Lösung anzeigen
TESTE DEIN WISSEN
  • Completeness: Yes, if costs are greater than 0 (otherwise infinite optimal paths of zero cost exist)
  • Optimality: Yes (if cost positive); heuristic has to be admissible for tree-search version and consistent for graph-search version
  • Time complexity: only consider easiest case: State space has single goal and all actions are reversible: O(b^(e*d)
    • relative error e = (h*-h)/h*
    • h is estimated and h* actual cost from root to goal
  • Space complexity: same as time complexity since all nodes are stored
Lösung ausblenden
TESTE DEIN WISSEN

Which alternatives to A* Search did we see? What is a disadvantage of A*?

Lösung anzeigen
TESTE DEIN WISSEN
  • Disadvantage: huge space consumption possible
  • Iterative-deepening A* : adapts idea of iterative deepening to A*; main difference is that f-cost (g+h) is used for cutoff rather than depth
  • Recursive best-first search: simple recursive algorithm with linear space complexity; Structure is similar to recursive depth-first-search, but keeps track of f-value of best alternative path
  • Memory-bounded A* and simplified memory-bounded A*: These algorithms work just like A* until memory is full; drop less promising paths to free memory
Lösung ausblenden
TESTE DEIN WISSEN

How do we characterize the quality of a heuristic?

Lösung anzeigen
TESTE DEIN WISSEN
  • effective branching factor b*
  • Given:
    • Number of nodes N generated by A* search
    • Uniform tree with depths d (each node has same fractional # b* of children)
  • N+1 = 1 + b* + b*^2 + ... + (b*)^d
  • makes it possible to compare heuristic applied to problems of different size
Lösung ausblenden
TESTE DEIN WISSEN

How does informed search work? Which constraints does a heuristic function have?

Lösung anzeigen
TESTE DEIN WISSEN
  • uses indications how promising state is to reach a goal
  • can find solutions more efficiently than uninformed search
  • choice of next node is based on evaluation function f(n) (often called heuristic function h(n))
    • h(n) is problem specific with only constraint that it is nonnegative and h(^n) = 0 where ^n is goal node
Lösung ausblenden
  • 337861 Karteikarten
  • 7634 Studierende
  • 331 Lernmaterialien

Beispielhafte Karteikarten für deinen Grundlagen der künstlichen Intelligenz Kurs an der TU München - von Kommilitonen auf StudySmarter erstellt!

Q:

What are Heuristics in general?

A:
  • refer to art of achieving good solutions with limited knowledge and time based on experience
Q:

What is the basic idea behind Greedy Best-First Search?

A:
  • expands node that is closest to goal by using just heuristic function so that f(n) = h(n)
Q:

What is the performance of Greedy Best-First Search?

A:
  • Completeness: Yes, if graph search is used, otherwise no
  • Optimality: No
  • Time complexity: worst case is that heuristic is misleading to search such that solution is found last O(b^m); good heuristic can improve
  • Space complexity: equals time complexity since all nodes are stored: O(b^m)
Q:

What is the idea behind A* search?

A:
  • evaluates nodes by combining path cost g(n) and estimated cost to goal h(n): f(n) = g(n) + h(n)
  • h(n) has to be admissible (underestimation)
    • f(n) never overestimates cost of goal
    • algorithm keeps searching for paths that might have lower cost to goal than those found prevoiusly
Q:

What is an admissible heuristic?

A:
  • Underestimation, has to be less than actual cost
Mehr Karteikarten anzeigen
Q:

What is a consistent/monotonic heuristic? When is it required?

A:
  • for given cost of transactions c(n,a,n') , we have that for all nodes n and its successors n':
    • h(n) <= c(n,a,n') + h(n')
  • every consistent heuristic is admissible
  • required for applying A* with graph search
Q:

What is the effect of the heuristic in A* Search?

A:
  • Heuristic "steers" search towards goal
  • A* expands nodes in order of increasing f value, so that "f-contours" of nodes are gradually added
  • Each contour i includes all nodes with f <= fi where fi < fi+1
Q:

What is pruning in A* Search?

A:
  • Given cost C* of optimal path, only paths with f(n) <= C* are expanded
    • equality occurs when heuristic returns exact remaining costs
  • Pruning = eliminating possibilities from consideration without having to examine them
    • brings enormous time savings
Q:

What is the performance of A* Search?

A:
  • Completeness: Yes, if costs are greater than 0 (otherwise infinite optimal paths of zero cost exist)
  • Optimality: Yes (if cost positive); heuristic has to be admissible for tree-search version and consistent for graph-search version
  • Time complexity: only consider easiest case: State space has single goal and all actions are reversible: O(b^(e*d)
    • relative error e = (h*-h)/h*
    • h is estimated and h* actual cost from root to goal
  • Space complexity: same as time complexity since all nodes are stored
Q:

Which alternatives to A* Search did we see? What is a disadvantage of A*?

A:
  • Disadvantage: huge space consumption possible
  • Iterative-deepening A* : adapts idea of iterative deepening to A*; main difference is that f-cost (g+h) is used for cutoff rather than depth
  • Recursive best-first search: simple recursive algorithm with linear space complexity; Structure is similar to recursive depth-first-search, but keeps track of f-value of best alternative path
  • Memory-bounded A* and simplified memory-bounded A*: These algorithms work just like A* until memory is full; drop less promising paths to free memory
Q:

How do we characterize the quality of a heuristic?

A:
  • effective branching factor b*
  • Given:
    • Number of nodes N generated by A* search
    • Uniform tree with depths d (each node has same fractional # b* of children)
  • N+1 = 1 + b* + b*^2 + ... + (b*)^d
  • makes it possible to compare heuristic applied to problems of different size
Q:

How does informed search work? Which constraints does a heuristic function have?

A:
  • uses indications how promising state is to reach a goal
  • can find solutions more efficiently than uninformed search
  • choice of next node is based on evaluation function f(n) (often called heuristic function h(n))
    • h(n) is problem specific with only constraint that it is nonnegative and h(^n) = 0 where ^n is goal node
Grundlagen der künstlichen Intelligenz

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Grundlagen der künstlichen Intelligenz an der TU München

Für deinen Studiengang Grundlagen der künstlichen Intelligenz an der TU München gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Grundlagen der künstlichen Intelligenz Kurse im gesamten StudySmarter Universum

Künstliche Intelligenz

Universität zu Lübeck

Zum Kurs
Gundlagen der Künstlichen Intelligenz

TU München

Zum Kurs
Künstliche Intelligenz

FOM Hochschule für Oekonomie & Management

Zum Kurs
Künstliche Intelligenz

Hochschule der Medien Stuttgart

Zum Kurs
Künstliche Intelligenz 1

Leibniz Universität Hannover

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Grundlagen der künstlichen Intelligenz
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Grundlagen der künstlichen Intelligenz