Your peers in the course KI at the Universität Freiburg im Breisgau create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

KI

What is Uninformed search?

No information on the length or cost of a path to the solution

- BFS
- DFS
- DFS-Limited

KI

What is Informed search?

Knowledge of the worth of expanding a node *n* is given in the form of an *evaluation function* *f(n)*, which assigns as a component a *heuristic function h(n)*, which estimates the costs of the cheapest path from *n* to the goal.

KI

What is Breadth-First Search?

- Nodes are expanded in the order they were produced
- Always finds the shallowest goal state first
- Completeness is obvious
- The solution is optimal if every action has identical and non-negative costs

KI

What is Depth-First Search?

- Always expands an unexpanded node at the greatest depth
- The solution found is not optimal
- Completeness can be guaranteed only for graph-based search and finite state spaces

KI

What is Depth-Limited Search?

- Depth-First Search with an imposed cutoff on the max depth of a path
- Use much less memory than BFS

KI

Space Complexity of DFS

Tree Based: O(bm)...m is max length of path in the state space and b is number of children of each node

Graph Based: bounded by the size of the state space

KI

Time Complexity of DFS

Tree Based: O(b^m)

Graph Based: in the worst case, all states need to stored in the explored set

KI

What is Iterative Deepening Search?

- Use DLS and in every iteration increase search depth by one
- Since the first steps are always repeated looks a bit like a waste of resources
- Combines BFS and DFS

KI

Space Complexity of IDS

O(bd)...d is depth of solution

KI

Time Complexity of IDS

O(b^d)

KI

What is Best-First Search?

is informed search procedure that expands the node with the "best" *f*-value first, e.g. explores a graph by expanding the most promising node chosen according to a specified rule

KI

What is Greedy Search?

a possible way to judge the "worth" of a node is to estimate its path-costs to the goal

*h(n)* = estimated path-costs from *n* to the goal

Greedy Search uses *h(n)* as the evaluation function and expands node with __lowest ____h(n)__

For your degree program KI at the Universität Freiburg im Breisgau there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to Universität Freiburg im Breisgau 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 KI at the Universität Freiburg im Breisgau 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