Ch 4 – Artificial Intelligence Illuminated

consists of a goal and set of actions that can be taken to lead to the goal.

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

problem space

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)

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

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

complexity, completeness, optimality, admissability, irrevocability

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.

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

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.

methods that use backtracking.

methods that do not use backtracking (use only one path). often fooled by local optima

easy to implement and relates closely to natural way humans search for things

start with hand on left side of maze or right and follow maze around until reach end. this corresponds exactly to depth-first search

stack. push successors to stack.

pop, push successors, pop, etc. if no successors then pop next one repeat until goal found

queue. add successors to queue. remove first, add successors, because queue adding successors to back of list rather than front as in stack

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 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.

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

provides an estimate of the distance from any given node to a goal node.

it uses additional information about nodes that have not yet been explored to decided which nodes to examine next

it is not informed or blind

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

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

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

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

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