Scribd
Upload
2 views

Search Algorithms

The document outlines various search algorithms, focusing on best-first search and its implementation, which utilizes a priority queue and an evaluation function to explore nodes. It also discusses data structures necessary for search algorithms, including different types of queues like FIFO, LIFO, and priority queues. Additionally, it covers breadth-first search, uniform-cost search, iterative deepening, depth-limited search, and bidirectional best-first search, detailing their functions and operational mechanisms.

Uploaded by

annet
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views

Search Algorithms

The document outlines various search algorithms, focusing on best-first search and its implementation, which utilizes a priority queue and an evaluation function to explore nodes. It also discusses data structures necessary for search algorithms, including different types of queues like FIFO, LIFO, and priority queues. Additionally, it covers breadth-first search, uniform-cost search, iterative deepening, depth-limited search, and bidirectional best-first search, detailing their functions and operational mechanisms.

Uploaded by

annet
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Search Algorithms

Best first search algorithms:

function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure

node←NODE(STATE=problem.INITIAL)

frontier←a priority queue ordered by f , with node as an element

reached←a lookup table, with one entry with key problem. INITIAL and value node

while not IS-EMPTY(frontier) do

node←POP(frontier)

if problem.IS-GOAL(node.STATE) then return node

for each child in EXPAND(problem, node) do

s←child.STATE

if s is not in reached or child.PATH-COST < reached[s].PATH-COST then

reached[s]←child

add child to frontier

return failure

function EXPAND(problem, node) yields nodes

s←node.STATE

for each action in problem.ACTIONS(s) do

s’←problem.RESULT(s, action)

cost←node.PATH-COST + problem.ACTION-COST(s, action,s’)

yield NODE(STATE=s’, PARENT=node, ACTION=action, PATH-COST=cost)

Figure The best-first search algorithm, and the function for expanding a node.

A very general approach is called best-first search, in which we choose a node, n, with minimum
value of some evaluation function, f(n). On each iteration we choose Evaluation function a node on
the frontier with minimum f(n) value, return it if its state is a goal state, and otherwise apply
EXPAND to generate child nodes. Each child node is added to the frontier if it has not been reached
before, or is re-added if it is now being reached with a path that has a lower path cost than any
previous path. The algorithm returns either an indication of failure, or a node that represents a path
to a goal. By employing different f(n) functions, we get different specific algorithms,
Search data structures

Search algorithms require a data structure to keep track of the search tree. A node in the tree

is represented by a data structure with four components:

• node.STATE: the state to which the node corresponds;

• node.PARENT: the node in the tree that generated this node;

• node.ACTION: the action that was applied to the parent’s state to generate this node;

• node.PATH-COST: the total cost of the path from the initial state to this node. In mathematical
formulas, we use g(node) as a synonym for PATH-COST.

We need a data structure to store the frontier. The appropriate choice is a queue of some

kind, because the operations on a frontier are:

• IS-EMPTY(frontier) returns true only if there are no nodes in the frontier.

• POP(frontier) removes the top node from the frontier and returns it.

• TOP(frontier) returns (but does not remove) the top node of the frontier.

• ADD(node, frontier) inserts node into its proper place in the queue.

Three kinds of queues are used in search algorithms:

Priority queue • A priority queue first pops the node with the minimum cost according to some
evaluation function, f . It is used in best-first search.

FIFO queue • A FIFO queue or first-in-first-out queue first pops the node that was added to the
queue first; we shall see it is used in breadth-first search.

LIFO queue • A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most

Stack recently added node; we shall see it is used in depth-first search.

Breadth-first search and uniform-cost search algorithms.

function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure

node←NODE(problem.INITIAL)

if problem.IS-GOAL(node.STATE) then return node

frontier←a FIFO queue, with node as an element

reached← {problem.INITIAL}

while not IS-EMPTY(frontier) do


node←POP(frontier)

for each child in EXPAND(problem, node) do

s←child.STATE

if problem.IS-GOAL(s) then return child

if s is not in reached then

add s to reached

add child to frontier

return failure

function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure

return BEST-FIRST-SEARCH(problem, PATH-COST)

Iterative deepening and depth-limited tree-like search.

function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure


for depth = 0 to ∞ do
result←DEPTH-LIMITED-SEARCH(problem, depth)
if result ≠ cutoff then return result
function DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff
frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element
result←failure
while not IS-EMPTY(frontier) do
node←POP(frontier)
if problem.IS-GOAL(node.STATE) then return node
if DEPTH(node) > l then
result←cutoff
else if not IS-CYCLE(node) do
for each child in EXPAND(problem, node) do
add child to frontier
return result

Bidirectional best-first search

function BIBF-SEARCH(problemF, fF, problemB, fB) returns a solution node, or failure


nodeF ←NODE(problemF.INITIAL) // Node for a start state
nodeB←NODE(problemB.INITIAL) // Node for a goal state
frontierF ←a priority queue ordered by fF, with nodeF as an element
frontierB←a priority queue ordered by fB, with nodeB as an element
reachedF ←a lookup table, with one key nodeF.STATE and value nodeF
reachedB←a lookup table, with one key nodeB.STATE and value nodeB
solution←failure
while not TERMINATED(solution, frontierF, frontierB) do
if fF(TOP(frontierF)) < fB(TOP(frontierB)) then
solution←PROCEED(F, problemF, frontierF, reachedF, reachedB, solution)
else solution←PROCEED(B, problemB, frontierB, reachedB, reachedF, solution)
return solution
function PROCEED(dir, problem, frontier, reached, reached2, solution) returns a solution
// Expand node on frontier; check against the other frontier in reached2.
// The variable “dir” is the direction: either F for forward or B for backward.
node←POP(frontier)
for each child in EXPAND(problem, node) do
s←child.STATE
if s not in reached or PATH-COST(child) < PATH-COST(reached[s]) then
reached[s]←child
add child to frontier
if s is in reached2 then
solution2←JOIN-NODES(dir, child, reached2[s]))
if PATH-COST(solution2) < PATH-COST(solution) then
solution←solution2
return solution

You might also like