AI

0.0 (0)

R. D.

Study

R. D.

About these flashcards

Diese Lernkarten behandeln fortgeschrittene Themen der künstlichen Intelligenz und Algorithmen, insbesondere Suchstrategien wie Minimax, Alpha-Beta, IDA*, und Heuristiken. Sie vertiefen sich in Methoden wie Forward Checking, Arc Consistency und Hill Climbing, sowie in logische Formeln und Constraint-Satisfaction-Probleme. Diese Karteikarten sind ideal für Studierende und Forscher, die sich mit komplexen Algorithmen und deren Anwendungen in der KI und Informatik auseinandersetzen möchten.

Flashcards

Students

Language

German

Cartes-fiches

Why are tree search algorithms incomplete?

Because state spaces can have an infinite number of states.

Because state spaces can have an infinite number of paths.

Because state spaces can have an infinite number of state transitions.

Because state spaces can have an infinite number of actions.

none of these

Which of the following are advantages of IDA* over A*?

It usually requires much less memory.

It usually requires far fewer node expansions.

It uses simpler data structures.

It is complete.

none of these

Which statements about heuristic search are correct?

All admissible heuristics can be computed efficiently.

If heuristic h is safe, then h(s) = ∞ holds for all unsolvable states s.

The point of heuristics is to direct a state-space search algorithm towards the goal.

Designing a good heuristic often involves a trade-off between computation time and quality of the heuristic estimate.

none of these

Which statements about hill climbing for combinatorial optimization are correct?

Hill climbing can return suboptimal solutions.

Hill climbing can fail on solvable problems.

Hill climbing can detect when a problem is unsolvable.

Hill climbing is very memory-efficient.

none of these

Which statements about inference methods for constraint satisfaction are correct?

Inference methods can be accelerated by using suitable variable ordering strategies in the BacktrackingWithInference algorithm.

Forward checking is a faster inference method than arc consistency.

Path consistency is a faster inference method than arc consistency.

All inferences made by forward checking are also made by arc consistency, but not vice versa.

none of these

NaiveBacktracking uses a form of depth-first search. Which of these are plausible reasons for using a form of breadth-first search instead within NaiveBacktracking?

Breadth-first search could find solutions with lower cost.

Breadth-first search could find solutions more quickly.

Breadth-first search would avoid problems with duplicates.

Breadth-first search would repair the problems that NaiveBacktracking has with unsolvable constraint networks.

none of these

Which of the following statements about logical formulas are correct?

Every valid formula is satisfiable.

Every unsatisfiable formula is valid.

There exist formulas that are both satisfiable and unsatisfiable.

There exist formulas that logically entail each other.

none of these

Which properties does the logical formula (A → (A → B)) have?

satisfiable

falsifiable

valid

unsatisfiable

none of these

Which of the following combinations of search algorithm and heuristic for a planning task are guaranteed to lead to optimal solutions?

Greedy best-first search with the FF heuristic.

IDA* with the LM-cut heuristic.

A* with reopening with the h^(add) heuristic.

Weighted A* with a weight of 2 and the h^(max) heuristic.

none of these

Consider a game tree whose root node is a MAX node for which Minimax computes a utility of 7. Which of the following statements are correct? Unless stated otherwise, the game tree is evaluated until the end (no use of evaluation functions for nonterminal positions). Unless stated otherwise, we make no assumptions about the strategy used by either player.

If MAX follows the Minimax algorithm, the game will end in a terminal position with utility exactly 7.

If MAX follows the Minimax algorithm, the game will end in a terminal position with utility at least 7.

If both players follow the Alpha-Beta search algorithm, the game will end in a terminal position with utility exactly 7.

Alpha-beta search leads to the best possible play, even when using an evaluation function for nonterminal positions that is based on imperfect information.

none of these

FS21

Search algorithm X is semi-complete, but not complete. Which of the following state-

ments about X follow from this?

On a solvable task, X will always terminate with a solution.

On a solvable task, X will always terminate, but not necessarily with a solution.

On an unsolvable task, X will always terminate.

On an unsolvable task, X will never terminate.

none of these

FS21

Which of the following are advantages of graph search over tree search?

Graph search algorithms always find optimal solutions.

Graph search algorithms are usually complete, while tree search algorithms might not even be semi-complete.

Graph search algorithms do not not need to expand multiple nodes with identical states.

Graph search algorithms do not need to keep track of an open list.

None of these

FS21

Which of the following statements about heuristics are correct?

If h1 and h2 are admissible heuristics, then max{h1,h2} is an admissible heuristic.

If h1 and h2 are admissible heuristics, then h1 + h2 is an admissible heuristic.

If h is an admissible heuristic, then 1.5h is an admissible heuristic.

If h is an admissible heuristic, then greedy best-first search with h will find an optimal solution.

none of these

FS21

Which of the following ideas can be said to encourage exploration in a search algorithm for a combinatorial optimization problem?

Using a heuristic to decide which neighbor to move to.

Using a heuristic that is more accurate, but more expensive to compute.

Using random initial states and including restarts.

Moving to random neighbors some of the time.

none of these

FS21

Consider the constraint network ⟨{u,v,w},dom,(Ruv)⟩ with dom(u) = dom(v) = dom(w) = {1, 2, 3} and the only nontrivial constraints R_uv = {(1, 2), (1, 3), (2, 3)} and R_vw = {(1, 2), (1, 3), (2, 3)}. Which of the following are consistent partial assignments?

∅

{u → 1}

{u→3}

{u→1,w→3}

none of these

FS21

Which of the following statements comparing the two inference methods “forward checking” and “arc consistency” are correct?

They require the same computational effort.

Forward checking always produces tighter constraint networks than arc consistency.

Arc consistency always produces tighter constraint networks than forward checking.

Arc consistency only restricts the variable domains, while forward checking also restricts the binary constraints.

none of these

FS21

Let φ = (A∨(A → B)) be a propositional formula over the alphabet Σ = {A, B}. Which of the following statements are true?

φ has exactly 4 models.

φ is valid.

φ is falsifiable.

φ |= (A∨B).

none of these

FS21

Which of these statements about the DPLL algorithm are correct?

It always runs in polynomial time.

It terminates on every input.

It always returns an optimal solution.

If the input formula is satisfiable, it will return a satisfying assignment.

none of these

FS21

Consider a STRIPS planning task Π with 10 state variables. Which of the following statements must be true?

Π has 2^10 states.

Π has 2^10 reachable states.

The delete relaxation of Π has 2^10 states.

Π has exactly one initial state.

none of these

FS21

Which of the following statements about game tree search algorithms are correct?

The runtime of Minimax search grows exponentially with the search depth.

The runtime of Alpha-Beta search grows polynomially with the search depth.

Alpha-Beta search explores forever and is greedy in the limit.

Minimax and Alpha-Beta search compute the same result.

none of these

Étudier

AI

Create or copy sets of flashcards

Cartes-fiches

Veuillez vous connecter

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog