Finding Optimal Paths

Given a  search space, apply search and find the solution quickly and make sure that solution is optimal. i.e, both look up cost and execution cost must be minimum.

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