Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

COSC343 > State Space Search > Flashcards

State Space Search Flashcards

1
Q

state space search

A

represented using a search tree or search graph it is about finding a sequence of actions to lead from an initial state/position to a goal state without knowing how to get there

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

state

A

representation of the problem at a given point in time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

actions

A

set of all possible moves

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

transition model

A

describes result of applying action to a sate given the environment (rules)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

state-space

A

math representation of all possible states that a system can be in with actions to go from one to another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

completeness

A

always finding a solution if one exists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

optimality

A

finding the least costly solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

time complexity in terms of big 0

A

nodes generated/expanded
how run time grows as a function of input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

space complexity in terms of big 0

A

max nodes in memory

how much memory required grows as function of input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

uninformed search

A

single agent
systematically exploring state space without use of knowledge to guide the agent until finds goal state
inefficient unintelligent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

uninformed search has the following features

A

initial state
transition model (rules)
set of possible actions
goal test

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

node in state space search has

A

represents a state in the search tree incl extra info like action that led to i, parent node, depth, costs)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

path vs step cost

A

path is total cost of total cost associated with a particular sequence of actions
step cost is cost incurred moving from one state to another or taking a single action

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

how is search strategy determined?

A

dependant on order of nodes in fringe are expanded

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

if search algorithm picks first node determined by

A

how new nodes are added

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

if search algorithm picks last node determined by

A

which node picked to expand

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

4 types of tree searches

A

Breadth first
depth first
death limited
iterative depth

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

BFS, what, complete, optimal and space/time

A

expand nodes in order of adding them to the fringe
work across all in one depth before going down
yes will complete if there is a solution
not optimal in general
space and time expo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

DFS, what, complete, optimal and space/time

A

explores nodes as far as possible along a branch before backtracking via stack
complete if finite depth not complete if in inf depth
not optimal
space linear
time expo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

DLS what, complete, optimal and space/time

A

DFS with limited depth
prevents inf loop
complete if depth is enough to find solution
not optimal
space linear
time expo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

IDS, what, complete, optimal

A

combines space efficiency of DFS with completeness of BFS
complete
not optimal in general
space linear
time expo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

tree vs graph search

A

tree explores hirearchical structures with single root, simple but doesn’t;t check for repeated states so wastes time and space
graph searches explore connections accounting for cycles, keeps closed list of repeated states expanded so far so only adds new node is state is not found on list but takes additional memory to track visited states

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

informed search

A

single agent
systematically exploring state space with use of knowledge to prioritise node expansion on those that are more likely to lead it to the goal state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

informed search features

A

initial state
set of possible actions
transition model (rules)
goal test (evaluation function to evaluate with respect to reaching goal)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

informed search picks the node to expand with the

A

best evaluation function

26
Q

3 types of uninformed search

A

uniform cost search
greedy search
A*

27
Q

uniform cost search, what, how, optimal, complete

A

variant of BFS prioritising nodes based on their path cost
expands nodes in increasing order (lowest first) and only looks back to cost of getting so far
finds optimal route
complete if action cost >0 but not in terms of space and time complexity
explores lots of possibilities and gives the optimal route

28
Q

greedy search, what, how, optimal, complete

A

only looks forward to goal state
chooses node to expand with lowest heuristic
won’t give optimal route like last time but finds the goal state a lot quicker
not optimal as might prioritise nodes that lead to dead ends

29
Q

heuristic, what and how used

A

evaluate how promising a prticular state or action is in reaching the goal
aim to reduce the search space by prioritizing certain paths.

30
Q

A*, what complete, optimal

A

uses actual accumulated cost so far and heuristic to estimate cost to reach the goal node
complete unless inf nodes
optimal if TS admissible heuristic and GS consistent heuristic

31
Q

adversial search

A

multi-agent
finds optimal strategy for one player while anticipating opponents move
models consequences of an action by modelling what action the other play may take
essential in 0 sum games (when one player gains the other loses resulting in 0 utility)

32
Q

adversial search features

A

initial state
possible actions
transition model
terminal test
utility function (agent’s subjective value of terminal state)
agent chooses move to max its utility

33
Q

what is the algorithm used in adversial search and how does it work?

A

minimax
search tree until reaches terminal state
note utility of each term state (+1,1,0)
back up values of nodes to parents selecting max value on MAX’s move and min value on MIN’s move
continue backwards until get values for children of root node

34
Q

admissible vs consistent heuristic

A

admissible never over estimates cost of path from current to goal state (can underestimate but never overestimate)
consistent estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour

35
Q

every consistent h is ____ but

A

admissible but not all admissible are consistent

36
Q

optimality of A* using heuristics TS vs GS

A

TS: when uses AD h it will find least cost path to goal
GS: when uses consistent h avoids redundant explorations

37
Q

2 common heuristics

A

1) straight line distance which is both ad and consistent
2) Manhattan distance in tile game is # of moves needed to get from one pt to to the other without diagonal moves

38
Q

depth limited minimax

A

same but just search until depth limit is reached, applying heuristic evaluation funcition to state of each leaf

39
Q

alpha beta pruning

A

optimisation technique used in minimax algorithm for eliminating branches that don’t need to be explored

40
Q

what values ab pruning holds?

A

alpha (α): The best score that the maximizing player (Max) can guarantee so far. Initially, it’s set to a very low value (negative infinity).
Beta (β): The best score that the minimizing player (Min) can guarantee so far. Initially, it’s set to a very high value (positive infinity).

41
Q

how ab pruning works

A

start with initialised a=- inf and b= +inf
DFS of game tree
for each maximiser node update a with max among children
for each minimiser node update a with min among children
pruning during traversal if at any point a>=b prune remaining branches of tree as won’t be looked at

42
Q

why is ab pruning helpful?

A

increases efficiency of algorithm as prunes redundant branches and increases as depth increases

43
Q

stochastic search

A

search algorithm that uses randomness/probability for decision making and doesn’t care about going from A-B just wants to find the best state according to some criteria
inspired by genetics and natural selection

44
Q

features of stochastic search

A

state space
fitness function

45
Q

stochastic search pros and cons

A

searches large search space
not guaranteed to find global optimum

46
Q

genetic algorithm

A

stochastic search of biological evolution over a state space

47
Q

GA state space

A

space of genetic variation in population

48
Q

GA fitness function

A

evaluates how close solution is to optimal solution

49
Q

GA chromosome

A

representation of a state in GA, encoded as #s often (DNA sequences) relates characteristic of individuals

50
Q

GA crossover

A

genetic operation combining 2 parent chromosome to crehtaeone new one

51
Q

mutation

A

randomly modify child’s chromosomes

52
Q

population

A

set of chromosomes at a given iteration of the algorithm

53
Q

diversity

A

variety of solutions within the population
high diversity avoids premature convergence to local optima

54
Q

elitism

A

retaining fittest individuals for next generation

55
Q

7 steps for GA

A

create pop of soutions
evaluate how fit each solution is
randomly select 2 parents but in a way fitter states are more likely to be picked
combine parents into offspring
mutuatiion, randomly modifying offspring to maintain diversity
replace old population w new
repeat process until stop criteria is met

56
Q

epoch

A

the one entire passing of training data through the algorithm

57
Q

2 parent selection options

A

roulette wheel selection
tournament selection

58
Q

roulette wheel selection

A

stochastic selection
each individual is given slice of wheel proportional to its fitness and wheel is spun

59
Q

tournament selection

A

select a sub group of individuals for a tournament and fitness there is selected

60
Q

RW vs TS pros/cons

A

RW which lech prefers may lead to rapid convergence if one individual is significantly fitter than most but good for preserving diversity
TS promotes fittest while still trying to give others a chance
more greedy

61
Q

3 types of point crossovers

A

single point, everything before point is from one parent and second half from other
k point has multiple of those points
uniform is all individual gene picked from each parent

62
Q

when would each of these types of state space searches be viable?

A

state space is not too large
transition model (rules known) for (un/in/adv)
fitness function can be formed that ranks attest and sensible cross over point (GA)

COSC343 (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions