Figure 2.38. Cut the root subtree a if eval(u)>eval(v)
Then we have the value of White vertex c at least the value of u, the value of Black vertex b at most the value of v. Therefore, if eval(u) > eval(v) we do not need to go down to evaluate vertex a anymore without affecting the evaluation of vertex c. Or in other words, we can cut off the root subtree a.
The same argument applies to the case where a is a Black vertex. In this case, if val(u)<eval(v), we also cut off the root subtree a.
To implement this technique, for the vertices on the path from the root to the current vertex, we use the parameter α to record the largest value among the values of the evaluated child vertices of a White vertex, the parameter β to record the smallest value among the values of the evaluated child vertices of a Black vertex.
Maybe you are interested!
-
Introduction to Artificial Intelligence - 21 -
The Level of Emotional Intelligence of Investigators in the Security Investigation Department of the Ministry of Public Security -
General Introduction About Ba Mien Restaurant In Hilton Hanoi Opera Hotel -
Introduction to Saigon Thuong Tin Commercial Joint Stock Bank (Sacombank) -
Introduction to Research Problem
Algorithm:
Procedure Alpha_Beta(u, v); begin. begin
α←-∞; β←-∞;
for each w is a child of u do if α <= MinVal(w, α, β) then
{α ← MinVal(w, α, β); v ← w} end;
-------------------------------------------------- -
Function MinVal(u, α, β); {function to determine values for Black vertices} begin
if u is a terminal vertex or u is a leaf of a restricted tree then MinVal(u, α, β) ← eval(u)
else for each vertex v is a child of u do Begin
β ← min{β, MaxVal(v, α, β) ; If α >= β then exit;
End;
/*cut off subtrees from remaining vertices v */ MinVal(u, α, β) ← β;
end;
-------------------------------------------------- -
Function MaxVal(u, α, β); { function to determine values for White vertices} begin
if u is a terminal or leaf of a restricted tree then MaxVal(u, α, β) ← eval(u)
Else
for each vertex v is a child of u do Begin
α ← max{α, MinVal(v, α, β)} ; If α >= β then exit;
End;
/*cut off subtrees from remaining vertices v */ MaxVal(u, α, β) ← α
end;
QUESTIONS AND EXERCISES CHAPTER 2
2.1. Present the concept of state space and problem representation in KGTT. Give illustrative examples.
2.2. Present blind search strategies: depth-first, breadth-first, and iterative depth search.
2.3. Present search strategies on graphs and/or.
2.4. Present heuristic search strategies: best-first search, hill climbing. Give illustrative examples.
2.5. Present A* search strategies. 2.6. Present branch-bound search strategies.
2.7. There is a boat on the left bank of a river. At any one time, the boat can carry a maximum of 2 people. Find a way to carry 2 robbers and 2 merchants from the left bank to the right bank of the river so that on each bank of the river, the number of merchants at any time is always at least the number of robbers (except in the case where there are no merchants on one bank of the river). Merchants and robbers can cross the two banks of the river many times.
Describe the state space of the problem and find a solution to the problem.
2.8. Given 2 bottles A and B with capacities of 4 liters and 7 liters respectively and no graduation lines. Initially, the 2 bottles have no water. You can pour water to fill the bottles, you can pour all the water from one bottle, you can pour water from one bottle to another. Construct the state space of the problem to pour exactly 1 liter of water and show 1 way to pour.
2.9. Given 2 bottles A, B with capacities of 3 liters and 8 liters respectively and no graduation lines. Initially, the 2 bottles have no water. You can pour water to fill the bottles, you can pour all the water from one bottle, you can pour water from one bottle to another.
Construct the state space of the problem to pour exactly 7 liters of water and show one way to pour.
2.10. Use the iterative deep search algorithm to find a path from A to G with depth d=3 in increasing order of the weights of the vertices in the state graph. Please simulate each step of the search process.
2.11. Given the state graph in the figure below. Use the deep iterative algorithm to find a path from vertex u o =A to vertex F with depth d =3 in increasing order of the weights of the vertices. Please simulate each step of the search process.
2.12. Given the state graph
1. Use hill climbing algorithm to find a path from vertex uo=A to vertex B. Weights attached at vertices determine the value of function h at that vertex. Requires simulating each step of the search process.
2. Use the deep iterative algorithm to find a path from A to B with depth d=1 in increasing order of vertex weights. Please simulate each step of the search process.
2.13. Given the state graph.
1. Use the best-first algorithm to find a path from vertex u o =A to vertex G. The weights attached to the vertices determine the value of the function h at that vertex. Please simulate each step of the search process.
2. Use the deep iterative algorithm to find a path from A to G with depth d=1 in increasing order of vertex weights. Please simulate each step of the search process.
2.14. Given a state graph. Use the A* algorithm to find the shortest path from vertex u 0 = A to vertex B. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
2.15. Given a state graph. Use the Branch-Bound algorithm to find the shortest path from vertex u 0 = A to vertex F. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
2.16 Given a state graph. Use the Branch-Bound algorithm to find the shortest path from vertex u 0 = A to vertex B. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
2.17. Given a state graph. Use the A * algorithm to find the shortest path from vertex u 0 = A to vertex B. The weights attached to the vertices determine the value of the function h at that vertex Requires simulating each step of the search process.
2.18. Given a state graph. Use the Branch-Bound algorithm to find the shortest path from vertex u 0 = A to vertex B. The weights attached to the vertices determine the value of the function h at that vertex Requires simulating each step of the search process.
2.19. Given a state graph. Use the A* algorithm to find the shortest path from vertex u o =A to vertex B. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
12
A
10
K 4
4
7
5
C
D
6
6
5
E
4
7
6
6
9
G
14
3
F
6
H
7
4
6
B
0
7
7
3
2.20. Given a state graph. Use the Branch-Bound algorithm to find the shortest path from vertex u o =A to vertex G. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
2.21 . Given a state graph. Use the A* algorithm to find the shortest path from vertex u o =A to vertex G. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
2.22. Given a state graph. Use the Branch-Bound algorithm to find the shortest path from vertex u o =A to vertex G. The weights attached to the vertices determine the value of the function h at that vertex. Simulate each step of the search process.
