Brute force procedure

BritishMuseum (){

1. Explore the entire search space;
2. return the optimal solution;

}

Branch&Bound(){

1. open <- {(start, NIL, Cost(start))}
2. closed <- {}
3. while TRUE
4.   do if Empty(open)
5.                   then return FAILURE;
6.   pick  the cheapest node n from  open
7.   if GoalTest(Head(n))
8.            then return ReconstructPath(n)
9.    else  children <- MoveGen(Head(n))
10.              for each m ∈ children{
11.                       do Cost(m) <- Cost(n) + K(m, n)
12.                        Add  (m, Head(n), Cost(m) ) to open }

}

GeneralisedBranch&Bound(){

1. start with all possible solutions
2. repeat
3.      Refine the least ( Estimated cost ) solution further
4. until the cheapest solution is fully refined
   
5. return s

}

Dijkstra’s Alg(){

1. Color all nodes white
2. cost(start) <- 0
3. parent(start) <- NIL
4. for all other nodes n
5.        do cost(n) <- ∞
6. repeat
7.     select lowest cost white node n
8.      color n black
9.      for all white neighbors m of n
10.             do if (const(n) + k(n, m)) < cost(m)
11.                   then cost(m) = const(n) + k(n, m)
12.                             parent(m) <- n
13. until all nodes are colored black

}

A*(){

// heuristic fun f(n) = g(n) + h(n)

//g(n) =known cost of path found from S to n

//h(n) = Estimated cost of path from n to G

1. open <- List(start)
2. f(start) <- h(start)
3. parent(start) <- NIL
4. closed <- {}
5. while open is not EMPTY
6.    do
7.        Remove node n from open such that f(n) has the lowest value
8.        Add n to closed
9.        if GoalTest(n) == TRUE
10.             then return Reconstructpath(n)
11.        neighbors <- MoveGen(n)
12.        for each m ∈ neighbors
13.               do switch
14.                    case m ∉ open and m ∉ closed : /* new node */
15.                            Add m to open
16.                            parent(m) <- n
17.                            g(m) <- g(n) + k(n, m)
18.                            f(m) <- g(m) + h(m)
20.                     case m ∈ open :
21.                            if (g(n) + k(n, m) ) < g(m)
22.                                   then  parent(m) <- n
23.                                              g(m) <- g(n) + k(n, m )
24.                                              f(m) <- g(m) + h(m)
26.                     case m ∈ closed :
27.                            if (g(n) + k(n, m) ) < g(m)
28.                                   then  parent(m) <- n
29.                                              g(m) <- g(n) + k(n, m )
30.                                              f(m) <- g(m) + h(m)
31.                                             propagateImprovement(m)
32. return FAILURE

}

PropagateImprovement(m){

1.  neighbours <- MoveGen(m)
2. for each  s ∈ neighbours
3.         do newGvalue <- g(m)  + k(m, s)
4.               if newGvalue < g(s)
5.                   then parent(s) <- m
6.                             g(s) <- newGvalue
7.                             if s ∈ closed
8.                                   then PropagateImprovement(s)

}

Admissibility of A*

Assumptions:

1. The branching factor is finite