BRITISH MUSEUM SEARCH

DEPTH-FIRST SEARCH

HILL CLIMBING

BREADTH-FIRST SEARCH

BEAM SEARCH

BEST-FIRST-SEARCH

BRITISH MUSEUM SEARCH

BRANCH-AND-BOUND SEARCH

With Underestimates
With Dynamic programming

A* Procedure

MINIMAX Procedure

ALPHA-BETA Procedure

DEPTH-FIRST SEARCH

To conduct a depth-first search:

Form a one-element stack consisting of the root node.
Until the stack is empty or the goal has been reached, determine if the first element in the stack is the goal node.

2a. If the first element is the goal node, do nothing.

2b. If the first element is not the goal node, pop the first element from the stack and push the first element's children, if any, to the stack.

If the goal node has been found, announce success; otherwise announce failure.

HILL CLIMBING

To hill climb:

Form a one-element consisting of the root node.
Until the queue is empty or the goal has been reached, determine if the first element in the queue is the goal node.

2a. If the first element is the goal node, do nothing.

2b. If the first element is not the goal node, pop the first element from the stack, sort the first element’s children, if any, by estimated remaining distance, and the first elements children, if any, to the stack.

If the goal node has been found, announce success; otherwise announce failure.

BREADTH-FIRST SEARCH

To conduct a breadth-first search:

Form a one-element queue consisting of the root node.
Until the queue is empty or the goal has been reached, determine if the first element in the queue is the goal node.

2a. If the first element is the goal node, do nothing.

2b. If the first element is not the goal node, remove the first element from the queue and add the first elements children, if any, to the front of the queue.

If the goal node has been found, announce success; otherwise announce failure.

BEAM SEARCH

Beam search is like breadth first search because beam search progresses level by level. Unlike breadth-first search, however, beam search only moves downward from the best w nodes at each level. The other nodes are ignored forever.

Consequently the number of nodes explored remains manageable, even if there is a great deal of branching and the search is deep. If beam search of width w is used in a tree with branching factor b, there will be only wb nodes under consideration at any depth, not the explosive number there would be if breadth-first search were used.

BEST FIRST SEARCH

To conduct a best-first search:

Form a one-element list consisting of the root node.
Until the list is empty or the goal has been reached, determine if the first element in the list is the goal node.

2a. If the first element is the goal node, do nothing.

2b. If the first element is not the goal node, remove the first element from the list, add the first element’s children, if any, to the front of the list, and sort the entire list by estimated remaining distance.

If the goal node has been found, announce success; otherwise announce failure.

BRITISH MUSEUM SEARCH

One procedure for finding the shortest path through a net is to find all possible paths and to select the best from them. This procedure is known as British Museum procedure. To find all possible paths, either a depth-first search or a breadth-first search will work, with one modification: search does not stop when the first path to the goal has been found.

BRANCH AND BOUND SEARCH

To conduct a branch and bound search:

Form a queue of partial paths. Let the initial queue consist of the zero-length, zero-step path from the root node to nowhere.
Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.

2a. If the first path reaches the goal node, do nothing.

2b. If the first path does not reach the goal node:

2b1. Remove the first path from the queue.

2b2. Form new paths from the removed path by extending one step.

2b3. Add the new paths to the queue.

2b4. Sort the queue by cost accumulated so far with least-cost paths in front.

If the goal node has been found, announce success; otherwise announce failure.

To conduct a branch and bound search with underestimates:

Form a queue of partial paths. Let the initial queue consist of the zero-length, zero-step path from the root node to nowhere.
Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.

2a. If the first path reaches the goal node, do nothing.

2b. If the first path does not reach the goal node:

2b1. Remove the first path from the queue.

2b2. Form new paths from the removed path by extending one step.

2b3. Add the new paths to the queue.

2b4. Sort the queue by the sum of cost accumulated so far and a lower-bound estimate of the cost remaining, with least cost paths in front.

If the goal node has been found, announce success; otherwise announce failure.

To conduct a branch and bound search with dynamic programming:

Form a queue of partial paths. Let the initial queue consist of the zero-length, zero-step path from the root node to nowhere.
Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.

2a. If the first path reaches the goal node, do nothing.

2b. If the first path does not reach the goal node:

2b1. Remove the first path from the queue.

2b2. Form new paths from the removed path by extending one step.

2b3. Add the new paths to the queue.

2b4. Sort the queue by cost accumulated so far, with least-cost paths in front.

2b5. If two or more paths reach a common node, delete all those paths except the one that reaches the common node with the minimum cost.

If the goal node has been found, announce success; otherwise announce failure.

A* Procedure

To do A* search with lower bound estimates:

Form a queue of partial paths. Let the initial queue consist of the zero-length, zero-step path from the root node to nowhere.
Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.

2a. If the first path reaches the goal node, do nothing.

2b. If the first path does not reach the goal node:

2b1. Remove the first path from the queue.

2b2. Form new paths from the removed path by extending one step.

2b3. Add the new paths to the queue.

2b4. Sort the queue by the sum of cost accumulated so far and a lower-bound estimate of the cost remaining, with least cost paths in front.

2b5. If two or more paths reach a common node, delete all those paths except the one that reaches the common node with the minimum cost.

If the goal node has been found, announce success; otherwise announce failure.

MINIMAX Procedure

To MiniMax:

Determine if the limit of search has been reached, or if the level is a minimizing level, or if the level is maximizing level:

1a. If the limit of search has been reached, compute the static value of the current position relative to the appropriate layer. Report the result.

1b. If the level is a minimizing level, use MINIMAX on the children of the current position. Report the minimum of the results.

1c. Otherwise, the level is a maximizing level. Use MINIMAX on the children of the current position. Report the maximum of the results.

ALPHA-BETA Procedure

To MINIMAX with ALPHA-BETA:

Determine if the level is the top level, or if the limit of search has been reached, or if the level is a minimizing level, or if the level is a maximizing level:

1a. If the level is the top level, let alpha be –a, and let beta be +a.

1b. If the limit of the search has been reached, compute the static value of the current position relative to the appropriate layer. Report the result.

1c. If the level is a minimizing level:

1c1. Until all children are estimated with MINIMAX or alpha is bigger than beta:

1c1.1 Set beta to the smaller of the given beta values and the smallest value so far reported by MINIMAX working on the children.

1c1.2 Use MINIMAX on the next child of the current position, handing this new application of MINIMAX the current alpha and beta.

1c2. Report beta.

1d. If the level is a maximizing level.

1d1. Until all children are examined with MINIMAX or alpha is bigger than beta:

1d1.1 Set alpha to the larger of the given alpha values and the biggest value so far reported by MINIMAX working on the children.

1d1.2 Use MINIMAX on the next child of the current position, handing this new application of MINIMAX the current alpha and beta.

1d2. Report alpha.

===========================================================

code for breadth first search

(defun breadth (map start final)
     (cond (not (equal (car list1) final))
             (setq list2 (cons (car list1) list2))
             (setq list1 (cdr list1))
             (searchgraph (car list2) graph)
             (findchild z)
             (breadth graph start final))
           ((equal (car list1) final)
              (setq list1 (cdr list1))
              (setq list2 (cons final list2)))))

(defun findchild (x)
     (setq x (cdr x))
     (cond
          ((not (equal x nil))(setq k (car (car x)))
           (cond ((not (member k list2))(setq list1 (cons k list1))))
           (findchild x))))

(defun searchgraph (x graph1)
    (cond
        ((not (equal x (car (car graph1))))
          (setq graph1 (cdr graph1))
          (searchgraph x graph1)))
    (cond ((equal x (car (car graph1)))(setq z (car graph1)))))

(defun initialize (start)
      (setq list1 start)
      (setq list2 '( ))
=======================================================