Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Informed search

a. Best-First branch-and-bound
b. Hill Climbing / Gradient Descent
c. A* Search
d. A* Searching And-Or graphs

**Informed search**

*a. **Best-First branch-and-bound*

*b. **Hill Climbing / Gradient Descent*

*c. **A* Search*

*d. **A* Searching And-Or graphs*

Informed
search uses some kind of evaluation function to tell us how far each expanded
state is from a goal state, and/or some kind of heuristic function to help us
decide which state is likely to be the best one to expand next.

The hard
part is to come up with good evaluation and/or heuristic functions. Often there
is a natural evaluation function, such as distance in miles or number objects
in the wrong position.

Sometimes
we can learn heuristic functions by analyzing what has worked well in similar
previous searches.

The
simplest idea, known as greedy best first search, is to expand the node that is
already closest to the goal, as that is most likely to lead quickly to a
solution. This is like DFS in that it attempts to follow a single route to the
goal, only attempting to try a different route when it reaches a dead end. As
with DFS, it is not complete, not optimal, and has time and complexity of O(b^{m}).
However, with good heuristics, the time complexity can be reduced substantially.

**Branch and Bound: **An
enhancement of backtracking.** **Applicable
to optimization problems.

For each
node (partial solution) of a state-space tree, computes a bound on the value of
the objective function for all descendants of the node (extensions of the
partial solution).

Uses the
bound for:

Ruling
out certain nodes as “nonpromising” to prune the tree – if a node’s bound is
not better than the best solution seen so far.

Guiding
the search through state-space.

The
search path at the current node in a state-space tree can be terminated for any
one of the following three reasons:

The value
of the node’s bound is not better than the value of the best solution seen so
far.

The node
represents no feasible solutions because the constraints of the problem are
already violated.

The
subset of feasible solutions represented by the node consists of a single point
and hence we compare the value of the objective function for this feasible
solution with that of the best solution seen so far and update the latter with
the former if the new solution is better.

**Best-First branch-and-bound:**

A
variation of backtracking.

Among all
the nonterminated leaves, called as the live nodes, in the current tree,
generate all the children of the most promising node, instead of generation a
single child of the last promising node as it is done in backtracking.

Consider
the node with the best bound as the most promising node.

**A* Search: **Suppose that, for each node n in
a search tree, an evaluation function f(n)**
**is defined as the sum of the cost g(n) to reach that node from the start
state, plus an estimated cost h(n) to get from that state to the goal state.
That f(n) is then the estimated cost of the cheapest solution through n.

A*
search, which is the most popular form of best-first search, repeatedly picks
the node with the lowest f(n) to expand next. It turns out that if the
heuristic function h(n) satisfies certain conditions, then this strategy is
both complete and optimal.

In
particular, if h(n) is an admissible heuristic, i.e. is always optimistic and
never overestimates the cost to reach the goal, then A* is optimal.

The
classic example is finding the route by road between two cities given the
straight line distances from each road intersection to the goal city. In this
case, the nodes are the intersections, and we can simply use the straight line
distances as h(n).

**Hill Climbing / Gradient Descent: **The basic
idea of hill climbing is simple: at each**
**current state we select a transition, evaluate the resulting state, and if
the resulting state is an improvement we move there, otherwise we try a new
transition from where we are.

We repeat
this until we reach a goal state, or have no more transitions to try. The
transitions explored can be selected at random, or according to some problem
specific heuristics.

In some
cases, it is possible to define evaluation functions such that we can compute
the gradients with respect to the possible transitions, and thus compute which
transition direction to take to produce the best improvement in the evaluation
function.

Following
the evaluation gradients in this way is known as gradient descent.

In neural
networks, for example, we can define the total error of the output activations
as a function of the connection weights, and compute the gradients of how the
error changes as we change the weights. By changing the weights in small steps
against

those
gradients, we systematically minimize the network’s output errors.

**Searching And-Or graphs**

The DFS
and BFS strategies for OR trees and graphs can be adapted for And-Or trees The
main difference lies in the way termination conditions are determined, since
all goals following an And node must be realized, whereas a single goal node
following

an Or
node will do

A more
general optimal strategy is AO* (O for ordered) algorithm

As in the
case of the A* algorithm, we use the open list to hold nodes that have been
generated but not expanded and the closed list to hold nodes that have been
expanded

The
algorithm is a variation of the original given by Nilsson

It
requires that nodes traversed in the tree be labeled as solved or unsolved in
the solution process to account for And node solutions which require solutions
to all successors nodes.

A
solution is found when the start node is labeled as solved

The AO* algorithm

Step 1:
Place the start node s on open

Step 2:
Using the search tree constructed thus far, compute the most promising solution
tree T_{0}

Step
3:Select a node n that is both on open and a part of T_{0.} Remove n
from open and place it on closed

Step 4:
If n ia terminal goal node, label n as solved. If the solution of n results

in any of
n’s ancestors being solved, label all the ancestors as solved. If the start
node s is solved, exit with success where T_{0} is the solution tree.
Remove from open all nodes with a solved ancestor

Step 5:
If n is not a solvable node, label n as unsolvable. If the start node is
labeled as unsolvable, exit with failure. If any of n’s ancestors become
unsolvable because n is, label them unsolvable as well. Remove from open all
nodes with unsolvable ancestors

Otherwise,
expand node n generating all of its successors. For each such successor node
that contains more than one subproblem, generate their successors to give
individual subproblems. Attach to each newly generated node a back pointer to
its predecessor. Compute the cost estimate h* for each newly generated node and
place all such nodes thst do not yet have descendents on open. Next recomputed
the values oh h* at n and each ancestors of n

Step 7:
Return to step 2

It can be
shown that AO* will always find a minimum-cost solution tree if one exists,
provided only that h*(n) ≤ h(n), and all arc costs are positive. Like A*, the
efficiency depends on how closely h* approximates h

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.