Essay, 4 pages (850 words)

Ch 4 – artificial intelligence illuminated

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

state of search spacerepresents where you have reached in problem solving

initial statethe starting state when solving a problem

goal statethe final state that satisfies a goal of a certain problem that was trying to solve

search spaceproblem space

search methodsmethods of searching nodes

data-driven searchstarts from initial state and uses actions that are allowed to move forward until a goal is reached (forward chaining)

goal-driven searchsearch starts at goal and works back to a start state by seeing what moves could have led to goal state. (backward chaining)

generate and testsearch that generates each node in search space and tests it to see if it is a goal node. (simple brute-force method)

exhaustive searchbrute force search where every node in tree is examined

blind searchanother 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)

depth-first searchfollows 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.

breadth-first searchexamines 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.

plyall nodes on a level

useful search method properties to considercomplexity, 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

big-o notationdescribes 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 searcheasy 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 implementationstack. push successors to stack. pop, push successors, pop, etc. if no successors then pop next one repeat until goal found

breadth first search implementationqueue. 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-firstdepth-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

heuristic (redeux)humans use them to solve problems. Can reduce a hard problem into a relatively simple one.

heuristic evaluation functionfunction 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 methodsprovides 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

monotonic heuristica heuristic that is monotone

admissible heuristica heuristic that never overestimates the true distance of a node from the goal. a monotonic heuristic is heuristic

hill climbinginformed 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 climbingsame 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

best-first searchheuristic similar to hill climbing. entire queue is sorted after new paths have been added to it rather than sorting new paths before adding

beam searchform of breadth-first that uses heuristic.

optimal pathoptimal path is one that has lowest cost or involves traveling the shortest distance from start to goal node

British Museum procedureexamine every single path through search tree and returning via the best path that was found

A* algorithmsimilar to best-first but uses more complex heuristic


Thank's for Your Vote!
Ch 4 – artificial intelligence illuminated. Page 1
Ch 4 – artificial intelligence illuminated. Page 2
Ch 4 – artificial intelligence illuminated. Page 3
Ch 4 – artificial intelligence illuminated. Page 4
Ch 4 – artificial intelligence illuminated. Page 5
Ch 4 – artificial intelligence illuminated. Page 6

This work, titled "Ch 4 – artificial intelligence illuminated" was written and willingly shared by a fellow student. This sample can be utilized as a research and reference resource to aid in the writing of your own work. Any use of the work that does not include an appropriate citation is banned.

If you are the owner of this work and don’t want it to be published on AssignBuster, request its removal.

Request Removal
Cite this Essay


AssignBuster. (2022) 'Ch 4 – artificial intelligence illuminated'. 22 August.


AssignBuster. (2022, August 22). Ch 4 – artificial intelligence illuminated. Retrieved from https://assignbuster.com/ch-4-artificial-intelligence-illuminated/


AssignBuster. 2022. "Ch 4 – artificial intelligence illuminated." August 22, 2022. https://assignbuster.com/ch-4-artificial-intelligence-illuminated/.

1. AssignBuster. "Ch 4 – artificial intelligence illuminated." August 22, 2022. https://assignbuster.com/ch-4-artificial-intelligence-illuminated/.


AssignBuster. "Ch 4 – artificial intelligence illuminated." August 22, 2022. https://assignbuster.com/ch-4-artificial-intelligence-illuminated/.

Work Cited

"Ch 4 – artificial intelligence illuminated." AssignBuster, 22 Aug. 2022, assignbuster.com/ch-4-artificial-intelligence-illuminated/.

Get in Touch

Please, let us know if you have any ideas on improving Ch 4 – artificial intelligence illuminated, or our service. We will be happy to hear what you think: [email protected]