From Vasai to [code]
Sep. 28th, 2010 10:55 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
davvAs I wrote in an LJ entry, I was thinking about writing some CS problem/algorithm thoughts here. One in particular comes to mind, both because I referred to it on that other entry, and because somehow it's been stuck in my mind - its simple puzzle-like nature may be to blame, there.
(It's a funny thing; I still haven't quite got the DW-LJ balance right. I thought I would put the short "hey d00d" posts on LJ and the long ones here, but the past two LJ entries ended up quite long in themselves...)
But it's quite a jump from my creatures, and so I'll put up a cut here so it won't clutter the page of those that prefer reading about the critters :)
Everybody knows that abstract CS problems need either fancy or descriptive names. I've tended towards the latter, but I'll try one of the former here, so let's call the problem I'll describe, the "tired competitors problem".
Consider some kind of pairwise contest among n competitors. There are 0.5n(n-1) matches because the competitors don't face themselves and face each other only once. However, the type of contest they're engaged in leaves them tired, so each competitor would prefer to wait some time before he has to face somebody else. Say that the outcome of each match will be more chancy the less resting time they get.
Now, the reasonable thing would be to put waiting periods between matches so that the competitors can rest, but those who are arranging the competition would prefer it to be over quickly. Idealize the problem a little, and we're left with this:
Consider the series of matches 1...0.5n(n-1). Each match, call it p, has a score that is equal to the number of matches that pass until one of the competitors are involved in another match (whichever gets involved first). If neither gets involved, the score is equal to k >= 0.5n(n-1), since the competitors will have a long time to rest after the contest will be over. In the standard, k unspecified version of the problem, k = 0.5n(n-1), so no temporary break can be as rewarding as not having to do any more matches.
An assignment is a way of ordering the 0.5n(n-1) matches. The assignment's score is equal to the sum of the scores of all its matches.
Now, what I've been thinking about is: is it possible to find the assignment that has maximum score, in reasonable time? If so, how?
I have made a greedy algorithm that works well, but it doesn't always find the optimum. At each point, among all the contests that remain, determine the backwards score. That score is the distance to the closest of the two competitors involved in the contest in question, were it to be added to the end. Pick the contest with the greatest backwards score. Repeat until done, reverse the assignment (since the score is backwards), and that's the output.
I think that's right. For my particular purpose, the greedy algorithm works well enough, but being who I am, I still wonder about the theoretical optimum.
If you wonder what practical use such an algorithm might have, just ask!
(It's a funny thing; I still haven't quite got the DW-LJ balance right. I thought I would put the short "hey d00d" posts on LJ and the long ones here, but the past two LJ entries ended up quite long in themselves...)
But it's quite a jump from my creatures, and so I'll put up a cut here so it won't clutter the page of those that prefer reading about the critters :)
Everybody knows that abstract CS problems need either fancy or descriptive names. I've tended towards the latter, but I'll try one of the former here, so let's call the problem I'll describe, the "tired competitors problem".
Consider some kind of pairwise contest among n competitors. There are 0.5n(n-1) matches because the competitors don't face themselves and face each other only once. However, the type of contest they're engaged in leaves them tired, so each competitor would prefer to wait some time before he has to face somebody else. Say that the outcome of each match will be more chancy the less resting time they get.
Now, the reasonable thing would be to put waiting periods between matches so that the competitors can rest, but those who are arranging the competition would prefer it to be over quickly. Idealize the problem a little, and we're left with this:
Consider the series of matches 1...0.5n(n-1). Each match, call it p, has a score that is equal to the number of matches that pass until one of the competitors are involved in another match (whichever gets involved first). If neither gets involved, the score is equal to k >= 0.5n(n-1), since the competitors will have a long time to rest after the contest will be over. In the standard, k unspecified version of the problem, k = 0.5n(n-1), so no temporary break can be as rewarding as not having to do any more matches.
An assignment is a way of ordering the 0.5n(n-1) matches. The assignment's score is equal to the sum of the scores of all its matches.
Now, what I've been thinking about is: is it possible to find the assignment that has maximum score, in reasonable time? If so, how?
I have made a greedy algorithm that works well, but it doesn't always find the optimum. At each point, among all the contests that remain, determine the backwards score. That score is the distance to the closest of the two competitors involved in the contest in question, were it to be added to the end. Pick the contest with the greatest backwards score. Repeat until done, reverse the assignment (since the score is backwards), and that's the output.
I think that's right. For my particular purpose, the greedy algorithm works well enough, but being who I am, I still wonder about the theoretical optimum.
If you wonder what practical use such an algorithm might have, just ask!
no subject
Date: 2010-11-08 06:10 am (UTC)If you wonder what practical use such an algorithm might have, just ask!
Oh yeah, and: I ask!
no subject
Date: 2010-11-08 10:05 am (UTC)That's interesting... I could check whether that's the case. If it is, I think it is by side effect: bracket tournaments are designed to be intuitive and to be quick (only needing n contests to determine the winner, or n log n for a ranking).
Oh yeah, and: I ask!
Consider the tournament matrix idea to producing a personal transitive ranking of items (such as pictures). In the complete version, the program asks 0.5n^2 times and finds the ranking that minimizes the number of "upsets". This can be either done once or multiple times - if multiple, the matrices are simply summed.
Now, say that the "voter" is considering A vs B. If he next considers A vs C, then he may be biased by the previous comparison. By moving A vs C away from A vs B, there's a greater chance that he has forgotten the A vs B comparison by the time he has to judge if A is better than C. Thus one would expect to get more representative results that way.
Some actual experiments would be useful, however, because there might be a switching advantage to spacing similar contests closer: that is, if you've considered A vs B, you're better prepared to consider A vs *, or B vs *. The experimental protocol would be something like: organize a bunch of people into two groups. The first goes through the algorithm with comparisons changed to space individual "contestants" as far apart as possible, and the second goes through the algorithm with the "contestants" as close as possible. Both do these a number of times to find a stable ranking. Then one checks which are less noisy - which group has individuals whose results converge to the final the quickest.
But I don't have access to that, so intuition has to suffice, and to me, it seems bias is more likely than switching.