CHAPTER 2 - Problem Solving by Search

Goal based

An important aspect of intelligence is ____ _____ problem solving. Several problems can be formulated as finding a sequence of actions that leads to a desirable goal. Each action changes the state and the aim is to find the sequence of actions and states that lead from the initial state to a final (goal) state

States, operators, start, initial, test

Searching through a state space involves the following:

- A set of ______

- _________

- A _____ or _______ state

- A ____ to check for goal state

Operators or successor function

describes a well-defined problem. for any state x returns s(x), the set of states reachable from x with one action

Path

describes a well-defined problem. sequence through state space

State space

describes a well-defined problem. all states reachable from the initial state by any sequence of actions

Path cost

describes a well-defined problem. function that assigns a cost to a path. Cost of a path is the sum of costs of individual actions along the path

Goal test

describes a well-defined problem. test to determine if a goal state

Search

is the systematic examination of states to find a path from the start state to the goal state.

Uninformed, heuristic, adversarial

Search techniques fall into what three groups

Tree-Based Search

The set of all paths within a state-space can be viewed as a graph of nodes, which are connected by links. If all possible paths are traced out through the graph, and the paths are terminated before they return to nodes already visited (cycles) on that path, a search tree is obtained.

Root node

Component of tree based search. represents the node the search starts from

Leaf node

Component of tree based search. a terminal node in the search tree having no children

Ancestor/descendant

Component of tree based search. node A is an ancestor of node B if either A is B's parent or A is an ancestor of the ancestor of the parent of B. If A is an ancestor of B, B is said to be a descendant of A

Branching factor

Component of tree based search. the maximum number of children of a non-leaf node in the search tree

Path

Component of tree based search. represents complete path if it begins with the start node and ends with a goal node. Otherwise, it is a partial path

State, pointer, depth, operator, cost

A node in the tree may be viewed as a data structure containing the following elements:

• A _____ description

• A _______ to the parent of the node

• _____ of the node

• The ________ that generated this node

• ____ of the path (sum of operator costs) obtained from the initial (start) state

Memory

It is advisable not to produce complete physical trees in ______ but rather explore as little of the virtual tree looking for root-goal paths.

State space

is explored by generating successors of the already explored states. Every state is evaluated in order to see whether this is the goal state.

Store

A disadvantage of the tree search is that it can end up repeatedly visiting the same node. A solution to this is to _____ all the visited nodes but this will require a lot of memory resources.

Open, fringe

The nodes that the algorithm has generated so far during the search process are kept in a data structure called ____ or ______. Initially only the start node (the initial state) is in OPEN. The search starts with the root node. The algorithm picks a node from OPEN for expanding and generates all the children of the node. Expanding a node from OPEN results in a closed node.

Closed

Some search algorithms keep track of the closed nodes also in a data structure called ______

Graph Search

If the search space is not a tree, but a graph, the search tree may contain different nodes corresponding to the same state. The state space can be considered a graph G(V, E), where V is the set of nodes/vertices and E is a set of edges, which are directed from a node to another node.

Vertex

In graph search, Each ______ corresponds to an instance of one of the operators. When the operator is applied to the state associated with the arc's source node, then the resulting state is the state associated with the vertex's destination node. Each vertex has a positive cost associated with it corresponding to the cost of the operator.

Successor

Each node has a set of _________ nodes corresponding to all of the operators that may be applied at the source node's state. Expanding a node means generating all the successor nodes of it and add them and their associated vertices to the state-space graph

Initial state

component of graph search. One or more nodes are designated as start nodes.

State space

component of graph search. Initially, a starting node S is considered and V equals {S}. Then S is expanded and its generated successors (nodes and vertices) are added to V and E respectively. This process continues until a goal node is found

Path

component of graph search. each node represents a partial solution path from the start node to the given node. In general, from this node there are many possible paths (and therefore solutions) that have this partial path as a prefix

Path cost

component of graph search. the sum of the vertices costs on the solution path

Goal test

component of graph search. test applied to a state to determine if its associated node is a goal node and satisfies all goal conditions

Solution

component of graph search. a sequence of operators that is associated with a path in a state space from a start node to a goal node

uninformed/blind, informed/heuristic

2 major categories of search methods

Breadth first, width first, iterative deepening depth first, bidirectional. Branch and bound

5 examples of well known algorithms under uninformed search (BDIBB)

Hill climbing, beam, greedy, best first

4 examples of well known algorithms under informed search (HBGB)

Root

Similar to a queue, fifo. In the breadth first search (BFS) algorithm, each state at a given layer is expanded before moving to the next layer of states. This way always the node nearest the ____ can be cached. This is important if the tree is unbalanced, but is wasteful if all the goal nodes are at similar levels

Memory exhaustion

______ __________ stops BFS long before processing time becomes an issue.

RAM

Uninformed BFS is completely impractical for deep problems due to ___ limits

Depth First Search

The queue here may be replaced with a stack, lifo. Nodes are popped from the front of the queue and new nodes are pushed to the front. The strategy always chooses to expand one of the nodes that is at the deepest level on the search tree. It only expands nodes on the queue that are at the shallower level if the search has reached a dead-end at the deepest level. A path is expanded as much as possible until it reaches a goal node or can be expanded no more prior to expanding other paths.

Depth First Search

in infinite-depth spaces or cyclic graphs, Can plunge down an infinite path and never reach a goal on a neighboring branch.

Depth limits, cycle checking

DFS Requires _____ ______ or _____ ________ (an Explored Set) to prevent infinite loops.