Game Development Reference
In-Depth Information
In order to achieve the worst-case running time bound O ( n d/ 3+ O (1) ) for
the modified divide-and-conquer algorithm parity-win-dominion ( G ), we
have to make an appropriate choice of the parameter b for the calls to the
preprocessing procedure progress-measure-lifting ( G, b ). It turns out that a
good choice for the analysis of the modified algorithm is b =2
n 2 / 3
, where
n is the number of vertices of the parity game in the top-level call of the
algorithm parity-win-dominion ( G ).
Note that in order to facilitate the running-time analysis of the algorithm,
the choice of the parameter b is fixed globally for all recursive calls. This is
unlike procedure parity-win-dominion ( G ), in which the parameter has been
always the function of the number of vertices in the actual argument G of
each recursive call. It is worth noting that the analysis of the running time
of the algorithm parity-win-dominion ( G ) carried out in Section 3.3.2 could
have also been done with the parameter fixed at the top level throughout
all recursive calls.
In the following exercise we analyse the worst-case running time of the
preprocessing procedure progress-measure-lifting ( G, b ).
= b +( d/ 2)
d/ 2 = d/ 2
b + i
Exercise 3.23
Argue that
|
N b
|
i . Prove that for all
i =1
n 2 / 3
b +1
1
b +2
2
b +3
3
b +4
4
su ciently large integers n ,if b =2
then we have
·
·
·
( n 2 / 3 ) 4 , and
i ≤ n 2 / 3 for all i ≥ 3, and hence that |N b |≤n d/ 3 for all d ≥ 8.
Conclude that if b ( n )=2
b + i
n 2 / 3
then the worst-case running time of the
procedure progress-measure-lifting ( G, b ( n )) is O ( n d/ 3+ O (1) ).
We are now ready to complete the analysis of the worst-case running
time of the divide-and-conquer algorithm parity-win-dominion ( G ). Observe
that if the else -case in the algorithm parity-win-dominion ( G ) obtains then
the argument of the only recursive call parity-win-dominion ( G ) is clearly
a game with no more than n
n 2 / 3
vertices. On the other hand, if the
then -case obtains instead, then within the call parity-win ( G ) two recursive
calls parity-win-dominion ( G ) and parity-win-dominion ( G ) are made, the
argument G of the former has at most d − 1 priorities if G had d , and the
number of vertices of the argument G of the latter is, by Exercise 3.22, at
most n−n 2 / 3
decrease in size of game G or
of G , at most one recursive call is made to a game with at most d
. In either case, for every n 2 / 3
1 priorities.
Finally, each recursive call of procedure parity-win-dominion ( G ) leads to
one call of procedure progress-measure-lifting ( G, b ) which, by Exercise 3.23,
runs in time O ( n d/ 3+ O (1) ).
Exercise 3.24
Argue that the worst-case running time of the procedure