Supp-
Consider a graph like this:
During the search
|
OPEN |
CLOSED |
REMARK |
|---|---|---|
|
[A(0)] |
[] |
|
|
[B(3,A), |
[A(0)] |
B can reach C with cost 9. When compare C in open, no change is needed |
|
[C(7,A), |
[A(0),B(3)] |
D is chosen |
|
[C(7,A), |
[A(0),B(3),D(5)] |
C is chosen, since D is already in CLOSED, no need to handle D, for E, since new cost is 8, replace E |
|
[E(8,AC)] |
[A(0),B(3),D(5),C(7)] |
|
|
|
|
max f(n) |
|
|
|
|
|---|---|---|---|---|---|---|
|
|
d{ |
(max underestimate) |
|
|
|
|
|
f*(n) --> |
|
|
|
|
|
|
|
|
e{ |
min f(n) |
|
max g(n) |
|
|
|
|
|
(max overestimate) |
|
(max underestimate) |
}d |
|
|
|
|
|
|
|
|
<-- g*(n) |
|
|
|
|
|
min g(n) |
}e |
|
|
|
|
|
|
(max overestimate) |
|
|
If we only know f*(n) and g*(n), then f(n) will lie between min f(n) and max f(n) as shown above. The same applies for g(n). In order to have f(n)>g(n), we must be certain that min f(n) > max g(n). This is guaranteed if f*(n)-g*(n)>d+e (as illustrated in above figure).
Alpha-Beta Pruning
Consider figure 4.15 and the alpha-beta pruing algorithm in the lecture notes. Note that the parameters alpha and beta are passed to a lower level recursion, and its value is not returned back.