[EM] BeatpathWinner Algorithm
MIKE OSSIPOFF
nkklrp at hotmail.com
Thu Dec 18 03:23:01 PST 2003
Here is an algorithm to implement BeatpathWinner. It seems to me that
someone called the strongest beatpaths algorithm the Floyd algorithm. But
maybe not. When Markus said that the fragment of code that he quoted didn't
work to find the shortest path, he may have been referring to the overall
algorithm or program from which his fragment was taken. That may well be,
because the strongest beatpaths algorithm used here isn't intended to find
shortest paths. It's intended to find strongest beatpaths.
BeatpathWinner Algorithm:
The algorithm below isn't written here in any
particular programming language. But it would only
require a few small changes to make it into any
programming language.
Here's the BeatpathWinner algorithm:
First we make the strongest beatpaths array.
Place the defeat-strengths into the strongest
beatpaths array, B(i,j):
If i beats j, then B(i,j) = the number of people who
have ranked i over j.
If i doesn't beat j, then B(i,j) = 0.
repeat = 1
while repeat = 1:
change = 0
for i = 1 to N
for j = 1 to N
for k = 1 to N
least = min(B(i,j), B(j,k))
if least > B(i,k):
B(i,k) = least
change =1
endif
endfor
endfor
endfor
if change= 0
repeat = 0
endif
endwhile
When this has been done, you have the strongest
beatpaths array, B(i,j), where B(i,j) is the strength
of the strongest beatpath from i to j. (If there's no
beatpath from i to j, then B(i,j) = 0).
Then B(i,j) is used to find the winners of
BeatpathWinner:
for i = 1 to N
win(i) = 1
endfor
for i = 1 to N
for j = 1 to N
if B(j,i) > B(i,j)
win(i) = 0
endif
endfor
endfor
print "The winners are:"
for i = 1 to N
if win(i) = 1
print i
endif
endfor
[end of BeatpathWinner algorithm]
_____
_________________________________________________________________
Grab our best dial-up Internet access offer: 6 months @$9.95/month.
http://join.msn.com/?page=dept/dialup
More information about the Election-Methods
mailing list