consists of a goal and set of actions that can be taken to lead to the goal.
state of search space
represents where you have reached in problem solving
the starting state when solving a problem
the final state that satisfies a goal of a certain problem that was trying to solve
methods of searching nodes
starts from initial state and uses actions that are allowed to move forward until a goal is reached (forward chaining)
search starts at goal and works back to a start state by seeing what moves could have led to goal state. (backward chaining)
generate and test
search that generates each node in search space and tests it to see if it is a goal node. (simple brute-force method)
brute force search where every node in tree is examined
another term for generate and test search
generator (generate and test)
the “spawner” of nodes. should satisfy three proporties. 1. must be complete (every possible solution). 2. must be nonredundant 3. must be well informed (should only propose suitable solutions)
follows each path to greatest debth before moving to next path. See any algorithm book on implementation. secret is you add nodes to a stack (last in is first out) start from left and work right, goes to leaf, then backtracks a level.
examines all nodes on same level befoe moving to next level. secret is you add nodes to the front of the queue and remove from the back of queue.
all nodes on a level
useful search method properties to consider
complexity, completeness, optimality, admissability, irrevocability
complexity (search methods)
how efficient the method is over time and space. time complexity – how long it takes. space complexity – amount of memory search method takes
describes complexity of a method o(x) etc.
completeness (search methods)
search method is described as complete if guaranteed to find a goal state if one exists. Breadth-first is complete, depth-first search is not complete
optimal (search methods)
search method is optimal if it is guaranteed to find the best solution that exists. will take the least number of possible steps to reach goal.
tentative (search methods)
methods that use backtracking.
irrevocable (search methods)
methods that do not use backtracking (use only one path). often fooled by local optima
humans use depth-first search
easy to implement and relates closely to natural way humans search for things
traversing a maze (depth-first)
start with hand on left side of maze or right and follow maze around until reach end. this corresponds exactly to depth-first search
depth first search implementation
stack. push successors to stack. pop, push successors, pop, etc. if no successors then pop next one repeat until goal found
breadth first search implementation
queue. add successors to queue. remove first, add successors, because queue adding successors to back of list rather than front as in stack
optimality of breadth-first vs. depth-first
depth-first search is neither optimal nor complete. breadth-first search is both. depth first might never find solution, breadth-first will always find best solution
depth-first iterative deepending (DFID)
depth-first search combined with breadth-first search. repeatedly carry out depth-first searches limited to level (1, 2, …, n). wasteful for small tree, works well for large tree
humans use them to solve problems. Can reduce a hard problem into a relatively simple one.
heuristic evaluation function
function when applied to a node gives a value that represents a good estimate of the node from the goal. two nodes, m and n, if f(m) < f(n) then it should be that m is more likely to be on an optimal path than n
heuristic search methods, or heuristically informed search methods
provides an estimate of the distance from any given node to a goal node.
heuristic is informed if…
it uses additional information about nodes that have not yet been explored to decided which nodes to examine next
heuristic is uninformed if…
it is not informed or blind
heuristic is more informed than another heuristic if…
if h(node) <= j(node) for all nodes in the search space. the more informed a search method is the more efficiently it will search
monotone (search method)
if it always reaches a given node by shortest path
a heuristic that is monotone
a heuristic that never overestimates the true distance of a node from the goal. a monotonic heuristic is heuristic
informed search. check height is higher than current position, move to that location and restart the algorithm. if all directions lead lower than current position, stop and assume summit. – uses stack
steepest ascent hill climbing
same as hill climbing, but rather than choosing first higher value, choose the highest out of all possible values (directions) – uses stack, you sort successors before placing on stack
local maxima problem (hill climbing)
hill climbing can be fooled by foothills, plateus, and ridges
heuristic similar to hill climbing. entire queue is sorted after new paths have been added to it rather than sorting new paths before adding
form of breadth-first that uses heuristic.
optimal path is one that has lowest cost or involves traveling the shortest distance from start to goal node
British Museum procedure
examine every single path through search tree and returning via the best path that was found
similar to best-first but uses more complex heuristic