0
$\begingroup$

Pruning

I am studying some old past test questions. Is this search tree correctly pruned?

$\endgroup$
3
  • 1
    $\begingroup$ Can you explain why you didn't prune 8 and 4 in the middle? $\endgroup$
    – Pål GD
    Apr 14 '13 at 10:19
  • 1
    $\begingroup$ What have you done to check it yourself? $\endgroup$
    – Raphael
    Apr 14 '13 at 11:52
  • $\begingroup$ You can't prune 8 and 4 because MAX doesn't know if there are better values there or not. $\endgroup$
    – gbhall
    Apr 14 '13 at 12:22
1
$\begingroup$

I once implemented this in common lisp and running my program on your tree tells me that the pruned nodes are the one you marked and also the rightmost leaf and its parent. The output of the program gives $\alpha$ and $\beta$ values for each node (if you mark from A through X in a BFS manner, left-to-right. Then O and J are pruned).

MIN: K     -INFTY    11        [v:11]
MIN: L     11        INFTY     [v:9]
MAX: E     11        INFTY     [v:11]
MIN: M     -INFTY    4         [v:4]
MIN: N     4         11        [v:13]
MAX: F     4         11        [v:13]
MIN: B     -INFTY    11        [v:11]
MIN: P     11        12        [v:12]
MIN: Q     12        INFTY     [v:8]
MIN: R     12        INFTY     [v:4]
MAX: G     12        INFTY     [v:12]
MIN: C     11        12        [v:12]
MIN: S     12        INFTY     [v:9]
MIN: T     12        13        [v:13]
MIN: U     13        INFTY     [v:1]
MAX: H     13        INFTY     [v:13]
MIN: V     12        13        [v:12]
MIN: W     12        13        [v:9]
MAX: I     12        13        [v:12]
MIN: D     12        13        [v:12]
MAX: A     12        INFTY     [v:12]
12 
21 
T
$\endgroup$
1
  • $\begingroup$ Wow, that's awesome, thank you. Is it possible to see your source code, that would be awesome. $\endgroup$
    – gbhall
    Apr 22 '13 at 15:06
0
$\begingroup$

I was close. Here's an answer from my tutor which makes sense:

There should be some pruning on the last branch.

When descending into the third branch from the main node, the top criteria is >=12. The first sub-tree of that node sets its value to 13 (>12), so the next sub-tree is expanded. When the value of the node changes to 12 after the second sub-tree is completed, the condition triggers.

It doesn't matter what the value of the last sub-tree is. If the value is > 12 then min will choose it and max will choose the previous top-level sub-tree (value 12). if the value is <= 12 then min will choose 12 and the overall value doesn't change. For this reason the last two nodes (both value 10) are pruned before being examined.

I think he may have slightly messed up his wording in the last paragraph, but basically we are not going to improve on the 12, as min will select 12 and less, so there's no point in checking anymore.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.