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

- 370640 Karteikarten
- 8657 Studierende
- 341 Lernmaterialien

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

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

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

Jetzt loslegenFü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!