Uniformed/Informed searches

Question 1

What are the uninformed searches?

Answer 1

DFS, DFS + Iterative Deepening, BFS

Question 2

What are the informed searches?

Answer 2

Best FS, Hill Climbing, Branch and Bound Techniques, A* Algo, Simulated annealing, Tabu Search

Question 3

Why do we generate state space at run time?

Question 4

What is a state space?

Answer 4

A set of descriptions of states

Question 5

Should a tree or graph be used when a state can be visited more than once?

Answer 5

graph

Question 6

How do search algorithms for trees differ from search algorithms for graphs?

Answer 6

Graphs need to cater for possible loops and cycles

Question 7

What are the types of problems?

Answer 7

Problem that only need a representation
Problem that require a yes or no response indicating whether a solution can be found or not.
Problems that require a solution path

Question 8

How does DFS work?

Answer 8

go to the left and down as far as possible, backtrack to split and then go right down as far as possible

Question 9

How does BFS work?

Answer 9

Go down in layers, start from left to right on each layer

Question 10

How does DFS with iterative deepening work?

Answer 10

Only go down to the level that has been specified, If level has been reached go to next nodes and dont continue further down

Question 11

How is BFS better than DFS?

Answer 11

BFS is guaranteed to find the shortest path from the start to the goal
DFS may get lost in search and hence a depth-bound may have to be imposed on a dfs

Question 12

Why is BFS bad?

Answer 12

Has a bad branching factor (lead to combinatorial explosion)

Question 13

When is DFS more efficient?

Answer 13

When the search space has many branches (+ branches = + branching factor)

Question 14

What is the criteria to decide which search to use?

Answer 14

How important is it to find the shortest path to goal.
branching, time and resources
Average length of paths to a goal node

Question 15

How does Heuristic searches choose which node to visit?

Answer 15

It uses the domain-specific knowledge to choose

Question 16

What is a weak search method?

Answer 16

A search method that include the use of domain knowledge in the form of a heuristic.

Question 17

What are examples of heuristic searches?

Answer 17

Best FS, A* algorithm, hill-climbing

Question 18

Why is domain knowledge incorporated into search process by means of heuristics?

Answer 18

To speed up the search process

Question 19

Are heuristic functions completely accurate?

Answer 19

No

Question 20

What are heuristics?

Answer 20

rules of thumb that may find a solution (not guaranteed)

Question 21

What is the range for heuristic values?

Answer 21

> =0

Question 22

What does a heuristic value of 0 mean?

Answer 22

current state = goal state

Question 23

When is a heuristic admissible?

Answer 23

When is never overestimates the cost to the goal

Question 24

What is the value of a heuristic if the state is a dead end?

Answer 24

infinity

Question 25

What is a property of a good heuristic?

Answer 25

Must not take long to compute

Question 26

Where are heuristics defined on?

Answer 26

on a simplified/relaxed version of the problem

Question 27

When is H1 expanded less nodes than H2 during the search. which heuristic function is better?

Answer 27

H1

Question 28

What is the problem with heuristic functions?

Answer 28

Difficult to devise

Question 29

How does Best FS work?

Answer 29

Min cost nodes are expanded first

Question 30

Does Best FS always find the shortest solution?

Answer 30

No

Question 31

What is the purpose of Best FS?

Answer 31

To minimize the cost of finding a solution

Question 32

Which 2 searches does Best FS combine?

Answer 32

BFS and DFS

Question 33

How is Hill Climbing different from Best FS?

Answer 33

Hill Climbing = Local states, Best FS = considers global states

Question 34

What does A Algorithm combine?

Answer 34

Best FS + f(n) = g(n) + h(n)
g(n) = measures length of the path from any state to the start state
h(n) = heuristic measure from the state to the goal state
( g(n) = amount of steps that has been taken from the start state)

Question 35

What is the evaluation function used by admissible algorithms?

Answer 35

f(n) = g(n) + h(n)
g(n) = actual cost of path from start to current
h*(n) = actual cost from node to goal node

Question 36

True or false. Most of the time we cant compute h*(n) in the admissible function?

Answer 36

True.

Question 37

What is the Best FS used with f(n) called?

Answer 37

A Algorithm

Question 38

When does does the A algorithm become the A* algorithm?

Answer 38

When h(n) <= h*(n)

Question 39

What techniques are used to find the most optimal solutions?

Answer 39

Branch and Bound