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.
- If the goal node has been found, announce success; otherwise announce failure.

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.

- 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.
- If the goal node has been found, announce success; otherwise announce failure.

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.

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.
- If the goal node has been found, announce success; otherwise announce failure.

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.

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.

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.
- If the goal node has been found, announce success; otherwise announce failure.

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.*

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.
- If the goal node has been found, announce success; otherwise announce failure.

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.

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.
- If the goal node has been found, announce success; otherwise announce failure.

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.

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.
- If the goal node has been found, announce success; otherwise announce failure.

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.

To do A* search with lower bound estimates:

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

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.

- 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.

- 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 '( )) =======================================================