Eecs118 Definitions Midterm 1

Front 1

uniformed

Back 1

we have no problem specific reason to prefer one part of the search space to any other toward finding a part to the goal

Front 2

heuristic

Back 2

we have problem specific information to help focus the search

Front 3

breadth first search

Back 3

generates an explicit state search graph by applying all possible operators to the start node, then applying all possible operators to the direct successors of the start node, then to their successors

Front 4

successor function

Back 4

when applied to a node, it produces the entire set of nodes that can be produced by applying all of the operators that can be applied to that node

Front 5

uniform cost search

Back 5

nodes are expanded outward from the start node along contours of equal cost rather than along contours of equal depth. If the costs of all arcs in the graph are identical then uniform cost search is the same as breadth first search

Front 6

depth first search

Back 6

generates the successors of a node just one at a time by applying individual operators. A trace is left at each node to indicate that additional operators can eventually be applied there if needed. At each node, a decision must be made about which operator to apply first, which next, and so on

Front 7

depth bound

Back 7

a bound which is set which does not allow any successor to be created whose depth is greater than the depth bound

Front 8

chronological backtracking

Back 8

going back to a previous node and expanding a new path from it

Front 9

algorithm A*

Back 9

finds an optimal path to a goal(breadth first search)

Front 10

algorithm AO*

Back 10

for searching "and", "or" graphs

Front 11

assignment problems

Back 11

involves assigning values to variables subject to constraints

Front 12

constructive method

Back 12

a method where the solution is constructed step by step. Ex: place one queen first column, then place the second queen in a place that will satisfy in second column,and so on

Front 13

repair approach

Back 13

starts with a proposed solution, which most likely doesn't satisfy the constraints and repairs it until it does

Front 14

hill climbing

Back 14

a function over data structures where we seek to find a structure having a max or min value of that function. Traverse by moving from one point to that "adjacent" point having the highest elevation

Front 15

backed up value

Back 15

assume were max to choose among the tips nodes of a search tree, he would prefer the node having the largest evaluation. The backed up value of a max node parent of min tip nodes is equal to the maximum of the static evaluation of the tip nodes