Your peers in the course Grundlagen der künstlichen Intelligenz at the TU München create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Grundlagen der künstlichen Intelligenz

What are Heuristics in general?

- refer to art of achieving good solutions with limited knowledge and time based on experience

Grundlagen der künstlichen Intelligenz

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

- expands node that is closest to goal by using just heuristic function so that f(n) = h(n)

Grundlagen der künstlichen Intelligenz

What is the performance of Greedy Best-First Search?

- 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)

Grundlagen der künstlichen Intelligenz

What is the idea behind A* search?

- 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

Grundlagen der künstlichen Intelligenz

What is an admissible heuristic?

- Underestimation, has to be less than actual cost

Grundlagen der künstlichen Intelligenz

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

- 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

Grundlagen der künstlichen Intelligenz

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

- 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

Grundlagen der künstlichen Intelligenz

What is pruning in A* Search?

- 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

Grundlagen der künstlichen Intelligenz

What is the performance of A* Search?

- 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

Grundlagen der künstlichen Intelligenz

Which alternatives to A* Search did we see? What is a disadvantage of 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

Grundlagen der künstlichen Intelligenz

How do we characterize the quality of a heuristic?

- 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

Grundlagen der künstlichen Intelligenz

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

- 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

For your degree program Grundlagen der künstlichen Intelligenz at the TU München there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to TU München overview pageCheck out courses similar to Grundlagen der künstlichen Intelligenz at other universities

Back to TU München overview pageStudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Grundlagen der künstlichen Intelligenz at the TU München or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Best EdTech Startup in Europe

X

X## Good grades at university? No problem with StudySmarter!

### 89% of StudySmarter users achieve better grades at university.

## Learn with over 1 million users on StudySmarter.

50 Mio Flashcards & Summaries

Create your own content with Smart Tools

Individual Learning-Plan

Already registered? Just go to Login