CS37 - Search

Question 1

Trying to figure out what to do in a situation

Answer 1

Search

Question 2

Entity that perceives its environment
and acts upon that environment

Answer 2

agent

Question 3

a configuration of the agent and
its environment

Answer 3

state

Question 4

the state in which the agent begins

Answer 4

initial state

Question 5

choices that can be made in a state

Answer 5

actions

Question 6

ACTIONS(s) returns the set of actions that can be executed in state s

Answer 6

actions

Question 7

a description of what state results from performing any applicable action in any state

Answer 7

transition model

Question 8

RESULT(s, a) returns the state resulting from
performing action a in state s

Answer 8

transition model

Question 9

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

Answer 9

state space

Question 10

way to determine whether a given state is a goal state

Answer 10

goal test

Question 11

numerical cost associated with a given path

Answer 11

path cost

Question 12

Basis of search problem

Answer 12

• initial state
• actions
• transition model
• goal test
• path cost function

Question 13

a sequence of actions that leads from the initial state to a goal state

Answer 13

solution

Question 14

a solution that has the lowest path cost among all solutions

Answer 14

optimal solution

Question 15

a data structure that keeps track of:
- a state
- a parent
- an action
- a path cost

Answer 15

node

Question 16

what does a node keeps track of

Answer 16

• a state
• a parent
• an action
• a path cost

Question 17

Process of approach

Answer 17

• Start with a frontier that contains the initial state.
  Repeat:
• If the frontier is empty, then no solution.
• Remove a node from the frontier.
• If node contains goal state, return the solution.
• Expand node, add resulting nodes to the frontier

Question 18

Process of Revised Approach

Answer 18

• Start with a frontier that contains the initial state.
• Start with an empty explored set.
  Repeat:
• If the frontier is empty, then no solution.
• Remove a node from the frontier.
• If node contains goal state, return the solution.
• Add the node to the explored set.
• Expand node, add resulting nodes to the frontier if they
  aren’t already in the frontier or the explored set

Question 19

last-in first-out data type

Answer 19

stack

Question 20

what’s the difference between an approach and revised approach

Answer 20

revised approach has an explored set

Question 21

search algorithm that always expands the
deepest node in the frontier

Answer 21

depth-first search

Question 22

search algorithm that always expands the
shallowest node in the frontier

Answer 22

breadth-first search

Question 23

first-in first-out data type

Answer 23

queue

Question 24

search strategy that uses no problem-specific knowledge

Answer 24

uninformed search

Question 25

search strategy that uses problem-specific
knowledge to find solutions more efficiently

Answer 25

informed search

Question 26

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

Answer 26

greedy best-first search

Question 27

search algorithm that expands node with
lowest value of g(n) + h(n)

Answer 27

A* search

Question 28

A* search is optimal if:

Answer 28

• h(n) is admissible (never overestimates the
  true cost), and
• h(n) is consistent (for every node n and
  successor n’ with step cost c, h(n) ≤ h(n’) + c)

Question 29

What does DFS use

Answer 29

stack

Question 30

What does BFS use

Answer 30

queue

Question 31

Approach process

Answer 31

Start with a frontier that contains the initial state
Repeat:
If the frontier is empty, then no solution
Remove a node from the frontier
If node contains goal state, return the solution
Expand node, add resulting nodes to the frontier

Question 32

What could go wrong with the approach?


Answer 32

There is a possibility that it will enter an endless loop and the goal can never be found

Question 33

Revised Approach process

Answer 33

Start with a frontier that contains the initial state
Start with an empty explored set
Repeat:
If the frontier is empty, then no solution
Remove a node from the frontier
If node contains goal state, return the solution
Add the node to the explored set
Expand node, add resulting nodes to the frontier if they aren’t already in the frontier or the explored set

Question 34

What’s the difference between approach and revised approach?


Answer 34

Revised Approach has an explored set