Assume also that the ESTIMATED
distances to the goal are given by the following table:
Node: | S | A | C | D | F | G | H | ||||||||
Estimated Distance to G: | 10 | 5 | 4 | 3 | 4 | 0 | 2 |
For EACH of the following search methods list the nodes in the order in which they are EXPANDED by the search method while looking for a solution. When everything else is equal, order the nodes in alphabetical order. As an illustration, the solution for Depth 1st search is provided below.
List: [S, A, C, D, G]
S / \ A F / \ C F / \ D G * goal
List: [S, A, F, C, F, A, G]
S / \ A F / \ / | \ C F A G H / \ / \ * D G G H
List: [S, A, C, F, D, H, G]
S / \ 2 A F 7 / \ / | \ 6 C F A G H / \ 10 15 12 9 9 D G x x x | 11 G * 12 x
List: [S, F, G]
S 10 / \ 5 A F 4 / | \ A G H 5 0 2 *
List: [S, A, C, F, G]
S / \ 7 A F 11 / \ / | \ 10 C F A G H / \ 14 20 12 11 D G x x x 12 11 *
List: [S, F, G]
S 10 / \ 5 A F 4 / | \ A G H 5 0 2 *
Same net as in Example 1:
Node: | S | A | C | D | F | G | H | ||||||||
Estimated Distance to G: | 10 | 5 | 4 | 3 | 4 | 0 | 2 |
S,F,G
Length of S,F,G = 12. However, there exists path S,A,C,G with length only 11.
BACKWARD CHAINING: hobbes is a tiger ?x is a tiger | | R4 | hobbes has black stripes ?x has black stripes | | succeeds due to A1 | hobbes is a carnivore ?x is a carnivore | | R3 | hobbes eats meat ?x eats meat | | succeeds due to A2 | hobbes is a mammal ?x is a mammal | | R1 | hobbes gives milk ?x gives milk succeeds due to A4 hence the working memory is updated with: A6: hobbes is a mammal A7: hobbes is a carnivore A8: hobbes is a tiger
FORWARD CHAINING: R1: hobbes gives milk ?x gives milk succeeds due to A4 WM := WM + {A6: hobbes is a mammal} ?x is a mammal R2: tweety has feathers ?x has feathers | | succeeds due to A3 | tweety flies ?x flies | | succeeds due to A5 | tweety lays eggs ?x lays eggs fails hence rule R2 is not triggered. R3: hobbes eats meat ?x eats meat | | succeeds due to A2 | hobbes is a mammal ?x is a mammal succeeds due to A6 WM:= WM + {A7: hobbes is a carnivore} ?x is a carnivore R4: hobbes has black stripes ?x has black stripes | | succeeds due to A1 | hobbes is a carnivore ?x is a carnivore succeeds due to A7 WM:= WM + {A8: hobbes is a tiger} ?x is a tiger Applying again R1, R2, R3, R4 does not yield any new assertions and so the forward chaining process stops.
Note then that the set of variables and their domains are:
Variable Domain ------------------------------------- Bill Mo9, Mo10, Wed9, Wed10 Ann Mo9, Mo10, Wed9, Wed10 Paul Mo9, Mo10, Wed9, Wed10
Draw the complete constraint net, including full constraint matrices.
AFTER all the constraints have been entered into the binary constraint matrices, and BEFORE the search for a solution begins, we check all the rows and columns of the binary constraint matrices for time that has all zeros, and for which the variable domain for that person still contains this time (because it was not removed by entering any of the given constraints). Such times are removed from the domain of those people, and then all binary constraint matrices for that person are updated to reflect the smaller domain. After the arc consistency checking is done, only one value remains true in each binary constraint matrix.
Although all there is only value left for each binary constraint matrix, a general problem solving strategy would order the variables by how constrained they were. The depth first search would begin with an assignment of the most constrained variable.
Assignments would be made for each successive node, where the selection of the next successive node would be the most constrained of the remaining variables. This would eventually lead to the discovery that the solution to the CSP is We10.