Search

Question 1

An entity that perceives its environment and acts upon that environment.

Answer 1

Agent

Question 2

A configuration of an agent in its environment.

Answer 2

State

Question 3

The state from which the search algorithm starts.

Answer 3

Initial State

Question 4

Choices that can be made in a state.

Answer 4

Actions

Question 5

A description of what state results from performing any applicable action in any state.

Answer 5

Transition Model

Question 6

The set of all states reachable from the initial state by any sequence of actions.

Answer 6

State Space

Question 7

The condition that determines whether a given state is a goal state.

Answer 7

Goal Test

Question 8

A numerical cost associated with a given path.

Answer 8

Path Cost

Question 9

A sequence of actions that leads from the initial state to the goal state.

Answer 9

Solution

Question 10

A solution that has the lowest path cost among all solutions.

Answer 10

Optimal Solution

Question 11

contains the following data:
* A state
* Its parent node, through which the current node was generated
* The action that was applied to the state of the parent to get to the current node
* The path cost from the initial state to this node

Answer 11

node

Question 12

the mechanism that “manages” the nodes

Answer 12

frontier

Question 13

search algorithm that exhausts each one direction before trying another direction

Answer 13

Depth-First Search

Question 14

search algorithm where the frontier is managed as a stack data structure

Answer 14

Depth-First Search

Question 15

Pros and Cons of DFS

Answer 15

Pros:
* At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance), then depth-first search takes the least possible time to get to a solution.
Cons:
* It is possible that the found solution is not optimal.
* At worst, this algorithm will explore every possible path before finding the solution, thus taking the longest possible time before reaching the solution.

Question 16

search algorithm that will follow multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction.

Answer 16

Breadth-First Search

Question 17

search algorithm where the frontier is managed as a queue data structure

Answer 17

Breadth-First Search

Question 18

Pros and Cons of BFS

Answer 18

Pros:
* This algorithm is guaranteed to find the optimal solution.
Cons:
* This algorithm is almost guaranteed to take longer than the minimal time to run.
* At worst, this algorithm takes the longest possible time to run.

Question 19

A type of algorithm that considers additional knowledge to try to improve its performance

Answer 19

Informed Search Algorithm

Question 20

search algorithm that expands the node that is the closest to the goal, as determined by a heuristic function h(n).

Answer 20

Greedy Best-First Search

Question 21

ignores walls and counts how many steps up, down, or to the sides it would take to get from one location to the goal location

Answer 21

Manhattan Distance

Question 22

function that estimates how close to the goal the next node is, but it can be mistaken.

Answer 22

heuristic function

Question 23

The efficiency of the greedy best-first algorithm depends on

Answer 23

how good a heuristic function is

Question 24

considers not only h(n), the estimated cost from the current location to the goal, but also g(n), the cost that was accrued until the current location.

Answer 24

A* Search

Question 25

For a* search to be optimal, the heuristic function has to be:

Answer 25

Admissible & Consistent

Question 26

In the heuristic function h(n) of an A* search algorithm, it is consistent if

Answer 26

for every node n and successor node n' with step cost c, n ≤ n' + c

Question 27

In the heuristic function h(n) of an A* search algorithm, what does it mean to be admissible?

Answer 27

Never overestimates the actual cost to reach a goal from any node

Question 28

algorithm that faces an opponent that tries to achieve the opposite goal.

Answer 28

Adversarial Search

Question 29

represents winning conditions as (-1) for one side and (+1) for the other side.

Answer 29

Minimax

Question 30

Recursively, the algorithm simulates all possible games that can take place beginning at the current state and until a terminal state is reached. Each terminal state is valued as either (-1), 0, or (+1).

Answer 30

Minimax

Question 31

an optimization technique for minimax that skips some of the recursive computations that are decidedly unfavorable

Answer 31

Alpha-Beta Pruning

Question 32

Minimax that considers only a pre-defined number of moves before it stops, without ever getting to a terminal state.

Answer 32

Depth-Limited Minimax

Question 33

estimates the expected utility of the game from a given state, or, in other words, assigns values to states.

Answer 33

Evaluation function