Search

Question 1

Defining a state space

Answer 1

When solving a problem, we start by defining what each “state” looks like and how states transition from one to another. Each state represents a possible configuration of the problem at a particular point in time. Basically the set of all possible configurations.

Question 2

Pruning strategies

Answer 2

Systematically eliminate certain states from consideration to reduce search space and improve efficiency

Question 3

Search strategies

Answer 3

Strategies for deciding how to explore the state space. Different strategies determine the order in which states are considered

Question 4

Navigating the Frontier

Answer 4

In search algorithms, the “frontier” is the set of states that are ready to be explored next. For ex. BFS, states are explored layer by layer, while DFS, states are explored by diving deep into one path before backtracking

Question 5

Search Heuristics

Answer 5

guide the search process by estimating how close a given state is to the goal. Heuristics help the search algorithm to be more efficient

Question 6

Completeness

Answer 6

Will the search always find a solution of a solution exits

Question 7

Optimality

Answer 7

Will the search always fin the least cost solution if actions have cost

Question 8

Time Complexity

Answer 8

What is the maximum number of nodes that can be expanded or generated

Question 9

Space Complexity

Answer 9

What is the maximum number of nodes that have to be stored in memory

Question 10

Uninformed Search strategies

Answer 10

-Adopt a fixed fule for choosing the next state to be expanded.
- They don’t take into account any domain specific information about a specific search problem
- Ex. BFS, uniform-cost, DFS

Question 11

Uniform Cost search

Answer 11

BFS but frontier is sorted in increasing cost of the path. It always expands the least cost node

Question 12

Dept limited search

Answer 12

DFS but to a pre-specified depth limit L. No node over L steps is on the frontier.
This eliminates infinite length paths problem

Question 13

Iterative deepening search

Answer 13

Dept limit search but starting at depth limit L=0 and iteratively increase the depth limit, doing a DLS for each depth limit

Question 14

Cycle Checking/ Path checking

Answer 14

Ensure that the state c is not equal to the state reached by any ancestor of c along this path

Question 15

merit of a frontier node

Answer 15

A measure that helps decide the order in which nodes should be expanded
- “Cost of solution” notion of merit

Question 16

Greedy best-first search

Answer 16

Greedily trying to achieve a low cost solution

Question 17

h(n)

Answer 17

heuristic estimate of the cost of getting to a goal node from n
- it is always an underestimates of the true cost

Question 18

A* search

Answer 18

Always expand the node with lowest f-value on the frontier
f(n)= g(n) + h(n)
g(n) is the cost of the path to node n
h(n) is the heuristic estimate of the cost of getting to a goal node from n

Question 19

Monotone consistent Heuristic

Answer 19

h(n1) <= c(n1->n2) + h(n2)
c(n1->n2) is the actual of the step from n1 to n2
-Monotonicity implies admissibility

Question 20

Local Search

Answer 20

This algorithm operate using a single Current State and generally move to neighbours of that state

Question 21

Why search

Answer 21

Successful: in game playing, and other AI problems can be solved
Practical: Useful in approximation

Question 22

What search show

Answer 22

Search only shows how to solve the problem once we have it correctly formulated

Question 23

TreeSearch

Answer 23

TreeSearch(Frontier, Successors, Goal?)

Question 24

BFS time complexity

Answer 24

O(b^(d+1)

Question 25

Admissibility

Answer 25

idea of h(n) understating the true cost
h(n) <= h*(n)

Question 26

Suduko_bruteforce

Answer 26

?- game(easy, Ls), solve(Ls).

Looks for the possible choices for each slot, then uses the first choice, then back tracks

• only one solution

Question 27

Sudoku_forward

Answer 27

Removing choices. If the guess does not conflict with the guesses for previous cells, it advances(forwarded)

Question 28

Sudoku_dynamic

Answer 28

Chooses the choices with fewer choices available
This is pruning

Question 29

World_path

Answer 29

Changes one letter at a time to go from start word to finish word. word_path(horse, mouse, Ps).
Ps= [horse, morse, mouse] ;
ps=[horse, morse, moise, mouse];
ps=[horse, morse, moise, moose, mouse];
Ps=[horse, morse, moose, mouse];

Question 30

Pigeon-hole: Heuristics_Sudoku(Forcing a choice

Answer 30

For all slots in a group with slot S except for S are marked are not possible for X. Therefore, slot S must be X.

Imagine you have several places to put a number, but all spots except one are already ruled out for that number.
The only spot left must then hold that number because there are no other options.

Question 31

Eliminating Choices

Answer 31

In/Out:
The main idea: If a number can’t go anywhere else in the “Out” group, it must go in a shared slot, meaning Slot S can’t be that number. Slot S is in one group not the other
exact Cover: If a group of slots will cover certain numbers exactly, then Slot S can’t use those numbers.

Question 32

Word_trail

Answer 32

Swapping two letters or change one letter
swap_letters_in_world(barber, W).
First letter swapped with second letter, first letter swapped with third letter…..
second letter swapped with third letter…

word_trail(Cat, dog, Trail).
Trail= [cat, cot, dot, dog]

Question 33

bagof(W, swap_letter_in_word(barber,W), Ws)

Answer 33

Ws= list of all swaps

Question 34

bagof(W, swap_letter_in_word(barber,W), Ws), length(Ws, L)

Answer 34

output length