KI an der Bergische Universität Wuppertal | Karteikarten & Zusammenfassungen

Lernmaterialien für KI an der Bergische Universität Wuppertal

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen KI Kurs an der Bergische Universität Wuppertal zu.

TESTE DEIN WISSEN

What is Informed search?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

Lösung anzeigen
TESTE DEIN WISSEN
• 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
Lösung ausblenden
TESTE DEIN WISSEN

What is Depth-First Search?

Lösung anzeigen
TESTE DEIN WISSEN
• 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
Lösung ausblenden
TESTE DEIN WISSEN

What is Depth-Limited Search?

Lösung anzeigen
TESTE DEIN WISSEN
• Depth-First Search with an imposed cutoff on the max depth of a path
• Use much less memory than BFS
Lösung ausblenden
TESTE DEIN WISSEN

Space Complexity of DFS

Lösung anzeigen
TESTE DEIN WISSEN

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

Lösung ausblenden
TESTE DEIN WISSEN

Time Complexity of DFS

Lösung anzeigen
TESTE DEIN WISSEN

Tree Based: O(b^m)

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

Lösung ausblenden
TESTE DEIN WISSEN

What is Iterative Deepening Search?

Lösung anzeigen
TESTE DEIN WISSEN
• 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
Lösung ausblenden
TESTE DEIN WISSEN

Space Complexity of IDS

Lösung anzeigen
TESTE DEIN WISSEN

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

Lösung ausblenden
TESTE DEIN WISSEN

Time Complexity of IDS

Lösung anzeigen
TESTE DEIN WISSEN

O(b^d)

Lösung ausblenden
TESTE DEIN WISSEN

What is Best-First Search?

Lösung anzeigen
TESTE DEIN WISSEN

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

Lösung ausblenden
TESTE DEIN WISSEN

What is Greedy Search?

Lösung anzeigen
TESTE DEIN WISSEN

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)

Lösung ausblenden
TESTE DEIN WISSEN

What is Uninformed search?

Lösung anzeigen
TESTE DEIN WISSEN

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

• BFS
• DFS
• DFS-Limited
Lösung ausblenden
• 188755 Karteikarten
• 1846 Studierende
• 111 Lernmaterialien

Beispielhafte Karteikarten für deinen KI Kurs an der Bergische Universität Wuppertal - von Kommilitonen auf StudySmarter erstellt!

Q:

What is Informed search?

A:

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.

Q:

A:
• 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
Q:

What is Depth-First Search?

A:
• 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
Q:

What is Depth-Limited Search?

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

Space Complexity of DFS

A:

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

Q:

Time Complexity of DFS

A:

Tree Based: O(b^m)

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

Q:

What is Iterative Deepening Search?

A:
• 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
Q:

Space Complexity of IDS

A:

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

Q:

Time Complexity of IDS

A:

O(b^d)

Q:

What is Best-First Search?

A:

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

Q:

What is Greedy Search?

A:

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)

Q:

What is Uninformed search?

A:

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

• BFS
• DFS
• DFS-Limited

Erstelle und finde Lernmaterialien auf StudySmarter.

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

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang KI an der Bergische Universität Wuppertal

Für deinen Studiengang KI an der Bergische Universität Wuppertal 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 KI Kurse im gesamten StudySmarter Universum

Ki

Helmut-Schmidt-Universität/ Universität der Bundeswehr

KIB

Leibniz Universität Hannover

ki

Fachhochschule Bielefeld

TU Ilmenau

KIB

Leibniz Universität Hannover