I'd like to post these algorithm suggestions. The first is for
calculating an array of beatpath strengths. The 2nd is for calculating
the Smith set. I make no claim that these are the most efficient
algorithms for these purposes. There are a number of professional
computer programmers on this list no doubt have written more efficient
algorithms, but I'm posting these anyway, in case anyone is interested.
Norm Petry & Rob Lanphier are more qualified than I am for implementation
algorithms, so you should ask them if you want the
most efficient algorithms.
To calculate an array of beatpath strengths:
1. Have a 2-dimensional array of xy
2. The initial value of xy is the magnitude of x's defeat of y. If
x doesn't beat y, then the initial value of xy is zero.
3. List the defeat magnitudes xy in a list ordered by magnitude,
starting with strongest.
4. Go through the list, processing each xy as follows: For each
candidate, z, distinct from x & y:
If z beats x, and if min(zx,xy)>zy, then replace zy's value with
min(zx,xy). If y beats z, and if min(xy,yz)>xz, then replace xz
with min(xy,yz).
5. Repeatedly go through the list of xy in that way until you go
through the entire list without any changes in any of the xy.
[end of procedure]
When that has been done, each xy is the strength of the strongest
beatpath from x to y. If xz is zero, then there is no beatpath from
x to y.
To implement BeatpathWinner, of course just find the candidate(s)
who have a beatpath to each of the other candidates at least as strong
as that other candidate has to them.
To find the Schwartz set, find every canddiate who has a beatpath to
everyone who has a beatpath to him. He has no unreturned beatpaths.
If xy isn't zero, then x has a beatpath to y.
Smith algorithm:
1. List how many defeats each candidate has, starting with the one
who has the fewest.
2. Declare the one with the fewest a member of the Smith set.
3. Go through the list of candidates, and if a candidate beats or ties
a member of the Smith set, then add him, and everyone who has
no more defeats than he has, to the Smith set.
4. Repeat 3 till you go through the list of candidates in that way
with no additions to the Smith set.
[end of procedure]
As with my beatpath-magnitude procedure, I make no claim that this
is the most efficient procedure for the purpose.
Can a procedure similar to this Smith procedure find the Schwartz set?
Can it do it faster than the beatpath procedure? Could Cloneproof SSD
thereby be as fast as BeatpathWinner?
Mike Ossipoff
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com
