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

disadvantages of A* and alternatives

- huge space consumption

alternatives:

- iterative-deepening A*: f cost is used for cutoff
- recursive best-first search
- memory-bounded A*

Grundlagen der Künstlichen Intelligenz

what is an effective branching factor b*?

- way of characterizing the quality of a heuristic
- indicator: if its small, the heuristic is good
- independent of problem size

Grundlagen der Künstlichen Intelligenz

What is the difference between assertions and queries in First-Order Logic

Sentences added to knowledge base using TELL = Assertions

Ask questions of knowledge base = queries

Grundlagen der Künstlichen Intelligenz

performance of A* search

- we need relativ error epsilon = (h*-h)/h*, h is estimated, h* is actual cost from root to goal
- completeness: yes, if costs are greater than 0
- optimality: yes (if cost are positive), heuristic admissible for tree-search, consistent for graph-search
- time complexity: O(b^(epsilon*d))
- space complexity: identical to time

Grundlagen der Künstlichen Intelligenz

what is informed search?

- requires problem-specific knowledge
- finds solutions more efficiently than uninformed search
- uses indications whether a state is more promising than another to reach a goal

Grundlagen der Künstlichen Intelligenz

how is choice of next node made?

- based on evaluation function f(n) which is based on heuristic function h(n)
- h(n) is problem specific, non-negative and h(goalnode) = 0

Grundlagen der Künstlichen Intelligenz

what is heuristics?

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

Grundlagen der Künstlichen Intelligenz

idea of greedy best-first search?

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

Grundlagen der Künstlichen Intelligenz

performance of greedy best-first search?

- completeness: yes, but only if graph search is used
- optimality: no
- time complexity: O(b^m)
- space complexity: O(b^m)

Grundlagen der Künstlichen Intelligenz

what is the idea behind A* search?

- combines path cost g(n) and estimated cost to goal h(n): f(n)=g(n)+h(n)
- h(n) has to be admissible, so its an underestimation
- f(n) never overestimates the cost to goal so algorithm searches paths that might have a lower cost

Grundlagen der Künstlichen Intelligenz

Will A* expand nodes, where f(n)>= C*( the optimal path cost)?

no

Grundlagen der Künstlichen Intelligenz

What is the constraint of the heuristic function for informed search?

h(n*) = 0, if n* is a goal node

For your degree program Computer Science 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 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

1## Learning Plan

2## Flashcards

3## Summaries

4## Teamwork

5## Feedback